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.
:)
what's Gaussian primes?
Thank god, you didn't copy full article
Thanks so much for arranging the problems in expected order of difficulty.
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!
First time used Yandex's notepads to solve problem A :D
so quickly rating!
Thanks MikeMirzayanov!
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.
Contests are going in the direction of the ideal everyone love! Think more than Code! :)
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.
in the problem-B forming teams
is it not correct to just find the number of odd length cycles in graph described by 1..n??
It's incorrect
try test "5 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 -> 3
There 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)
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 --> 2013484
still can't figure out what's wrong..? :(
Please don't write in crippled English on purpose, it is very disturbing.
sorry...
now it is fixed...
It's also necessary to check if there are the same number of people on the two groups
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.
Yes. That is my mistake on that task. :(
sorry for this question(on this blog), but i am intrested why next round time is difference 08/18/2012 11:00AM
Why not? I'm very glad to see morning contest.
I love sleep :D
It's at Saturday :)
UPD: cout << (a+c-1)*(b+c-1)-c*(c-1) << endl;
You can see this submission 2013799.
Instead of exact formula, use simple loop (I'm think that this is simplest solution :))
example: http://codeforces.me/contest/216/submission/2007291 [w > 0 check is not necessary]
In condition reads: (2 ≤ a, b, c ≤ 1000).
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
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))
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!!
Function int cycle() doesn't always return a value. Maybe this is the bug you're looking for :)
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.
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++;
Still the same error.
You still miss the array bound check on lines 69 and 71.
You should rewrite not that while statements, but the above two while statements.
Thanks a lot!
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).
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 case
5 4
1 2
1 4
3 5
3 4
Maybe 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.
Thanks, that indeed is the error. (Edit: No, it's not!)
I was not keeping a proper track of connected components.
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);
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...
In Problem B,
This Test Case :
The expected ans is 0 but how will we make 3-3 pairs with this configuration ?