### Ripatti's blog

By Ripatti, 8 years ago, translation, ,

Hello everyone.

That is the 133th Codeforces round. Specially for the 2nd division. Contestants from the 1st division can solve the round out of competition.

Round is prepared by Ripatti , Gerald , Aksenov239 , Delinur and MikeMirzayanov .

The round will use dymanic scoring system. Problems will be ordered in random manner (see UPD1). If you want get more happiness from solving that round, please, read statements of all problems.

Good luck!

UPD1. Jury members discussed and have decided to rearrange problems in expected order of difficulty.

UPD2. Contest ended. Winners:
1. karensun522
2. stostap
3. sisterX
4. BiliBili
solved all 5 problems. Congratulations!

Editorial will be soon tommorow (I am very tired =_=, but now you can try to read russian editorial here).

UPD3. Editorial in English.

• +113

 » 8 years ago, # | ← Rev. 2 →   -21 :)
•  » » 8 years ago, # ^ |   -31 awesmmmm
•  » » 8 years ago, # ^ | ← Rev. 2 →   -19 what's Gaussian primes?
•  » » 8 years ago, # ^ | ← Rev. 2 →   +46 Thank god, you didn't copy full article
 » 8 years ago, # | ← Rev. 2 →   +36 Thanks so much for arranging the problems in expected order of difficulty.
 » 8 years ago, # |   +7 This contest started horribly for me (it took me a very long time to correctly deduce the formula for A, noob :P), but ended as my best placement ever (35th). I'm really happy, and I really enjoyed this entire competition, all the tasks were very interesting! Especially the Web one (even though the idea behind it is not that difficult, the formulation was very nice :D).Gratz everyone!
 » 8 years ago, # |   +3 First time used Yandex's notepads to solve problem A :D
 » 8 years ago, # |   +1 so quickly rating!
•  » » 8 years ago, # ^ |   0 Thanks MikeMirzayanov!
•  » » 8 years ago, # ^ |   +2 This time the tasks was not difficult to be writen in programing language but they were difficult to solve. For the first time i was thinking about A task 40 mins.
•  » » » 8 years ago, # ^ |   +7 Contests are going in the direction of the ideal everyone love! Think more than Code! :)
 » 8 years ago, # |   0 hard questions really! specially question A. I hope the editorial will be available soon. And really thanks to all of you who prepared this great contest.
 » 8 years ago, # |   +1 in the problem-B forming teamsis it not correct to just find the number of odd length cycles in graph described by 1..n??
•  » » 8 years ago, # ^ |   +1 It's incorrecttry test "5 0"
•  » » 8 years ago, # ^ | ← Rev. 4 →   0 it is correct (ofc with also removing one more player if the number of players left is odd), but look at the test which you failed:n = 4 3 -> 2 4 -> 2 4 -> 3There is one cycle here, and also this leaves us with an odd number of people left so we got to remove one more, rendering the final solution of 2. Your program outputs 0.My only conclusion could be that you implemented something wrongly. (since you passed the pretests I guess you already minded the case when the remaining number of players is odd)
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 yeah... i saw that... i went wrong trying to implement the graph in a different way..anyways i think i corrected this and resubmitted after the contest...link --> 2013484still can't figure out what's wrong..? :(
•  » » » » 8 years ago, # ^ |   +8 Please don't write in crippled English on purpose, it is very disturbing.
•  » » » » » 8 years ago, # ^ |   +3 sorry...now it is fixed...
•  » » 8 years ago, # ^ |   0 It's also necessary to check if there are the same number of people on the two groups
•  » » 8 years ago, # ^ |   0 After excluding exactly one element from each odd length cycle, you can get odd number of left (not excluded) students; in such case, we must exclude one more student.
•  » » » 8 years ago, # ^ |   0 Yes. That is my mistake on that task. :(
 » 8 years ago, # | ← Rev. 4 →   0 sorry for this question(on this blog), but i am intrested why next round time is difference 08/18/2012 11:00AM
•  » » 8 years ago, # ^ |   +3 Why not? I'm very glad to see morning contest.
•  » » » 8 years ago, # ^ |   +6 I love sleep :D
•  » » 8 years ago, # ^ |   0 It's at Saturday :)
 » 8 years ago, # | ← Rev. 7 →   +9 UPD: cout << (a+c-1)*(b+c-1)-c*(c-1) << endl;You can see this submission 2013799. some tips about problem A a=2 b=3 c=4 total=18 O O O O O O O O O O O O O O O O O O a=1 b=4 c=5 total=20 X:2 O:18 O O O O X O O O O O O O O O O X O O O O a=4 b=1 c=6 total=24 X:6 O:18 X X O O O O X O O O O O O O O O O X O O O O X X a=5 b=6 c=1 total=30 X:12 O:18 X X X X X X O O O O O O O O O O O O O O O O O O X X X X X X 
•  » » 8 years ago, # ^ |   0 Instead of exact formula, use simple loop (I'm think that this is simplest solution :))example: http://codeforces.com/contest/216/submission/2007291 [w > 0 check is not necessary]
•  » » 8 years ago, # ^ |   0 In condition reads: (2 ≤ a, b, c ≤ 1000).
•  » » 8 years ago, # ^ |   0 it seems all of the solutions for problem A are different with each others !! there are no two same formula for this problem in AC codes :D
•  » » » 8 years ago, # ^ | ← Rev. 2 →   +1 i found a lot in O(1) solution :D(B*C) + (B+C-1)*(A-1)if we suppose we have an rectangle B*C(here A is 1) for any extra of A, we are adding a line containing B hexagons and line containing C hexagons that one of them overlaps each other, so total answer will be : B*C + (B+C-1:(one edge of B + one edge of C — one overlapped)) * ( A-1 :(for any extra of A))
 » 8 years ago, # |   +1 Here is my submission to problem B: 2014265. It gives correct output on my system as well as ideone. But it fails on codeforces judge. Is there some problem with my code ? Comments are welcomed!!
•  » » 8 years ago, # ^ |   +3 Function int cycle() doesn't always return a value. Maybe this is the bug you're looking for :)
 » 8 years ago, # |   0 My submission for Problem D results in runtime error at test case 35. i have no idea why this is happening. I am using the same concept as many other people during the contest.
•  » » 8 years ago, # ^ |   0 Perhaps there are some bugs in 69th line and 71th line, and the bug may be "Array index out of bounds". You shoud rewrite like this.while(lpos < threads[left].size() && threads[left][lpos] < threads[i][0]) lpos++; while(rpos < threads[right].size() && threads[right][rpos] < threads[i][0]) rpos++;
•  » » » 8 years ago, # ^ |   0 Still the same error.
•  » » » » 8 years ago, # ^ |   +2 You still miss the array bound check on lines 69 and 71.
•  » » » » 8 years ago, # ^ |   +1 You should rewrite not that while statements, but the above two while statements.
•  » » » » » 8 years ago, # ^ |   0 Thanks a lot!
 » 8 years ago, # |   0 I am getting an incorrect answer for problem B on test case #18. I wish there were a way to get the test case (it's being truncated currently).
•  » » 8 years ago, # ^ | ← Rev. 2 →   0 Try using the information available, and you are very probably going to see your problem. Remember to change the value of M to the number of lines you have.You are probably partial visiting/coloring a component, check this case5 41 21 43 53 4Maybe it works for that case, but the idea is when you get to 4, if you didn't paint all the component, then 3 and 1 are visited, and it might think it's an odd cycle.
•  » » » 8 years ago, # ^ | ← Rev. 2 →   0 Thanks, that indeed is the error. (Edit: No, it's not!)
•  » » » » 8 years ago, # ^ |   +3 I was not keeping a proper track of connected components.
 » 8 years ago, # |   +1 I have found a very easy approach for problem A. The idea is to calculate like this if a>1 && b>1 && c>1 //it means its a hexagon: so ans = ans + 2*(a+b+c)-6 (calculating the tiles on perimeter)...else //i.e. a==1 || b==1 || c==1 it means its a square now... ans = ans + (a*b*c);
 » 8 years ago, # |   +4 for those who couldn't AC Problem D : i prefer learning function upper_bound(first_iterator, last_iterator, data); (in C/C++) (which uses binary_search and it's order is O(logN))i think CLEAN BruteForce algorithm gets AC too... but with this function, implementing is SO EASY, it does all the job...all you have to do is find four upper_bounds(two for each side of cell) and calculate distances see if they are equal...