CodeChef invites you to participate in the September CookOff 2013 at http://www.codechef.com/COOK38.
Time: 22nd September 2013 (2130 hrs) to 23rd September 2013 (0000 hrs). (Indian Standard Time — +5:30 GMT) — Check your timezone.
Details: http://www.codechef.com/COOK38/
Registration: Just need to have a CodeChef user id to participate.
New users please register here
- Problem Setter : Roman Rubanenko
- Problem Tester and Editorialist: Utkarsh Lath
It promises to deliver on an interesting set of algorithmic problems with something for all.
The contest is open for all and those, who are interested, are requested to have a CodeChef userid, in order to participate.
I would like to say that we did our best to make statements as short as possible and thank the tester.
It's the first contest that all five problems are prepaired by myself and I am pretty excited :) I would like everybody to share your impressions after the contest.
I am satisfied. Not with my performance (too many WAs due to stress, I got 9th place in the last contest and tried hard to defend it), but the problems were quite good. I especially like BIGNUM.
BTW it's kind of an honor for you to have your initials at the start of every tasks's short name :D
Thanks a lot. I had to put my initials just because problem code should be unique :)
Why modulo was required in problem RRGAME?
It wasn't really required, since the answer is clearly no more than M. I just computed the answer as long long and printed it modulated :D
What is your approach on Tree problem ?
There is some known way how to calculate diameter. Find the most distant vertex from root (denote it v), and than the most distant from v. That distance will be the diameter.
Using this fact you can easily keep track on diameters. When you add vertex i, if it's parent is one of the most distant vertices from root (by the moment), then you say that the current result is increased by 1 and there is new most distant vertex from root. If not, than the answer can only be increased by the path from current most distant vertex (from root) and vertex i. You can calculate that path using LCA.
Thanks :)
Well done! Neither me, nor tester invented such a neat solution. Mine uses divide&conquer and tester's appraoch requires hldot :)
Can you write in short divide&conquer solution ?
Sure: We are to find the most distant vertex U for every Vertex V such that U<V. Let's call such vertex U F[V].
Let's fix a vertex R. We can count all answer for V if path from V to F[V] goes through R using a lot of data structues, even Segment Tree will do. So, let's take a look at our tree, choose R and update F[]. Then we delete vertex R and do the same for new connected components because if some path V->F[V] does not go through the vertex R it will lay in one of these connected components.
Feel free to ask for details, because my explanation does not seems pretty clear :)
thank you , nice solution :)
It was like a reverse engineering hack.
I think so :)
this is something very similar to what was used in the model solution of IOI 2011 Race. This divide and conquer approach on trees is a useful trick.