Ready, steady, go!
It's time to find out who the top 50 participants to compete in the Final Round of Russian Code Cup 2017 are. We invite everyone qualified to take part in the Elimination Round this Sunday, May 14, 2017 at 13-00 Moscow Time. Round length is 2 hours. We invite you to russiancodecup.ru, and wish you good luck!
T-shirts?
Top 200
When you are one of the few people (3 to be exact) who solved F and you didn't get a T-shirt, because you forgot that in Russian Code Cup all problems are worth the same :')
What's the intended solution for E? priority_queue for getting subarrays and binary search + hash for merging sequences get TL.
There is a solution for n^2log. You check symbols one by one for nlogn and also keep in mind dp[x] = min{y, you could have finished known prefix with x-prefix of a and y-prefix of b}.
So, you don't fix the number of elements chosen from each array?
No, you just have not to get position (0,y) or (x,0) at the end (to make both subsequences not empty).
I used min segment tree for creating subsequences and O(N * log(N)) suffix array to merge them and it passed.
We just construe answer one by one and for each position in either array keep track of minimal position in the other array such that we can construe prefix of answer we have so far from corresponding prefixes of arrays
My solution is O(N2), but it didn't pass test 9 because of the corner case.
I greedily construct the answer one by one. I store the set of pairs of prefixes of a and b I used to construct the answer up till now. It has size O(N), because for each prefix of a we're only interested in the shortest prefix of b.
For the given pair of prefixes, we can take any element, after which there's enough elements to construct the rest. We need the smallest, so we can take RMQ over the next allowed elements in O(1) for each pair, and find minimum over the pairs.
Now, we need to advance the prefixes to reach the chosen element. To do that, we can just construct arrays of pointers to the next occurrence of this element in both arrays in O(N + M).
Got WA#9 in problem E because missed the fact that both subsequences must be non-empty...
Same. Quite atificial condition that we can get rid of just by adding following to the end:
Is the final round online?
Yes.
What is solution for D?
Just count for every vertex v, number of pairs (u1<u2) ui!=v, such that Ang(u1-v-u2) < 90. Then you just need to subtract 2 * binom_coef(n,3).
How to use the checker for problem C on my computer ?
You can try DFS, you just need hash table to check point exists or not and same for visited.
I mean how can I use the checker to check my solution on my computer. I don't see a main function in the checker, and I see a lot of "import ..." that I've never seen before.
Sorry for my inexperience with Java.
Will there be a place to submit solutions after the contest?
vovuh, already mentioned that Codeforces have internal error which not allow add problems to gym. They will be added after problem will be resolved.
Sorry for long delay, contest has been added (finally!) to gyms: 2017 Russian Code Cup (RCC 17), Elimination Round
Thank you!
To RussianCodeCup: I still don't know why I got TLE for E during the contest. My submission is #27152353 of http://codeforces.net/gym/101397/status/E, and it's much faster (2027ms) than genomes_iz_2modules.cpp (2870ms). Is it possible that my code works very slowly on RCC's server?
I got the answer from I_love_natalia. It seems memory allocator/deallocator are slow on RCC. I guess my solution was slow because I used too much vectors/priority_queues.