By RussianCodeCup, history, 6 years ago, translation,

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!

• +54

 » 6 years ago, # |   +40 Do you can check system faster? In the previous round we were waited about two minutes to know the results.
•  » » 6 years ago, # ^ |   +26 Yes, making judging faster would be highly appreciated.
 » 6 years ago, # |   +31 Curiously, did they fix the bug with problemset presentation? Or when the contest starts, we will see 1st-qualifiication's problems again?
 » 6 years ago, # |   +5 Can someone who is not Russian participate ?? if yes Link to the contest website please .
•  » » 6 years ago, # ^ |   +51 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.
 » 6 years ago, # |   +1 How can I submit solutions ? I am not seeing any submit button option.
•  » » 6 years ago, # ^ |   0 Same here
•  » » 6 years ago, # ^ |   +8
•  » » » 6 years ago, # ^ |   0 :(
•  » » 6 years ago, # ^ |   +8 Me too. I just created an account. Used log in with facebook option. Can't see submit button !
 » 6 years ago, # |   0 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..
 » 6 years ago, # |   -8 For D we needed this, right? http://e-maxx.ru/algo/tree_painting Found it 5 minutes before the end :/
•  » » 6 years ago, # ^ |   +5 lca + segment tree
•  » » » 6 years ago, # ^ |   0 Tried that. Got RE#16:D
•  » » 6 years ago, # ^ | ← Rev. 2 →   +19 I used sqrt-decomposition: new DFS+LCA every 400 queries.
•  » » » 6 years ago, # ^ | ← Rev. 2 →   +5 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?
•  » » » » 6 years ago, # ^ |   0 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).
•  » » » » » 6 years ago, # ^ |   0 Thanks. I didn't think enough about it, this is quite easy to using dfs entry/exit times. Sorry.
•  » » » 6 years ago, # ^ |   0 I came up same solution but failed in coding this idea. Can you share with your code ?
•  » » » » 6 years ago, # ^ |   0 Sure: code
•  » » » » 6 years ago, # ^ |   0 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
•  » » » » » 6 years ago, # ^ |   0 Thx for advise. I used dsu for deleting edges:p
•  » » 6 years ago, # ^ |   +10 You need just this: a) LCA b) sum on path.Both are standard.
•  » » 6 years ago, # ^ |   +5 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.
 » 6 years ago, # | ← Rev. 3 →   0 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. Code#include #include #include #include using namespace std; int n, maxn; vector start, depth, en, BIT, discover; vector > graph, T; void dfs(int node, int len, int par) { start[node] = int(discover.size()); discover.push_back(node); depth[node] = len+1; T[node][0] = par; for(vector::iterator it = graph[node].begin();it != graph[node].end();it++) dfs(*it, len+1, node); en[node] = int(discover.size())-1; } void upd(int idx, int v) { while(idx < int(BIT.size())) { BIT[idx] += v; idx += (idx&-idx); } } int qry(int idx) { int res = 0; while(idx > 0) { res += BIT[idx]; idx -= (idx&-idx); //cout << idx << "n"; } return res; } void init() { for(int j = 1;j <= maxn;j++) { for(int i = 0;i < n;i++) { if(T[i][j-1] != -1) { T[i][j] = T[T[i][j-1]][j-1]; //cout << i << " " << j << " " << T[i][j] << "n"; } } } } int LCA(int x, int y) { //cout << x << " " << y << "n"; if(depth[x] > depth[y]) swap(x, y); //cout << x << " " << y << "n"; for(int j = maxn;j >= 0;j--) { if(depth[y]-(1<= depth[x]) { //cout << y << "n"; y = T[y][j]; } } if(x == y) return x; for(int j = maxn;j >= 0;j--) { if(T[x][j] != T[y][j]) { x = T[x][j]; y = T[y][j]; } } return T[x][0]; } int main(void) { int u, q, type, a, b, v; scanf("%d", &n); graph.clear(); graph.resize(n); maxn = int(log2(n))+1; T.clear(); T.resize(n+2, vector(maxn+2, -1)); start.clear(); start.resize(n); depth.clear(); depth.resize(n); en.clear(); en.resize(n); discover.clear(); discover.push_back(-1); for(int i = 1;i < n;i++) { scanf("%d", &u); u--; graph[u].push_back(i); } dfs(0, 0, -1); BIT.clear(); BIT.resize(int(discover.size())+2); init(); for(int i = 0;i < n;i++) { if(start[i] == en[i]) continue; upd(start[i]+1, 1); upd(en[i]+1, -1); //cout << start[i] << " " << en[i] << "n"; } //for(int i = 0;i < n;i++) cout << qry(start[i]) << "n"; scanf("%d", &q); vector del(n+1); while(q--) { scanf("%d", &type); if(type == 1) { scanf("%d%d", &a, &b); a--; b--; if(a == b) { printf("0n"); continue; } //cout << start[a] << " " << start[b] << "n"; int res = qry(start[a])+qry(start[b]); //cout << res << " " << "n"; //cout << LCA(a, b) << "n"; res -= 2*qry(start[LCA(a, b)]); if(T[a][0] == T[b][0] && del[T[b][0]] && T[a][0] != -1) res += 2; printf("%dn", res); } else { scanf("%d", &v); v--; if(start[v] == en[v]) continue; upd(start[v]+1, -1); upd(en[v]+1, 1); del[v] = 1; } } } 
•  » » 6 years ago, # ^ | ← Rev. 2 →   +3 There is no corner case. You just have to subtract 1 from everyone in the deleted node's subtree, including the node itself.
•  » » » 6 years ago, # ^ |   0 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 :/
 » 6 years ago, # | ← Rev. 2 →   +33 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.
•  » » 6 years ago, # ^ | ← Rev. 3 →   0 i think HLD is too hard solution to D You can use euler tour and segment tree with min and range substraction
•  » » » 6 years ago, # ^ |   +18 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?
 » 6 years ago, # |   +37 The contest in Gym: 2016 Russian Code Cup (RCC 16), 3rd qualification round.
 » 6 years ago, # | ← Rev. 2 →   -15 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
 » 6 years ago, # |   0 when will the editorial be out??
•  » » 6 years ago, # ^ |   0 If you have not got it...LINK