By RussianCodeCup, history, 22 months ago, translation, ,

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!

•
• +84
•

 » 22 months ago, # |   0 T-shirts?
•  » » 22 months ago, # ^ |   +5 Top 200
 » 22 months ago, # |   +149 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 :')
 » 22 months ago, # |   +3 What's the intended solution for E? priority_queue for getting subarrays and binary search + hash for merging sequences get TL.
•  » » 22 months ago, # ^ |   0 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}.
•  » » » 22 months ago, # ^ |   0 So, you don't fix the number of elements chosen from each array?
•  » » » » 22 months ago, # ^ |   0 No, you just have not to get position (0,y) or (x,0) at the end (to make both subsequences not empty).
•  » » 22 months ago, # ^ |   +3 I used min segment tree for creating subsequences and O(N * log(N)) suffix array to merge them and it passed.
•  » » 22 months ago, # ^ |   +1 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
•  » » 22 months ago, # ^ | ← Rev. 2 →   +8 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).
 » 22 months ago, # |   +18 Got WA#9 in problem E because missed the fact that both subsequences must be non-empty...
•  » » 22 months ago, # ^ |   0 Same. Quite atificial condition that we can get rid of just by adding following to the end:  if (maxElement(answer) < minElement(b)) { answer[k - 1] = minElement(b); } if (maxElement(answer) < minElement(a)) { answer[k - 1] = minElement(a); } 
 » 22 months ago, # |   0 Is the final round online?
•  » » 22 months ago, # ^ |   +18 Yes.
 » 22 months ago, # |   0 What is solution for D?
•  » » 22 months ago, # ^ |   0 Just count for every vertex v, number of pairs (u1
 » 22 months ago, # |   +3 How to use the checker for problem C on my computer ?
•  » » 22 months ago, # ^ |   0 You can try DFS, you just need hash table to check point exists or not and same for visited.
•  » » » 22 months ago, # ^ |   +3 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.
 » 22 months ago, # |   0 Will there be a place to submit solutions after the contest?
•  » » 22 months ago, # ^ | ← Rev. 2 →   0 0n25, already mentioned that Codeforces have internal error which not allow add problems to gym. They will be added after problem will be resolved.
 » 22 months ago, # |   +30 Sorry for long delay, contest has been added (finally!) to gyms: 2017 Russian Code Cup (RCC 17), Elimination Round
•  » » 22 months ago, # ^ |   +5 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.com/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?
•  » » » 22 months ago, # ^ |   0 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.