### PraveenDhinwa's blog

By PraveenDhinwa, 5 years ago, ,

Hi everyone,

Codeforces round #251 for division 2 participants will start at June 4, Wednesday, 19:30 MSK (usual time). Traditionally we invite Div.1 participants to take part out of the competition.

The round was prepared by me (praveen123). This is my first codeforces round. I have tried my best to make the problem statements as clear as possible. I hope that everyone will enjoy the round.

Special thanks to Gerald(Gerald), for his extensive help in problem ideas verification, problem testing, without his help the contest would not have seen the day. English translation is done by me with a lot of help from Gerald Agapov(Gerald). Problems are translated in Russian by Maria Belova(Delinur).

Many thanks to Pratik Moona(pratikmoona), Varun Nitish(JuanMata) for providing their help in testing of round. Their help is greatly appreciated :)

Many thanks to Devendra Agrawal(devuy11243)Utkarsh Lath(utkarshl) to helping me in verifying the ideas of problem statements.

Many thanks to Mike Mirzayanov(MikeMirzayanov) for creating this wonderful platform :)

The contest problems are dedicated to my dear friend Devu (devuy11243), He once proposed problem titled "Churu, the thief". Churu is my nick-name. So it is now time to take some revenge in a funny way :P

Score distribution for the contest is standard: 500-1000-1500-2000-2500.

I have a good news for you too. Tutorial of the contest will be available as soon as the contest ends :).

I wish all the participants good luck, high rating and lot of hacks :) Don't miss the round.

UPD Thank you everyone for participating. I hope that you have enjoyed the round, Thank you all !!

Editorial

• +210

 » 5 years ago, # | ← Rev. 3 →   +5 @praveen123 I guess you are the first Indian Problem Setter (that too from my college :) ) on Codeforces (at least from the time I have joined Codeforces) .. Congrats .. Will definitely participate !!
 » 5 years ago, # |   +17 LOL score distribution's available from the beginning :D
•  » » 5 years ago, # ^ |   +9 And editorial already written? I'm impressed!
•  » » 5 years ago, # ^ | ← Rev. 2 →   +5 The coders were fast too. %50 of submissions was in first 25 minutes.
 » 5 years ago, # |   +12 AFAIR, devuy11243 named it "Dhinwa Chor" not "Churu, the thief", which was later renamed "Dorsey Thief" before the contest. For Non-Hindi speaker, Chor == Thief
•  » » 5 years ago, # ^ |   0 Yes, you are right :) I forgot the actual wordings, I only remembered thief :P
•  » » » 5 years ago, # ^ |   +18 I was about to change before the contest churu. Please do not take revenge .. Please :D :D
•  » » » » 5 years ago, # ^ | ← Rev. 8 →   +2 You have already verified the problem statements, So it is similar to axe one's own feet :P
•  » » » » » 5 years ago, # ^ |   +6 BTW, here is another problem dedicated to devuy11243. Devi ji, you are so famous.
 » 5 years ago, # |   +4 Congrats praveen123 will surely participate :)
 » 5 years ago, # |   +2 I hope this round problems can be described more clearly. It is important for me to start the contest and I am raring to go. :)
 » 5 years ago, # |   +3 is devuy11243 the author (or tester) of the problem Devu Vs Police? i really liked that problem! :)
•  » » 5 years ago, # ^ |   0 He was the author of the problem :)
•  » » 5 years ago, # ^ |   +3 Thanks :D
•  » » » 5 years ago, # ^ |   0 actually, thank you for creating such an awesome problem. it was by far the hardest i have ever worked to solve a problem since i started competing in online contests. and as u can see from my AC solution, i used CRT and ETF (two concepts i barely knew, and had no pre-written code for), along with a few small "tricks", to solve it. was that the intended solution?
•  » » » » 5 years ago, # ^ |   0 In my opinion, CRT is unnecessary — you need only fast modular exponentation and ETF.Of course (from Euler's theorem) we know that . So, for example, φ(10) = 4 and then In your task you can see that (if n ≥ 2) So you need to do only the following things: compute k = φ(n). find (use the modular exponentation); let's say the result is e. find (again modular exponentation).
•  » » » » » 5 years ago, # ^ |   0 But it can happen that (a, n) ≠ 1 and so, your idea will not always work.My idea was to factorize n and do some stuff which I forgot(and don't understand from my code) :P
•  » » » » » » 5 years ago, # ^ |   +5 Oops, true. I didn't notice the lack of the assumption :DHowever, I'm almost sure the following trick works: we can write a = xy, where x contains all the prime divisors which are both in a and n (for example, if a = 2734527 and n = 233911, then x = 2734 and y = 527). We do the same for n: n = zt (in the example above, z = 2339, t = 11). Result is then We can compute second factor as I mentioned previously (just because (y, n) = 1). What about the first one? If the exponent (b·cd) is quite small (less than or just 30), we can brute-force it. In the opposite case note xb·cd is surely divisible by z (compare the exponents). Then we just have to compute , which is doable using my previous post ((x, t) = 1) and then just multiply our result by z. I hope it's understandable (and moreover, that it's true) ;)
 » 5 years ago, # |   +4 Everything is happening quickly of this round.. :) quick announcement, quick score distribution & quick editorial too... :) hope, will enjoy this contest... :)
•  » » 5 years ago, # ^ |   +2 Hope Quick System Test :D
•  » » » 5 years ago, # ^ |   +12 And hope quick updated rating too... :D
•  » » » » 5 years ago, # ^ |   +2 And hope quick AC too :) (for all participants)
•  » » » » 5 years ago, # ^ |   +3 updating rates is too slow :D :D
 » 5 years ago, # |   +2 I wish all the participants ..... lot of hacks :) I guess the problems are going to be hackable :D
•  » » 5 years ago, # ^ |   0 Actually all problems are hackable if pretest cases are weak... :)
•  » » » 5 years ago, # ^ |   +1 That's what I meant.
•  » » 5 years ago, # ^ |   +1 I can't wait to hack many solutions!
•  » » » 5 years ago, # ^ |   +3 I could hack 9 solutions for the first time. So nice contest!
•  » » 5 years ago, # ^ |   0 REALLY A LOT OF HACKS.
 » 5 years ago, # | ← Rev. 2 →   +2 The prose in these announcements is getting better over time. Wish everybody high scores. Happy coding!
 » 5 years ago, # | ← Rev. 3 →   +10 Just look these unrated registrants I really try to be dewy-eyed and think all the 400 unrated users that register for every Div2 only contest are real...
•  » » 5 years ago, # ^ |   0 Maybe it's kinda good because it slows rating inflation.
 » 5 years ago, # |   +5 If I have registered but I can't participate any more will it affect my rating? Sorry for newbie question...
•  » » 5 years ago, # ^ |   0 No, it wont.
•  » » 5 years ago, # ^ |   0 Only if you have no any submission behavior.
•  » » 5 years ago, # ^ |   +1 Your rating wont be affected until you make a submission.
•  » » 5 years ago, # ^ |   +6 If you want to be 100% sure, you can find your nickname in the list of registrants (it may be easier if you sort the list by rating) and then use the red button to unregister ;)
•  » » » 5 years ago, # ^ |   +3 Much easier — to click "Friends"! :)
•  » » 5 years ago, # ^ |   0 no
 » 5 years ago, # |   +9 an unrated user named smart_lovely_JuanMata is currently leading the Standings. seems like a fake account to me, but i can't say for sure now.
•  » » 5 years ago, # ^ |   0 I don't think so. Just look at rationality. It's his second CF round, however he leads there.
•  » » » 5 years ago, # ^ |   +10 my reason for making that assumption is not because he is unrated and leading the round. it is because of handle alone!
•  » » » » 5 years ago, # ^ |   +4 Nice to meet you, young boy~~~~
•  » » » » 5 years ago, # ^ |   0 Oh, now i see. Sorry :)
 » 5 years ago, # |   +3 As the round closes, I'd like to commend the round writers. Even though the contest was slightly easier (I, who usually gets only one problem, solved 3), I loved the problems and how each and every one of them were easy sounding but had something to figure out.Thanks for my favorite problems so far!
 » 5 years ago, # |   0 Did anyone who solved D used Binary Search?
•  » » 5 years ago, # ^ |   +3 I solved using Ternary Search.
•  » » 5 years ago, # ^ | ← Rev. 4 →   0 EDIT: Previous posting is wrong.
•  » » 5 years ago, # ^ |   +1 I solved D using Binary Search (using lower_bound and upper_bound from STL, actually).
•  » » » 5 years ago, # ^ |   0 I tried to solve with the same method but got WA on test 8.Whaat wrong with that test?
•  » » » » 5 years ago, # ^ |   0 Just checking all the possible number x, such that making all elements in a is not less than x, while all elements in b is not larger than x.Here all the possible numbers are the elements in both a[] and b[].
 » 5 years ago, # |   0 Will DmitriyH count how many hacks were in this round?)
 » 5 years ago, # |   0 Really nice contest :) I think problem D should have had a 32-bit integer overflow warning...
 » 5 years ago, # |   0 Any ideas for problem E?
•  » » 5 years ago, # ^ | ← Rev. 3 →   +8 I used inclusion-exclusion principle. And it passes the sample tests :DI count number of bad distributions, like distributions that can be divided by 5, 7 etc. Then using IE principle I exclude 5*7 divisors etc. This works in O(Q*(2^7)). the number 7 is due to the fact that 2*3*5*7*11*13*17 is bigger than 10^5.But I was not able to submit in time :|
•  » » 5 years ago, # ^ | ← Rev. 2 →   +9 There is at most ~7 prime numbers which divides n. Tip : Solution is q * (2 ^ 7).EDIT: i did not saw Dixtosa.
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 I think about the following solution but I got WA2. First of all, lets calculate how many solutions has quality n = a1 + ... + af , where ai >  = 1. We can do in C(n - 1, f - 1) ways(this is well-known problem). Then if gcd(ai) = x > 1 then x|n. So try to iterate all dividers of n, and for all such x, subtract from our answer C(x - 1, f - 1). Is it correct?
•  » » 5 years ago, # ^ |   0 Quite simple if you use Möbius inversion formula. There are much harder problems on SPOJ, as PGCD, and so on....
 » 5 years ago, # |   +1 I think that many submissions to Problem B will fail the system test because of integer overflow, both a[] and x should be long long.
•  » » 5 years ago, # ^ |   +2 not both, only answer can be long long. We can use a[i] * 1ll * x
•  » » 5 years ago, # ^ |   0 at least one of them should be long long, or both int but using ans += a[i] * 1LL * x;
 » 5 years ago, # |   +4 superround, thanks for authors!
 » 5 years ago, # |   0 System Tests. Please
•  » » 5 years ago, # ^ |   0 It's not as fast as the other contests!
 » 5 years ago, # |   0 Быстрый разбор-это очень хорошо.
 » 5 years ago, # |   0 in this round 251 div2...i submitted the problem Devu the dumb guy and got all pretests passed....nd got score of 680....but in few minutes i saw the status of my submitted problem as hacked....finally my score dropped to -1.....what it means...??how to prevent it>> ????
•  » » 5 years ago, # ^ |   0 It means someone else from your room who also passed pretests and after locking his/her solution , the person went through your solution and maybe found some mistakes in your code. He then made your code go through his custom test , which your solution failed . :( To avoid this situation make sure your implementation is absolutely correct or no one is able to guess the mistake in your solution.
•  » » » 5 years ago, # ^ |   0 how to view the code of a person who s n my room?? is it posible to read the code wen the contest is goin>??
•  » » » » 5 years ago, # ^ | ← Rev. 2 →   0 Yes , you can view the code of other person in your room after passing pretests and locking your solution . Keep in mind that you can't alter your solution after locking.
•  » » » » » 5 years ago, # ^ |   0 Keep in mind that you can alter your solution after locking. but you can't alter your solution after locking!
 » 5 years ago, # |   +1 good tricky contest ^_^
 » 5 years ago, # |   0 Hey where is the editorial? It is disappeared!
•  » » 5 years ago, # ^ |   0 I guess the formulae were not displaying correctly (the LaTex part), so they are editing the editorial :)
•  » » » 5 years ago, # ^ |   0 I think it should be accessible now :)
 » 5 years ago, # |   0 I really wish people would stop using the anti-quicksort test. I'll agree it's a valid hack, but it's something that shouldn't disqualify a correct algorithmic solution...
 » 5 years ago, # | ← Rev. 2 →   +9 the Best and Most Secure way for problem B: #define int long long =))
•  » » 5 years ago, # ^ |   +4 long long main()Would that work? :D
•  » » » 5 years ago, # ^ | ← Rev. 2 →   +3 GNU C++ : main ( ) MS C++: void main ( ) Nothing is impossible!
•  » » » 5 years ago, # ^ |   +10 #undef int int main() { #define int long long :D
•  » » 5 years ago, # ^ |   +8 i tried to hack ur solution 6789141 in yesterday's Testing Round because i saw u using int everywhere. TROLL level long long! :D
 » 5 years ago, # |   +11 everyone in system test
•  » » 5 years ago, # ^ |   +5 copycat! :D
•  » » 5 years ago, # ^ |   +4 This is how I solve hard problems :D
 » 5 years ago, # |   +2 user "rationality" alone has +18 hacks!! o.O
 » 5 years ago, # |   +1 Hello, I'd like to bring attention to the following code, it's for problem B with complexity of O(NlogN). But it got TLE, I can't find an explanation for this behaviour. My code template is rather large but it is ok, you can rest assure about that since I'm using this template for last 10+ contests. Only getInput() and solveCase() methods are relevant here.http://codeforces.com/contest/439/submission/6799372
•  » » 5 years ago, # ^ |   0 Even qwerty787788 got TLE with more or less same code as mine, also on the same test case. Here is submission link:http://codeforces.com/contest/439/submission/6797936
•  » » » 5 years ago, # ^ |   0 i also got TLE for the same................. need to use objects rather than primitive now.............. http://codeforces.com/contest/439/submission/6809882
•  » » 5 years ago, # ^ |   +16 It's become popular to use an anti-quicksort test to break Java solutions. Arrays.sort() uses a variant on quick-sort that has a worst case of O(N^2) for (very) unlikely testcases. However, if they can choose them, they can make your program time-out due to sorting cost.Use ArrayList and Collections.sort() if you want to avoid it, or just use Integer[] instead of int[].
•  » » » 5 years ago, # ^ |   0 I got the same problem! I would really like to see author commenting on this — if he crafted an anti-quicksort on purpose — I think it's a disgrace! Those kind of conducts should be prohibited!
•  » » » » 5 years ago, # ^ |   0 I agree, it's quite frustrating to always remember to consider that someone may try that, but unfortunately it's a "valid" hack, so I doubt they'll fix it. Someone hacked my B and D, and I was required to resubmit both at the ~1:50 mark.
•  » » » » » 5 years ago, # ^ |   +1 Can you show me this popular anti-quicksort test?
•  » » » » » » 5 years ago, # ^ |   +1 sorry, i finded it.... http://codeforces.ru/blog/entry/2298
•  » » » 5 years ago, # ^ |   0 Oh, I didn't know that. I'll switch to object rather than using primitive data type.
•  » » » » 5 years ago, # ^ |   0 Switching to objects sucks because under normal circumstances Arrays.sort() works substantially faster on primitives.
 » 5 years ago, # |   +3 So many solutions of Problem C failed in system test. So spectacular...
 » 5 years ago, # | ← Rev. 2 →   0 look!! 01:57 星期四 2014年6月5日, I'm so sleepy!!, in the morning,i should to learn c++ class~~~,but now,i'm waiting~~~
 » 5 years ago, # |   0 How can I calculate my new rating?!
•  » » 5 years ago, # ^ |   +4 do nothing wait system
 » 5 years ago, # |   +3 Problem B was really easier than problem A! Pretest 3 was ... I regret why i didn't go to solve B before A.
 » 5 years ago, # |   0 Why there are so many hacks on problem B? I can't find any tricky test cases :(
•  » » 5 years ago, # ^ |   0 If you store x in int and array a in int, then despite storing answer in long long, your solution will get overflowed.
•  » » 5 years ago, # ^ |   0 int overflow.
•  » » 5 years ago, # ^ |   +1
 » 5 years ago, # |   0 Can someone tell me, is there any test in task C with K = 0? I found it, when i had got only five minutes left before the end of the contest, so i lost lots of points...
•  » » 5 years ago, # ^ |   0 No, but p could be zero.
•  » » » 5 years ago, # ^ |   +3 Oh, it's very sad... OK, thank you!
 » 5 years ago, # |   0 who can tell me why my solution of C my solution wa on 58 test
•  » » 5 years ago, # ^ |   0 I have the same WA on test 58 (my solution is similar to yours). No idea, yet...
•  » » » 5 years ago, # ^ |   +1 i've just found it XD. if p=0, i guss ur program will output a zero in the last line. u may try this data 10 10 0 1 3 5 7 9 11 13 15 17 19
•  » » » » 5 years ago, # ^ |   0 winoros, thank you.
•  » » » » 5 years ago, # ^ |   0 thanks for this example!
 » 5 years ago, # |   +2 I will forget int in C++ and I will never use it again. By the way, Do you know what data type is int in C++, because I only know long long data type.
 » 5 years ago, # |   +4 Problem C rocks!!
 » 5 years ago, # |   +1 The most interesting contest I have ever solved! Amazing! I was really enjoying while solving problem C! Really unexpected idea! thanks authors for the contest!
•  » » 5 years ago, # ^ |   +3 Agree about the most interesting contest. I've never been so interested during systests (especially about C). But I can't imagine pleasure while solving C, it was so annoying for me.
 » 5 years ago, # |   0 Damn . I failed system test on problem C , just because I forgot to comment one line while Debugging .It was surprising to find that it even passed the pretests with that terrible mistake .It is so frustrating to see that the after that commenting that line , the code passed all the system test cases. I just missed an oppurtunity to go blue .... :(
•  » » 5 years ago, # ^ |   +3 But you are blue :)
 » 5 years ago, # |   0 Can anybody tell me what is wrong with my C solution. The judge says "wrong output format Extra information in the output file" in test case #58 and I can't see any problem with my solution. Thanks in advance.
•  » » 5 years ago, # ^ |   0 I had the same problem.check your program when p = 0
•  » » 5 years ago, # ^ |   0 the same problem (wrong format, extra output).. :(
 » 5 years ago, # |   0 What the ... Wrong answer on test 71 A corner point that I thought about that but got confused with parameteres while coding A line was needed to accept C 6809803 -> 6811297 What a stupid mistake :( Someone helps me. I'm really sad :'(
•  » » 5 years ago, # ^ |   +1 Don't get upset man, sometimes we all make mistakes .
•  » » » 5 years ago, # ^ |   +3 Thank you man! Both for your consolation and good problems ;) I hope reduce these stupid mistakes
•  » » 5 years ago, # ^ |   +1 Don't worry brother .. I too made the dumbest mistake .. Forgot to comment one line while debugging .. Surprisingly it passed the pretests .. but failed system test .. 6809400mistake : Line 97 .. comment But later after commenting that line it passed the system tests.. 6811176
•  » » 5 years ago, # ^ |   0 Same thing happened with me @algor , :( 6805185 -> 6813772 It's not new things for me, same thing happened with me many times in codeforces.**Its not a reason to be sad. Its just a warning for improvement on coding.** I think i'm a stupid coder :(
 » 5 years ago, # |   0 problem Chttp://codeforces.com/contest/439/submission/6807018 plz explain why my code gives wrong ans . thnaks
•  » » 5 years ago, # ^ |   0 You fail if there are no even numbers enough to fill some arrays, like in this case: 5 5 2 1 3 5 7 9
 » 5 years ago, # |   0 I locked my problem from dashboard and then went to standings to hack solution. But I was able to open hack window for my submitted code. When I double clicked on someone else's solution then it just showed pretest passed,etc.. Clicking on submission number didnt open the hack window. What was I doing wrong?
•  » » 5 years ago, # ^ |   +2 You should go to room instead of standings
•  » » » 5 years ago, # ^ |   0 Thanks
 » 5 years ago, # | ← Rev. 2 →   0 Failed problem D because of implicit transformation of an integer and failed C because of i failed to copy paste some validation made on the even numbers to the odd numbers... Missed the spot 45 because of two errors...Anyways, congratulations because of the contest, well made, i understood without any trouble all statements.
 » 5 years ago, # |   0 There's an hour passed but there is no rating updates! Why..?
 » 5 years ago, # | ← Rev. 2 →   0 I was just going through different submissions of problem C, and came across this solution 6802980 which shows wrong answer for test case 44, but the output seems correct. Could you kindly tell how is that answer wrong?Got it Didnt see the number of elements :P
 » 5 years ago, # |   +1 my best contest ever, that's actually the first time i solve problem D in a contest really hats off to problem setters!.i still wonders why a lot of participants failed in problem C?
•  » » 5 years ago, # ^ |   +1 Lots of people forgot to add some conditions, in my case, i forgot a lot of things, such as considering all odd numbers or all even numbers, etc... I failed because of failing one simple validation... So i think many people got the C wrong because of not thinking all possible cases that could be evaluated with.Congratulations on your result :)
•  » » » 5 years ago, # ^ |   0 yes i think the hard part in the problem was about considering casesthanks a lot :)
 » 5 years ago, # |   +3 For problem C, I am getting following output on my machine for test #3YES2 7 5 2 1 2 1 3But the judge is showing NO as output. Can anyone please help me to figure out where is the problem? Submision ID : 6809178. Thanks!
•  » » 5 years ago, # ^ |   0 judge is showing answer "YES", but you are showing answer "NO".
•  » » » 5 years ago, # ^ |   0 Sorry I meant the same. On my machine I am getting the output I mentioned in my earlier comment on test 3 but don't know why my answer is shown as NO.
•  » » 5 years ago, # ^ |   0 The Answer is NO too in my Machine what's the compiler you use
•  » » » 5 years ago, # ^ |   0 g++ (from mac terminal).
 » 5 years ago, # | ← Rev. 3 →   0 Rating is updated... :) seems your wish has suited me a lot... :) thanks for nice contest... :)
 » 5 years ago, # |   0 Congratulations for the round! I loved the problems because they were more idea-based than algorithm-based. Also, I liked E because I don't find as many PINEX problems as I want to usually, so thank you!
 » 5 years ago, # |   0 Thanks for awesome contest
 » 5 years ago, # |   +15 Finally , I reached DIV1 :D
 » 5 years ago, # | ← Rev. 2 →   0 Problem C : I Got "Runtime error on test 60" :( in this 6806998 . What is special about it? :'(
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 Check this case2 1 0 2 1
•  » » 5 years ago, # ^ |   +4 The problem is at one of the for loops around line 40.You calculate j % p, and this crushed when p = 0. Test 60 also has p = 0.
•  » » » 5 years ago, # ^ | ← Rev. 2 →   0 Silly me :( Thanks HIdenoriS:)
•  » » » » 5 years ago, # ^ |   0 No problem :)
•  » » 5 years ago, # ^ | ← Rev. 2 →   0 there is a bug in your code if (Ge[p-1].size()==0) { cout<<"NO\n"; return 0; } p can be 0
•  » » » 5 years ago, # ^ |   +3 Thanks :)
 » 5 years ago, # |   +3 I've got RTE in problem C (test 20). I used queue with operations push and pop. After the contest, I changed queue to vector, only operation push_back, and I've got AC. Why RTE? Link to my submission: http://codeforces.com/contest/439/submission/6805127
•  » » 5 years ago, # ^ |   +3 I modified your solution, and got AC.Basically the size of queue changes, so you should keep the original size as a variable.
•  » » » 5 years ago, # ^ |   +3 Thanks! I forgot that I really had to keep the original size.
 » 5 years ago, # |   0 Enjoyed the contest. Specially problem C though failed on test 24.Thank you. :)
 » 5 years ago, # | ← Rev. 2 →   -6 Wth for the second problem Devu and dumb guy,judge didn't accepted my solution even for the first preset and now when i am running test cases of other participants and the test cases which are used by problem setter all are giving right output.Can i know why?Here's my solution http://ideone.com/coqCrK
 » 5 years ago, # |   0 Can one look at my submission and see what's different from praveen123's editorial? My submission: 6799361 Praveen's submission: 6814439both look functionally equivalent to me but, I got WA
•  » » 5 years ago, # ^ |   0 Never mind. I was reading in x as an int.
 » 5 years ago, # |   0 When I submit the solution: the status is "in queue", waste many time. Can you fix it :D
•  » » 5 years ago, # ^ | ← Rev. 3 →   0 How can i delet this cm? :|
 » 5 years ago, # |   +12 Where is DmitriyH statistics? I missed them :)