FameofLight ACRush: Finally the god of programming arrives
FameofLight ACRush: do you follow a random practice , or you practice question by topic , in your early days
ACRush FameofLight: No, our team practiced 3 or 4 full contests a week.
pt1989 ACRush: Can u tell us whom or what do u credit for ur success?
ACRush pt1989: I think more practice is the way.
ktuan ACRush: how can you arrange your study with 3-4 contests a week ?
ACRush ktuan: UVA, SGU , ZJU and PKU is enough.
pt1989 ACRush: what is ur method of practising? random or organised?
ACRush pt1989: contest env. We always solve programs in contest env.
Sunny_05 ACRush: wat is ur daily routine ?? i mean hw do u practice everyday ??
ACRush Sunny_05: We only have weekly routine for practice.
binarywithme ACRush: what u think about world final problems..level of difficulty
ACRush binarywithme: A little harder than 1000p.
MB__ ACRush: Which of these do you do after you submit your solution on TC: test solution, re-read problem statement, check code line by line
ACRush MB__: test for at least 10 cases.
martins256 ACRush: how many problems have you solved on OJ ?
ACRush martins256: about 2000.
kcm1700 ACRush: How many problems have you proposed on OJ or anything like this competition or something…?
ACRush kcm1700: about 2000.
vijay_comc ACRush: Who is your Arch Rival in Programming ? 😉
ACRush vijay_comc: Petr, I think.
SomethingWrong ACRush: What is your favourite Online Judge? 🙂
ACRush SomethingWrong: SGU.
vexorian ACRush: Why SGU?
ACRush vexorian: More tricky testcases.
Dee2306 ACRush: Being one of top programmers, do u believe its just practice which makes u perfect.. or some of u are born genius ?? 🙂
ACRush Dee2306: It’s at least 80% due to practice
stormsky ACRush: how to practice ACM for a ACM beginner?
ACRush stormsky: practice in contest env.
piva ACRush: Do you train more of one category of problems? Or you just solve problems at random?
ACRush piva: I do more practice in the ones I have troubles with.
pt1989 ACRush: what are ur interests other than programming?
ACRush pt1989: WarCraft.
vijay_comc ACRush: Petr is already married. No plans to compete him in that area ? 😀
ACRush vijay_comc: ….not yet.
Sarkin ACRush: Is analyzing algorithms an essential part of learning algorithms?
ACRush Sarkin: Not all, I think coding is in practice room is the rest way.
abdessamad ACRush: can believe it! when i see your challengers 😀 😀
ACRush abdessamad: It’s one thing that Petr did much better than me.
stjepan ACRush: where did/do you practice most and how?
ACRush stjepan: And join contest.
binarywithme ACRush: why u choose c++ as a default programming language
ACRush binarywithme: er.. Stl is the first reason. Another one may be efficient.
geekru2 ACRush: during contest, what kind of problems do u enjoy doing? as in type of problem?
ACRush geekru2: dp and network-flow.
reginachris ACRush: What’s the best OJ to start with for practice (UVa, SPOJ, TC, etc.)?
ACRush reginachris: USACO
ferry ACRush: What do you do when you can’t solve a problem or you don’t know what’s wrong?
ACRush ferry: I will try to pass it in practice room. I always do that.
geekru2 ACRush: Do you solve puzzles and mind bending questions to improve your problem solving techniques?
ACRush geekru2: no. I don’t like such problems like suduko.
Sarkin ACRush: What algorithm types helped you in the IOI?
ACRush Sarkin: dp.
abdessamad ACRush: did you like chess?
ACRush abdessamad: yes.
geekru2 ACRush: when in a team event(IOI etc), do you dominate while programming?
ACRush geekru2: yes. I guess.
kcm1700 ACRush: how do you prepare data for the challenge phase?
ACRush kcm1700: The trickiest one, of course.
binarywithme ACRush: sir what is the best way to learn DP.
ACRush binarywithme: TC contest.
[dasha] ACRush: When u were beginning to compete,did u have any problems? Like low speed of sloving, or maybe some particular method u couldn’t understend for a long time, sth else? If yes, how did u get over that?
ACRush [dasha]: USACO is a really good place. Especially for the beginners.
frank44 ACRush: how long did the usaco practice take you?
ACRush frank44: half one year.
binarywithme ACRush: what u think math should b strong to become a Gud programmer
ACRush binarywithme: The mathematical foundation is helps.
khanhptnk ACRush: excuse me, do you think what we should prepare before an important contest ?
ACRush khanhptnk: relax, and rush some simple problems. And solve some problems in a contest env. is also helpful.
Sarkin ACRush: Do you recommned reading "Introduction to Algorithms"? if you know?
ACRush Sarkin: Really good.
coder29 ACRush: which parts do u advice to read in "Introduction to Algorithms"?
ACRush coder29: All parts are perfect. except complexity.
MB__ ACRush: do you do any sports but topcoding?
ACRush MB__: soccer.
vijay_comc ACRush: Complexity in CLRS is flawed ?? 😮
ACRush vijay_comc: 7-8
Sarkin ACRush: What do you mean except comlexity?
ACRush Sarkin: That’s only my opinion.
pcaldeira ACRush: which skill do you consider most important on TCHS/ioi-style contests?
ACRush pcaldeira: algorithm skills and coding ability.
coder29 ACRush: I am newbie…which OJ is better fr me…USCO or UVA?
ACRush coder29: USACO
hakami ACRush: Are you useing library or typing from first for SRMs?
ACRush hakami: some includes and basic untilities.
vrajesh1989 ACRush: Will you try to prove your algorithms to yourselves during contest time or just believe your intuition and start coding?
ACRush vrajesh1989: Yes, it’s very important for me.
Sarkin ACRush: Do you use algorithm analyzis when solving a problem to see it’s effeciency?
ACRush Sarkin: Yes. the effeciency sometimes is more important than correctness in TC contest.
coder29 ACRush: basically i want 2 to do pratice on DP and greedy types…is TCs’ room are sufficient..?
ACRush coder29: A bulk of dp tasks in SRMs. TC’s room is good.
rajeshsr ACRush: In short, what is the strategy for becoming a good coder, according to u?
ACRush rajeshsr: Practice is the way.
Lingmum ACRush: How can we improve our speed of solving the problems,more problems?
ACRush Lingmum: More practice.
stormsky ACRush: do you often practice TC?and how to practice?
ACRush stormsky: Yes. But in fact, I prefer to doing past Regionals and finals.
sahiltiwari ACRush: how many hours you practise per day ?
ACRush sahiltiwari: 4-5
MohammadReza ACRush: What do you do to make your code becomes bugfree although the big size?
ACRush MohammadReza: test more tricky cases.(corner cases)
rajeshsr ACRush: Sorry to be repetitious, But I want to know what is the strategy of practice you employed? U select some random problems from OJs and solve or try to master a particular domain like DP by solving problems based on that or any other thing?
ACRush rajeshsr: set problems of past regionals and finals.
puneetkp444 ACRush: Can you suggest some ways to improve problem solving abilities
ACRush puneetkp444: practice all kinds of problems.
alft7 ACRush: what do you usually do before a very important competition, practise or something else?
ACRush alft7: practice until 3 days before it.
ferry ACRush: What is the hardest problem you’ve done?
ACRush ferry: I in WF2007.
分类存档：默认分类
[SPOJ pgcd]【容斥原理】【常数】
【地址】http://www.spoj.pl/problems/PGCD/
【题目大意】
10组数据，给定(m,n)，问gcd(i,j)=素数的对数(1<=i<=m,1<=j<=n) m,n<=10^7
【算法】
不妨设m 先筛出素数和miu函数。 然后暴力容斥。 for (int d=2;d<=m;d++) if (prime[d]) for (int j=1;j<=m/d;j++) ans+=miu(j)*(m/d/j)*(n/d/j) 这样是 m lg m的 miu是容斥系数。 特别地miu[1]=1。 miu[i]=1 i为Square-Free-Number并且i有偶数个素因子 miu[i]=-1 i为Square-Free-Number并且i有奇数个素因子 miu[i]=0 other 这样会TLE。 那么看我们所求。 sigma{ miu[j]*( m/(d*j) )*n/( n/(d*j) ) } 其中d*j<=m && d为素数 尝试枚举d*j的值。令x=d*j，由于d为素数，令x=p1^k1 * p2^k2 * p3^k3 … 其中pi为素数。 那么现在看看会出什么结果。 1、 假如ki全为1。那么从里面拿出一个素数d，会剩下一个Square-Free-Number。 设x有t个素因子。 j含有的素因子个数必然为t-1。所以所有的j的miu值都一样。而取法有t种于是ans+= ( ((t-1)&1)?-1:1 ) * t * (m/x) * (n/x) 2、 假如ki有一个是2，其它全是1，那么只能拿出那个ki=2的，否则剩下的不是SFN，miu值=0，无须计算。 这样设拿走了那个ki=2的一个素因子以后，剩下t个素因子。那么显然 ans+=( (t&1)?-1:1 )*(m/x)*(n/x) 3、 其它的不可能拿走一个素数以后得到SFN了。于是miu值都=0，不必考虑。 于是。。。枚举x。然后按照上面的情况分别搞就行了。 实际上都是P[x]*(m/x)*(n/x)的形式。由于上面的分类是针对x这个数值的，所以可以通过筛选法把P[x]预处理出来。 然后for (int x=2;x<=m;x++) ans+=P[x]*(m/x)*(n/x)就行了。 但是这样还不够快。 注意到m/x和n/x都只有sqrt级别个结果。于是随着x的递增，(m/x)*(n/x)只有sqrt(m)+sqrt(n)级别个结果。 通过对P[]建立前缀和数组，可以迅速知道区间的P[]之和。那么对于(m/x)*(n/x)相同的部分，直接跳过一整段， ans+=(S_P[r]-S_P[l-1])*(m/x)*(n/x) 其中(m/l) * (n/l) == (m/r) * (n/r) 。 【时间复杂度】 一开始的筛O(n)的 后面每个询问sqrt(n)的。 【其它】 出现了很诡异的事件- -，我用O(n)的筛，45S。 用O(n lg n)的筛，31S。 不明真相中。 【CODE】
#include #include #include #include #include using namespace std; const int N=(int)1e7; int F[N+5]; int cnt_1[N+5]; int cnt_2[N+5]; int S[N+5]; void Get_Prime(){ S[2]=0; for (int i=2;i<=N;i++){ if (cnt_1[i]==0){ F[i]=i; cnt_1[i]=1; //这个筛是n lg n的- -，但不知道为什么，居然比线性筛快。求指导。。。 /* for (int j=i+i,c=2;j<=N;j+=i,c++){ cnt_1[j]++; if (c==i){ cnt_2[j]++; if (cnt_2[j]==1 && j/i/i%i==0) cnt_2[j]++; c=0; } } */ } for (int j=2,k=i+i;j<=F[i];j++,k+=i){ if (k>N) break; F[k]=j; cnt_2[k]=cnt_2[i]+(j==F[i]); //计算k有多少个i^2形式的因子 cnt_1[k]=cnt_1[i]+1; //计算k有多少个因子。 } int t; int &c1=cnt_1[i]; int &c2=cnt_2[i]; if (c2==0) if (c1&1) t=c1; else t=-c1; else if (c2==1) t=( (c1&1)?1:-1 ); else t=0; S[i+1]=S[i]+t; } } int main(){ Get_Prime(); int Tc,m,n,d1,d2,Next_1,Next_2,Next; scanf("%d",&Tc); while (Tc–){ scanf("%d%d",&m,&n); if (m>n) swap(m,n); long long ans=0; for (int i=2;i<=m;){ d1=m/i; d2=n/i; Next_1=m/d1+1; //Next_1>i && m/Next_1>m/i Next_2=n/d2+1; //they are the same Next=Next_1 ans+=(long long)(S[Next]-S[i])*d1*d2; i=Next; } printf("%lldn",ans); } }
[POI2007 Zap]容斥原理
【url】http://www.zybbs.org/JudgeOnline/problem.php?id=1101
【题目大意】没法大意了- -，直接原题吧。
【算法】
直接暴力容斥可以在O(min(a,b))时间复杂度内解决一个询问。
先a/=d,b/=d
答案为Sum(d[i]*(a/i)*(b/i))，2<=i<=a其中d[i]是容斥系数。
那么可知a/i只有sqrt(a)级别种结果。b/i也只有sqrt(b)级别种结果。
也就是说随着i的递增，a/i和b/i总的变化数是sqrt(a)+sqrt(b)级别的。
于是对于a/i和b/i相同的放一组。一共只会有sqrt(a)+sqrt(b)级别组。通过对d构建前缀和数组可以做到O(1)处理每一组。
然后就没了。
【其它】
作为AC的门徒、外加NOI2010囧人，此题不切说不过去- –
【CODE】
#include #include const int N=50005; int d[N]; int S[N]; bool prime[N]; void predo(){ memset(prime,true,sizeof(prime)); for (int i=2;i<=50000;i++) d[i]=1; for (int i=2;i<=50000;i++) if (prime[i]){ for (int j=i+i;j<=50000;j+=i){ prime[j]=false; if (j/i%i==0) d[j]=0; d[j]=-d[j]; } d[i]=-1; } S[1]=0; for (int i=2;i<=50000;i++) S[i]=S[i-1]+d[i]; } void swap(int &x,int &y){ int t=x; x=y; y=t; } int min(int x,int y){return x int Get_Next(int a,int b){ // let ret=a/b this function get the smallest number x satisfy a/x!=ret && x>b return a/(a/b)+1; } int main(){ predo(); int Tc; scanf("%d",&Tc); while (Tc–){ int m,n,dd; scanf("%d%d%d",&m,&n,&dd); m/=dd; n/=dd; long long ans=(long long)m*n; if (m>n) swap(m,n); for (int i=2;i<=m;){ int Next=min(Get_Next(m,i),Get_Next(n,i)); long long tmp=(long long)(m/i)*(n/i); ans+=(S[Next-1]-S[i-1])*tmp; i=Next; } printf("%lldn",ans); } }
Codeforces Beta Round #71 （A～D）
A
直接模拟即可。10^6
B
【题目大意】
m*n的方格(m,n<=4*10^4)，有一些格子坏掉了(数目<=10^3)。然后以
for (int i=1;i<=m;i++)
for (int j=1;j<=n;j++)
的顺序填好的格子，依次填上Carrots Kiwis Grapes.
然后有<=10^3个询问，问第i行第j列的格子是什么。waste表示坏格子。
【算法】
(i,j)->(i-1)*n+j
然后根据排序二分。得出<=自己的坏掉的格子的数目。
C
【题目大意】
给定一个10^5的串，然后给出10个小串，他们的长度都<=10。然后问你大串满足不包含小串的最长连续子串是多少。
【算法】
令C[i]表示以大串第i位为结尾和小串匹配时的最短小串长度。如果没有小串和大串在以i为结尾的地方匹配，那么C[i]=oo。
然后就i递增地扫描，然后记now为当前以i为结尾的最长匹配长度。如果now>=C[i],那么now=C[i]-1。记录过程中最大的now与位置即可。
【时间复杂度】
10^7 —暴力
10^6 —KMP
10^5 —自动机
D
【题目大意】
1..n个格子，有黑白，一开始全白。其中有k个不相同的key_blocks。然后有m种操作。每种操作为L[i]，表示可以选择一段长度为L[i]连续格子翻转。
问最少多少步使得所有key_blocks变黑，其他格子全白。
【算法】
看了解题报告、
这个模型的转换确实挺巧妙的。
令b[i]=a[i]^a[i-1]。其中a[i]就是原格子的黑白状态。那么b[i]=0表示a[i]==a[i-1]。否则不等。
添加a[0]=0。那么用b可以完整表示出a。(要添加a[n+1]=0,b[n+1]=a[n]^a[n+1]，key_blocks如果前后没有，就要1变2了)
然后翻转连续的一段，就会只更改b的两个值x和x+L[i]，1<=x<=n+1。这样模型就很适合反映情况了。
更改两个b的值表示两个点有边，那么问题变成我们选择一些边，使得key_blocks对应的点度为奇数，其它点度为偶数。
因此答案必然可以分割为若干条简单路径，每条简单路径的起始点和结束点都是key_blocks，而且每个key_blocks会被覆盖1次且仅1次。于是可以bfs算出各个key_blocks间的最短距离。然后SCDP取得最优解。
可见把模型转化成合适的形式是很重要的。
【时间复杂度】
mnk + 2^(2k) * k
这场之后rating达到新高1922。= =，希望接下来一场多人点的把我带红。
这两天缺席了一场TC，一场CF、据说这两场都很好涨rating？555555555555555
[SWJTU1705 GreatAccepted]【贪心】
【Link】http://acm.swjtu.edu.cn/JudgeOnline/showproblem?problem_id=1705
【题目大意】
n个数，你每次可以取<=3个数出来将他们都-1。然后放回去。问将所有数变为0至少需要多少次操作。
输出的两个数中第二个数是Sum
【算法】
lcc大神一下就秒杀了。我完全YY不出来。
first of all，每次取最大的3个出来减这种贪心是肯定没问题的。
但是数目太多了。
考虑每次都只能将一个数-1。
所以答案至少是最大那个数。
设m1是最大那个数，m2是次大那个数。
那么看看m1什么时候会将答案卡住。
很容易想到就是每次m1都减，减到最后的情况。然后看剩下的2个名额怎么去减。
用这两个名额，
要么是m2把这个名额卡住了，
要么减到最后剩下一个1，
要么是除了m1全部减为0。
(原因可以模拟一开始的贪心看看)
后面两种就判一下是不是Sum-m1<=m1*2就可以了。
第一种的卡住，只能发生在m2一直减，减到最后的情况，所以就是Sum-m1-m2<=m2。
答案被卡住的情况解决了，剩下的就是没被卡住的情况。
这些情况的答案都是Sum/3向上取整。
还是参见一开始的贪心，现在假设n>3(n<=3必然是答案是m1)每次我们都选最大的3个减。最后因为不会再被m1卡住了。设这些数中最小值为min，容易必然能够转到下面3种情况中的一种。
1、所有数都=min
2、2个数=min，其余数=min+1
3、1个数=min，其余数=min+1
转化为这个以后、、不断的3个3个减。。。很容易知道最后要么刚好减完，要么剩一个1，要么剩2个1。因为都是3个3个减，所以就和它% 3的结果有关系。。。于是就是Sum/3向上取整了= =
【其它】
Orz lcc大神
【CODE】
#include #include #include #include using namespace std; int main(){ int Tc,n; int a[1005]; scanf("%d",&Tc); for (int k=1;k<=Tc;k++){ scanf("%d",&n); for (int i=0;i scanf("%d",&a[i]); sort(a,a+n); int Sum=0,ans; for (int i=0;i if (n<=3) ans=a[n-1]; else if (Sum-a[n-1]-a[n-2]<=a[n-2]) ans=a[n-1]; else if ( Sum-a[n-1]<=a[n-1]*2 ) ans=a[n-1]; else ans=(Sum+2)/3; printf("Case #%d: ",k); printf("%d %dn",ans,Sum); } }