Hi everyone!

I am pleased to announce that Codeforces Round #304 (Div.2), of which I am the author, will take place today. This will be my first round, so I hope that it will be cool and interesting. Traditionally Div.1 participants can take part out of the competition.

I want to thank znirzej, Dakurels and Zlobober for help with preparing the problems, thank Delinur for translating the problems, and thank to MikeMirzayanov and all who created polygon for this great system.

I wish you all good luck!

UPD Scoring will be 500-1000-1250-1500-2250.

UPD editorial

UPD Congratulations for winners in div.2:

And in div.1:

• +237

 » 6 years ago, # |   0 Thank You. :)
 » 6 years ago, # |   0 Hope to participate officially on your next contest :)
 » 6 years ago, # |   -12 Hope next time you arranged problems for both division . thanks .
 » 6 years ago, # | ← Rev. 2 →   -10 .
 » 6 years ago, # |   +52 Wow, polish round!
 » 6 years ago, # |   +1 "Scoring will be announced later." Hope it's not just a minute before the contest starts.
•  » » 6 years ago, # ^ |   +22 i am new here so plz help me how does knowing the score pattern help..?
 » 6 years ago, # |   +5 Radewoosh fought a lot in yellow but at the end he is red congrats and all the best for next rounds.
 » 6 years ago, # |   0 "This will be my first round" , hope to find it interesting like Codeforces Round #303 (Div. 2) which was the first one of its author too =D
 » 6 years ago, # |   +15 I wish all participants of Div2 to reach Div1.;)
•  » » 6 years ago, # ^ |   +12 this can never happen because rating change depends on rank of participant
 » 6 years ago, # |   +9 An only div2 round from a red.it will be interesting.
 » 6 years ago, # |   +24 I hope this round will be not easy like last contest
 » 6 years ago, # |   0 3+0+4=7 ... It's lucky Seven. I think this round will bring good luck for all.
 » 6 years ago, # | ← Rev. 3 →   +9 Scoring : 500-1000-1250-1500-2250. Looks like that the problems are not hard except E
•  » » 6 years ago, # ^ |   +8 and E is an easy E
•  » » 6 years ago, # ^ |   0 It seems that Div2 contests are becoming easy!
•  » » » 6 years ago, # ^ |   +11 So, let's go to div 1?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +10 The last contest had 2 problems with score 1750 but both were very easy. Let's just wait for the problems.
•  » » » 6 years ago, # ^ |   +5 the two problems were with score 1750 , and i agree with you , they were very easy .
 » 6 years ago, # |   0 My first contest (:
•  » » 6 years ago, # ^ |   +1 Maybe you win this contest like Bell-sama in the last contest ;)
 » 6 years ago, # |   +5 Too many unrated participants in top 20 -_-
 » 6 years ago, # | ← Rev. 2 →   -9 farnasirim has n badges.Who are the n lucky coders who want to receive badges ?
•  » » 6 years ago, # ^ |   +7 No badges for those who use these kinds of names for innocent variables.
•  » » » 6 years ago, # ^ |   +3 This was a joke, but please here is not write a bad word. Admin please delete this message. sorry for my poor English.
•  » » » » 6 years ago, # ^ |   -8 This is not a joke, this is a screenshot. I am sorry I should have set an age guard so it wouldn't teach bad words to 2 year olds. Also your age is not elligible for receiving a badge. So stop trying too hard :/
•  » » » » » 6 years ago, # ^ |   0 I'm not good in English but you can understand me... There are girls from our counry or other cultural countries in this site, so such messages aren't eligible to be written here. I think you are schoolboy who doesn't know how to behave!
•  » » » » » » 6 years ago, # ^ |   -8 Dick/Sperm (although not directly written by me) are facts that women from your country have to know about sooner or later :) No, I am a schoolboy who does not understand the way you think.
 » 6 years ago, # |   +4 The hack checker for the problem B has some problem as it gives an "Invalid Input" result for a valid input. Please check.
•  » » 6 years ago, # ^ |   +4 Did you output "\n"?
•  » » 6 years ago, # ^ |   +3 The test file must be closed with '\n'
 » 6 years ago, # |   +8 hack checker for problem B seems to be giving invalid input,have tried multiple times
 » 6 years ago, # |   0 It's a little bit strange... this round seems too easy. Look at the number of accepted solution.
•  » » 6 years ago, # ^ |   0 And look at the number of successful hacks!!!
 » 6 years ago, # |   0 waiting for D solutions to fail main tests... ;)
 » 6 years ago, # |   +14 How to solve E ?
•  » » 6 years ago, # ^ |   +9 Its a maxflow problem. Make a 2*N + 2 vertices , 2 copies of each node and 1 source and 1 sink. Now you can find out the respective edges required to make the graph (think about it a little bit, if u know max flow , else u can read about it), that part is only left. Then find the max flow from source to sink and print it.
 » 6 years ago, # |   +4 What were all the hacks on B and D?
•  » » 6 years ago, # ^ |   +13 I got hacked in D cause I used cin cout for input. Though I am pissed, I must say, that was a clever hack!
•  » » » 6 years ago, # ^ |   0 Me too, Failed system test case because of cin cout
•  » » » 6 years ago, # ^ |   +3 I'm sorry but why would cin,cout fail?
•  » » » » 6 years ago, # ^ |   0 cin cout streams are slower than scanf and printf. We have to read in about 2 million integers from the input file and write another million as output. The overhead in cin cout is just too much (will take more than 3 seconds) and thus your solution will timeout. Morever, the "endl" command to add a newline character has another overhead, it adds a newline character AND empties all buffers.It is advisable to use scanf printf for faster input/output operation.Try it out yourself on some local files and see which is faster
•  » » » » » 6 years ago, # ^ |   0 Okay, thank you!
•  » » 6 years ago, # ^ |   +3 you should've used scanf and printf instead of cin and cout I guess..
•  » » 6 years ago, # ^ |   0 For B:51 1 1 1 1
•  » » » 6 years ago, # ^ |   0 result is it 10?My code is giving me 10 as result
•  » » » » 6 years ago, # ^ |   0 Yea, it's 10.
•  » » 6 years ago, # ^ |   0 B: 5 1 1 1 1 1 D: very long input and output
•  » » 6 years ago, # ^ |   0 Well, I hacked D's that should obviously TLE, so the maximum tests weren't included in pretests. For B, there were a lot of incorrect solutions that had Passed Pretests.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +9 See these first timers on codeforces. /\
•  » » 6 years ago, # ^ |   +5 also i hacked 1 ppl using this test:33 3 3
•  » » 6 years ago, # ^ |   +1 Many did a brute force on D and didn't pre-calculate the values .
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 I've made 6 hacks with following test:103 3 3 3 3 3 3 3 3 3Most solutions used if(a[i] > 1) instead of while(a[i] > 1)Also, there was a case of 3000 times of 3000, which may cause overflow on some solutions, but I haven't tried that
 » 6 years ago, # |   +2 So weak pretest on B. And I locked it ...
 » 6 years ago, # |   +4 Thank you for the contest. Though I did some really really stupid mistakes.
 » 6 years ago, # |   0 Why my hacking test case for 2nd question is showing invalid input. I simply put n 3000 and write 3000 number of value 3000.
•  » » 6 years ago, # ^ |   +5 At the end need to add Enter.
•  » » » 6 years ago, # ^ |   0 Thanks!! This may be the problem :)
 » 6 years ago, # |   +1 I've tried to answer queries (in problem D) by using a prefix sum table of number of prime factors of numbers. But it's not fast enough. What's an efficient way to find number of prime factors of a number (not necessarily distinct)?
•  » » 6 years ago, # ^ |   0 I also tried the same
•  » » 6 years ago, # ^ |   0 I don't know, is my solution correct, but I did it in such way:1) Let's calc the Eratosphen Sieve and take all prime divisors for every number in [1..5*10^6]2) For each number let's divide it while we can, by all prime numbers, that we calculated.So, it works about 2,9 sec
•  » » » 6 years ago, # ^ | ← Rev. 3 →   0 This was my approach http://ideone.com/2eGhhsis it correct and what can I do to optimize it?
•  » » » 6 years ago, # ^ |   0 My first contest where I have solved ALMOST 4 out of 5 problems
•  » » » 6 years ago, # ^ |   0 I believe you only need to calculate primes up to sqrt(5000000) and if a number can't be divided by any of the primes you have, it must be a prime.P.S. My solution is the same so my submission code can be used to understand the idea. http://codeforces.com/contest/546/submission/11220118 (not sure if it's already visible but it will be soon enough).
•  » » 6 years ago, # ^ |   0 you just need to count sum of prime factors for each number,and then answer is d[a]-d[b](it't easy to show),for this precalculation you just need sieve of eratosthenes and for each prime p and number k; while (k | d) increase d[k],k=k/d
•  » » » 6 years ago, # ^ |   0 Can you explain why my code isn't fast enough then? I think I did the same thing. My Implementation
•  » » » » 6 years ago, # ^ |   0 You only need primes up to the sqrt(5000000) A couple iterations could be saved by moving prime=2 out of the loop when generating primes. Apart that, it is quite similar to what I wrote. I think it's the 1st problem that is making your code too slow.
•  » » » » » 6 years ago, # ^ |   0 Thanks for help, but I think your solution doesn't work either. Editorial's solution is O(N).
•  » » 6 years ago, # ^ | ← Rev. 2 →   +3 You don't need to find the number of prime factors per se in this problem or even calculate prime numbers per se.What I did in D was to calculate for each number the lowest number that divides it (it will be a prime). You can do it with a Sieve of Eratostenes by assigning to each number the first number that divides it and ignore other divisors.Knowing the smallest divisor for each number you can use a O(n) dynamic programming solution where:numDivisors[i] == 1 + numDivisors[i / smallestDivisor[i] ].You are basically dividing the number by it's smallest divisor and then adding the already calculated result for the remaining number.Then you calculate the accumulated number of divisors from 1 to 5 000 000 and then for each query you can calculate the result by subtracting accum[a] — accum[b] since a!/b! is the same as (b+1)*(b+2)*...*aThe highest complexity of the algorithm will be the either the sieve calculation or the number of queries.Edit: Code
•  » » » 6 years ago, # ^ | ← Rev. 3 →   +11 calculate for each number the lowest number that divides it it can be done with linear complexity. Described at e-maxxYou can see it in my submission : 11225962
 » 6 years ago, # |   0 What about E ?
•  » » 6 years ago, # ^ |   0 Max-Flow
•  » » » 6 years ago, # ^ |   +3 but how? we can move soldiers from this city only to the neighbours:) ?
•  » » » » 6 years ago, # ^ |   +3 You can make a flow graph with 2 * N + 2 nodes. The last 2 are dummy source and sink. You also have N original soldier nodes and N final soldier nodes.The edges are from the source to each original node, the original soldiers on each of such nodes. Then from the original nodes you connect to the final nodes where the soldiers can move, i.e, the neighbor nodes or the same node.Finally the final nodes are connected to the sink with capacities equal to the number of soldiers that are expected for each of the nodes in the end.If the flow is exactly equal to the sum of the soldiers and the if the final configuration has the same number of soldiers then it's a YES and you print the flows for each of the edges between original and final.My code
 » 6 years ago, # |   -19 I think, to hack is not honest. These contests are a test, but not a game "how to hack other people". I really hate hacks. Sorry for bad English)
•  » » 6 years ago, # ^ |   +3 Hack at least improve your understanding of other contestant code, and also finding a bug in their program. It really helps me creating some corner test case.
 » 6 years ago, # | ← Rev. 2 →   0 This round featured the most hacks i ve ever seen.I think the pretests were made too easy.
 » 6 years ago, # |   +1 How to solve D? I thought segment tree might be useful but even if I use it, it still takes a lot of time to calculate each score of numbers...
•  » » 6 years ago, # ^ |   0 Preprocessing is the key. Just count the amount of divisors for all the numbers in range 5000000, then create an array, i-th element of it contains a sum of divisors for all the elements in range (1..n) and then use it to calculate the answer — Arr[n]-Arr[k]
•  » » » 6 years ago, # ^ |   0 I guess counting the amount of divisors for all numbers up to 5000000 can take more than 3 sec?
•  » » » » 6 years ago, # ^ |   +1 the array of constant amounts, i guess. Just create it during the coding process of other problems and then use it in your program.
•  » » » » 6 years ago, # ^ |   0
•  » » 6 years ago, # ^ |   0 Answer was obviously phi(A)-phi(B) where we define phi(N) as number of all prime factors of N . (Ex- phi(12)=3 as 2*2*3). to compute phi(N) we could precompute using Sieve .
•  » » » 6 years ago, # ^ |   0 Yes, you are right. I don't need to use segment tree in this problem.
 » 6 years ago, # |   0 I use ios::sync and cin.tie on problem D. Am I get TLE??
•  » » 6 years ago, # ^ |   0 I guess you'll have to wait and see?
•  » » » 6 years ago, # ^ |   0 I can't wait anymore XD. OK :)
•  » » » » 6 years ago, # ^ |   +8 I know how you feel! :D
•  » » » » » 6 years ago, # ^ |   0 My solution passed system tests. YEEEEEES! XD
•  » » 6 years ago, # ^ |   0 i too used cout,cin!!
 » 6 years ago, # |   0 How to solve problem E ? I was having almost 1 hour for this problem but not able to come up with any idea.
•  » » 6 years ago, # ^ |   0
 » 6 years ago, # |   +1 All problems are very interesting. Thanks to author.
 » 6 years ago, # |   0 How to solve problem D?
•  » » 6 years ago, # ^ |   0
 » 6 years ago, # |   +1 I know some people are claiming it was too easy; but I personally like being able to actually try out a couple problems in a competition for once. Feels nice to succeed for a change!
 » 6 years ago, # |   +1 Will cin cout give TLE on D ?? Even if the query is answered in O(1) ??
•  » » 6 years ago, # ^ |   0 yes,cout<
•  » » » 6 years ago, # ^ |   0 Thank God... I have #define nline printf("\n") and I have used nline I just hope it passes himanshujaju I have used int arrays..
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +4 Thanks Got TLE with cin-cout and AC with printf-scanf disheartened :(
•  » » 6 years ago, # ^ |   +3 i guess yes. my solution was hacked. i changed all to int's and scanf printf. if you used int, it may pass easily.
 » 6 years ago, # |   -6 I hate those expert programmers, who got problem D right, and just to earn a few more points started to hack other people's solutions by giving large number of test cases and large values of a and b. One guy in my room was just sitting with that intention, that whenever this person locks it, I have to hack it :(
•  » » 6 years ago, # ^ |   +6 I don't see anything bad in it. For example, I knew that my solution is incorrect before end of contests and had chance to resubmit...
 » 6 years ago, # |   0 Why did I get a message saying I should not use %lld in problem A? Is using it bad? I ignored it since I don't know another way to do it and I passed the pretest. Could someone please explain how to read long long in c++ without using it and why I should not use it?
•  » » 6 years ago, # ^ |   0 It depends on the OS of the checking server. If it is linux than %lld is okay, but codeforces is using windows — so the right way is %I64d
•  » » » 6 years ago, # ^ |   0 oh no, I compiled it in my linux computer typing in %l64d and it didn't work. So for future occasions I just have to declare the variables as long long (as normal) and then when using printf and scanf substitute %lld with %l64d ?Am I going to get it wrong because of that though?
•  » » » » 6 years ago, # ^ |   0 If the online-judge system is CF — then yes, you should do it like that. I don't know about other online-judges like timus, topcoder etc.
 » 6 years ago, # |   +1 Are there 2 pretests in problem D??? REALLY??????
•  » » 6 years ago, # ^ |   +14 because each test case contains number of games!
 » 6 years ago, # |   +2 For D, I used a sieve to find the prime numbers which worked very fast. Then, for each number in range [1;5 000 000] I calculate the number of prime divisors using only prime numbers(that I put in vector) which don't exceed sqrt(cur number). Then, partial sums. Is it the correct solution? The slow part was the one with finding the divisors/ any trick I missed?
•  » » 6 years ago, # ^ |   0 Fast IO ?
•  » » » 6 years ago, # ^ |   0 No, this not the problem because after calculate the divisors for each number I wrote cout<<"Ready!\n";return 0; and wait for 10-20 seconds and nothing happen. I saw people that used the same idea but they only calculate the least divisor for a number and then divide it by its least divisor until reaching 1. I think we have the same complexity but in practice their solutions beat my solution...
•  » » 6 years ago, # ^ |   0 I don't understand your solution exactly. I solved it using Legendre's formula. (Although I don't know if it worked yet)
 » 6 years ago, # |   0 For problem C, I got a wrong answer on Pretest 3. I don't understand what was I missing. From the problem statement, I assumed that if N is odd, then print -1. Else do the usual queue and dequeue. Did I miss anything?
•  » » 6 years ago, # ^ |   0 n = 3 1 1 2 2 3
 » 6 years ago, # |   0 Start upsolving, please!
 » 6 years ago, # |   0 Can you please explain how these test cases are invalid for B5 1 1 1 1 16 1 1 1 1 3 4
•  » » 6 years ago, # ^ |   0 These are valid test cases. If you are talking about hacking, u need to put a newline at the end.
 » 6 years ago, # |   +10 No. of solutions passed : A B C D EPretests : 3591-2894-2383-1158-180Final : 3516-1986-1578-557-1374 out of 5 problems made for hacks! Great div2 contest!!
 » 6 years ago, # |   +3 Why cout why!!
 » 6 years ago, # |   +10 For problem D, I just replaced "cout<
•  » » 6 years ago, # ^ |   +1 mine passed in 1090sec with printf and scanf
•  » » 6 years ago, # ^ | ← Rev. 2 →   +6 always use scanf/printf when you have to input/output greater than 10^6 numbers. Learned the lesson in hard way.
•  » » 6 years ago, # ^ |   0 use C++11, and write cin.tie(nullptr); 11225307
•  » » 6 years ago, # ^ |   0 The problem is that you didn't use cin.tie(NULL). http://codeforces.com/contest/546/submission/11225554
•  » » » 6 years ago, # ^ |   0 I used it and still got TLE, but AC when using scanf printf. How is this fair? The problem should be rejudged.
 » 6 years ago, # | ← Rev. 2 →   0 it is really bad feeling when problem time limits because of cin cout :(((((((
•  » » 6 years ago, # ^ | ← Rev. 2 →   +2 Why? You should realize that the amount of input is huge, and it's going to take a while to read it using cin. Imo, it's only your fault. Using scanf and printf saves you a very big amount of time. I've learned it when I was upsolving. The solution, which used cin, got TL. But then I used scanf and the result was 140ms out of 1000. From that moment I'm using scanf and printf.UPD: The submissions are: 10834692 and 10834765
•  » » » 6 years ago, # ^ |   0 i already know it. but i hate cin cout from this day :D i just didn't think about it today
•  » » » 6 years ago, # ^ |   0 But cin, cout with sync_with_stdio and cin.tie(null) should get accepted too. Mine didn't. It is the setter's fault man.
 » 6 years ago, # |   0 cout...
 » 6 years ago, # | ← Rev. 2 →   0 Time limit on Div2 D were too strict. I got TLE when I submitted using cin,cout(using sync_with_stdio) in C++. And I got AC when I changed it to scanf,printf.This is not good Mr. Radewoosh. Same algorithm should get accepted inspite of input output specifications.
•  » » 6 years ago, # ^ |   +3 Strongly agree!
•  » » 6 years ago, # ^ |   0 You must also use cout << '\n', instead of cout << endl, it is significantly faster
•  » » » 6 years ago, # ^ |   0 It worked. Thanks!Learnt something new today. :)
•  » » 6 years ago, # ^ |   0 My solution passed in 608 ms using Java.Probably your algorithm can be improved.Here's my approach: http://codeforces.com/blog/entry/18031?#comment-229101
 » 6 years ago, # |   0 And the test case of D question was pathetic! scanf is getting accepted whereas cin doesn't!! Who is going to guess that in the contest! Shame!
•  » » 6 years ago, # ^ |   0 cin is getting accepted . You had to write ios_base::sync_with_stdio(0) ; cin.tie(0) ; to get AC .
•  » » » 6 years ago, # ^ |   0 I used that and even then I got TLE on test 3. I had to change to scanf and printf to get AC. This is not fair.
 » 6 years ago, # | ← Rev. 2 →   0 How much I wish , div-2 E test case 1 0 2 1were in the pretest. This test doesn't make sense anyway either. -_-
 » 6 years ago, # |   0 for problem C: #define stack queue
 » 6 years ago, # |   0 Output from diff command between WA and AC for the B problem :S.3333 -> 3333 3 30c30 < for(int i = 1; i <= 3333; ++i) { --- > for(int i = 1; i <= 33333; ++i) { 
 » 6 years ago, # |   0 In standing it is showing 3 solved problem but in contest I solved 4 problems and all 4 are accepted in the problem tab. P.S I have not resubmitted problem after contest.
•  » » 6 years ago, # ^ |   +6 You solved 3 problem I see, your problem D has a TLE .
 » 6 years ago, # |   0 how fair is it to award 0 to both , one who spent huge amount of time coding D correctly but forgets to put one line along with cin/cout & the one who had no idea about how to solve D & gave 0 time :P ? Disheartened :P
 » 6 years ago, # |   +3 People who use Python like me, don't care about cin or scanf. LOL!
•  » » 6 years ago, # ^ |   0 Lol, yes.I'm curious is it possible at all to solve it in Python?
 » 6 years ago, # |   0 When do we get the editorial?
•  » » 6 years ago, # ^ |   +3 already)
•  » » 6 years ago, # ^ |   +3 Click here to the editorial :)
 » 6 years ago, # | ← Rev. 2 →   0 problem D where is case? 1000000 5000000 1 5000000 1 . . .some AC code must be TLE
 » 6 years ago, # | ← Rev. 2 →   -9 got TLE on problem D just because I used endl not \n fuck this kind of problems -_-
 » 6 years ago, # |   +33 Guys, knowledge that cins/couts are very slow on big inputs/outputs is important on contests, and in this task this was one of the problems.
•  » » 6 years ago, # ^ |   0 I guess people do know that! Just that they do not benchmark which input is too large for cin and cout to not work! Most of the times cin inputs upto 1000000 run fine on codeforces! Anyways apart from that the problems were good!!
•  » » 6 years ago, # ^ |   0 I wonder, was this intended from the beginning. (Specifically, did Zlobober know about this?) This does not conform to the problem authors' guidelines that large tests should be included in pretests.It's ok that you test for large inputs in easier problems but I doubt that is appropriate for a 1500 mark problem.Don't get me wrong, I got AC. I am just curious.
 » 6 years ago, # |   0 Gain in rating!!
 » 6 years ago, # |   0 I got TLE in problem D, and I still don't understand Could anyone tell me what wrong in my code? http://codeforces.com/contest/546/submission/11221079
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 fast output :Dyour code 11229232
•  » » » 6 years ago, # ^ |   0 Thank you!
 » 6 years ago, # |   -9 Don't prepare any contests again, please :"DJust kidding :D , Good Luck and we are waiting for more contests from you. (Y)
 » 6 years ago, # | ← Rev. 2 →   0 I was solving problem E using max-flow and implemented edmond-karp algorithm ... and i think it's enough to pass the time-limit ... but im getting TLE :/ , and i don't understand what is the problem with my code?My submission : submissionany help will be appreciated :) !
 » 6 years ago, # |   0 Can someone please help and tell me what is wrong with my solution for 546D?I am getting TLE but I implemented exactly what the editorial says:http://codeforces.com/contest/546/submission/11232282
•  » » 6 years ago, # ^ |   0 many people has this problem.using ll inplace of int & cin or cout inplace of scanf & printf caused TLE. It's not good...
 » 6 years ago, # | ← Rev. 2 →   0 Where is the editorial ?
•  » » 6 years ago, # ^ | ← Rev. 2 →   +3
•  » » » 6 years ago, # ^ |   0 Thank you Sunnat
 » 6 years ago, # | ← Rev. 3 →   0 deleted
•  » » 6 years ago, # ^ |   +3 I think it should be 3. The numbers will be 1 2 5 6 7`
•  » » » 6 years ago, # ^ |   0 you're right , thank you.
 » 18 months ago, # |   +2 Very Good Contest! Thank you.