Hi, all!
The last possibility to get to the Elimination Round of Russian Code Cup this year is the Third Qualification Round, that will take place on Sunday, June 5, 16:00. Everyone who has not yet qualified is welcome to participate. Good luck, and see you at Russian Code Cup 2016!
Do you can check system faster? In the previous round we were waited about two minutes to know the results.
Yes, making judging faster would be highly appreciated.
Curiously, did they fix the bug with problemset presentation? Or when the contest starts, we will see 1st-qualifiication's problems again?
Can someone who is not Russian participate ?? if yes Link to the contest website please .
http://www.russiancodecup.ru/en/
The problems are quite interesting, but mail.ru reinvented the wheel developing their own system, which turned out to be the worst Online Judge ever, so expect huge bugs and slow testing during the contest. If you don't want a t-shirt from them, you'd better just wait for the problems to appear on the CF Gym.
How can I submit solutions ? I am not seeing any submit button option.
Same here
http://codeforces.net/blog/entry/45097?#comment-296431
:(
:(
Me too. I just created an account. Used log in with facebook option. Can't see submit button !
Is there some problem with the judge?
My code runs fine offline and on ideone, but gets runtime error on test case 1 in problem D. I asked the jury, and they confirmed that Case #1 is indeed sample case..
For D we needed this, right? http://e-maxx.ru/algo/tree_painting Found it 5 minutes before the end :/
lca + segment tree
Tried that. Got RE#16:D
I used sqrt-decomposition: new DFS+LCA every 400 queries.
Sorry if this is a dumb question but how did you check if some deleted edge was part of the path from u-v quickly?
Let vertex W = LCA(U, V) so X (a deleted vertex) is a part of the path U-V if and only if X is an ancestor of U or V, but not W (i.e. X is ancestor of exactly one of the path ends).
Thanks. I didn't think enough about it, this is quite easy to using dfs entry/exit times. Sorry.
I came up same solution but failed in coding this idea. Can you share with your code ?
Sure: code
As mentioned in the editorial, it is not necessary to delete the vertex explicitly — we may just assume that the corresponding edge has length 0. So, we may use a significantly simpler dfs — just calculating heights, without the tree rebuilding.
Code mk.II
Thx for advise. I used dsu for deleting edges:p
You need just this:
a) LCA
b) sum on path.
Both are standard.
I solved it with BIT on tree preorder. BIT holds current dept of the nodes.For update operation i updated corresponding segment of the BIT. And using LCA we can answer the other query.
What's wrong with this solution for D?
Keep a BIT on the DFS order for prefix sums from root to the node. For updates, subtract 1 from those which lie in the subtree of the current node, and to answer query use formula val[a] + val[b] - 2 * val[LCA(a, b)]. Only corner case is that both nodes are children of same node that has already been deleted where answer is 2. I kept getting WA on case 7.
There is no corner case. You just have to subtract 1 from everyone in the deleted node's subtree, including the node itself.
Shit, I was doing exactly that initially, but had some bug so rewrote large part of it, and messed that up and came up with new logic :/
To D I copy-pasted both LCA and HLD summing on paths. But what is funny is that I didn't copy it from my library but from problem E from RCC week ago :P (however I could as well copy-pasted from library, but second round was closer in directory tree than library :P).
Week ago 120 minutes weren't sufficient for me to get a result sufficient for qualification. Today 8 minutes were enough :P.
i think HLD is too hard solution to D You can use euler tour and segment tree with min and range substraction
code: http://pastebin.com/PApcfyiw
As long as I can copy-paste prewritten code I don't care whether it is complicated or not. What I care about is what I need to write specifically for that problem and here it was everything I needed: http://ideone.com/WGc7Uj Not too complicated, right?
The contest in Gym: 2016 Russian Code Cup (RCC 16), 3-й квалификационный раунд.
What's wrong with my solution? I used the same idea with the editorial, but instead of using a segment tree with lazy propagation, I used a trick with BIT that allow me to do range update, single node query (the same trick with this editorial, problem C div 1).
My solution
when will the editorial be out??
If you have not got it...LINK