By csacademy, 9 months ago, ,

Hello, Codeforces!

Once again, we've reached a round number that is a power of 2 at csacademy.com. In order to properly celebrate this, Round #64 will consist of interactive problems only. If you are not familiar with this type of problems on our platform, please read this blogpost before the contest.

The round will take place on Wednesday, 10/January/2017 15:05 (UTC). This contest will be a Div1 + Div2, with 7 tasks of varying difficulty that need to be solved in 2 hours.

Recently, Facebook has reintroduced the possibility of recurring events. If you choose "Interested" here, you will be notified before each round we organise from now on.

#### Contest format:

• You will have to solve 7 tasks in 2 hours.
• There will be full feedback throughout the entire contest.
• Tasks will not have partial scoring, so you need to pass all test cases for a solution to count (ACM-ICPC-style).
• Tasks will have dynamic scores. According to the number of users that solve a problem the score will vary between 100 and 1000.
• Besides the score, each user will also get a penalty that is going to be used as a tie breaker.

#### Prizes

We're going to award the following prizes:

1. First place: 100$2. Second place: 50$

• Computed using the following formula: the minute of the last accepted solution + the penalty for each solved task. The penalty for a solved task is equal to log2 (no_of_submissions) * 5.
• Solutions that don't compile or don't pass the example test cases are ignored.
• Once you solve a task you can still resubmit. All the following solutions will be ignored for both the score and the penalty.

•
• +117
•

 » 9 months ago, # |   +30 Just a reminder, the round starts in 4 hours.
 » 9 months ago, # | ← Rev. 2 →   -21 The E problem looks very strongly like this CF problem and has got the same idea ... Second time in the CS the problem like in the 427 CF Round
 » 9 months ago, # |   +65 About problem C. I still cannot understand why solution like  int n; scanf("%d", &n); for (int i = 1; i < n; i++) { int x = 0; while(x == 0) { printf("Q %d %d\n", i, n); fflush(stdout); scanf("%d", &x); } } printf("A\n"); fflush(stdout); getc AC. If for example n = 3, isn't it enough to output just one query (for example 1 2)? This solution outputs at least two edges.
•  » » 9 months ago, # ^ |   +49 It's easy. My solution gets AC because checker (or interactor) is incorrect.
•  » » » 9 months ago, # ^ | ← Rev. 2 →   +3 I think you should consider case when graph is not simple. Then yours is correct I believe.UPD: sorry I dont know about it since I did not participate in the contest.But if multiple edges were allowed then solution seems correct right?
•  » » » » 9 months ago, # ^ |   0 There was a public question during the contest.anachor: Can the graph have multiple edges between same pair of nodes?Answer: no
•  » » » 9 months ago, # ^ |   +5 Will be the round still rated or rejudge expected? So many people found that it is incorrect, while I tried to find minimum number :/
•  » » » » 9 months ago, # ^ |   +4 Maybe semi-rated :)
•  » » 9 months ago, # ^ |   +28 The official editorial is ready! https://csacademy.com/contest/round-64/analysis/It seems they don't care about correctness.
 » 9 months ago, # |   0 How can be solved the problem Eliminate Edge?
•  » » 9 months ago, # ^ |   -34 #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; typedef pair pii; #define mp make_pair const int N = 1 << 14; const int NN = N + 5; const int LOG = 15; vector g[NN]; int n, m, q; int par[NN][LOG]; set edgesUp[NN]; int t[NN][2]; int T; int jmp[NN]; int h[N]; struct Node { int l, r; pii val; Node() : l(), r(), val() {} Node(int _l, int _r) : l(_l), r(_r), val(mp(N, _l)) {} }; Node tree[2 * N + 5]; void buildTree() { for (int i = 0; i < N; i++) tree[N + i] = Node(i, i + 1); for (int i = N - 1; i > 0; i--) tree[i] = Node(tree[2 * i].l, tree[2 * i + 1].r); } void setVal(int v, pii x) { v += N; tree[v].val = x; while(v > 1) { v >>= 1; tree[v].val = min(tree[2 * v].val, tree[2 * v + 1].val); } } pii getMin(int v, int l, int r) { if (l <= tree[v].l && tree[v].r <= r) return tree[v].val; if (l >= tree[v].r || tree[v].l >= r) return mp(N, -1); return min(getMin(2 * v, l, r), getMin(2 * v + 1, l, r)); } void dfs(int v) { edgesUp[v].insert(h[v]); t[v][0] = T++; for (int u : g[v]) { if (h[u] != -1) { if (h[u] < h[v] - 1) edgesUp[v].insert(h[u]); continue; } h[u] = h[v] + 1; par[u][0] = v; for (int k = 0; k < LOG - 1; k++) { int w = par[u][k]; if (w != -1) par[u][k + 1] = par[w][k]; } dfs(u); } t[v][1] = T; } int up(int v, int dh) { for (int k = LOG - 1; k >= 0; k--) { if (dh < (1 << k)) continue; dh -= 1 << k; v = par[v][k]; } return v; } int LCA(int v, int u) { if (h[v] > h[u]) swap(v, u); u = up(u, h[u] - h[v]); if (v == u) return v; for (int k = LOG - 1; k >= 0; k--) { if (par[v][k] != par[u][k]) { v = par[v][k]; u = par[u][k]; } } return par[v][0]; } int jump(int v) { return jmp[v] == v ? v : jmp[v] = jump(jmp[v]); } void precalc() { for (int v = 0; v < n; v++) { jmp[v] = v; h[v] = -1; for (int k = 0; k < LOG; k++) par[v][k] = -1; } h[0] = 0; dfs(0); buildTree(); for (int v = 0; v < n; v++) setVal(t[v][0], mp(*edgesUp[v].begin(), v)); } void query(int v, int u) { int w = LCA(v, u); while(h[v] > h[w]) { if (v != jmp[v]) { v = jump(v); continue; } pii s = getMin(1, t[v][0], t[v][1]); if (s.first >= h[v]) { jmp[v] = par[v][0]; continue; } v = s.second; u = up(v, h[v] - s.first); printf("0 %d %d\n", v + 1, u + 1); fflush(stdout); edgesUp[v].erase(edgesUp[v].begin()); setVal(t[v][0], mp(*edgesUp[v].begin(), v)); return; } swap(v, u); while(h[v] > h[w]) { if (v != jmp[v]) { v = jump(v); continue; } pii s = getMin(1, t[v][0], t[v][1]); if (s.first >= h[v]) { jmp[v] = par[v][0]; continue; } v = s.second; u = up(v, h[v] - s.first); printf("0 %d %d\n", v + 1, u + 1); fflush(stdout); edgesUp[v].erase(edgesUp[v].begin()); setVal(t[v][0], mp(*edgesUp[v].begin(), v)); return; } printf("1\n"); fflush(stdout); } int main() { scanf("%d%d%d", &n, &m, &q); while(m--) { int v, u; scanf("%d%d", &v, &u); v--;u--; g[v].push_back(u); g[u].push_back(v); } precalc(); while(q--) { int v, u; scanf("%d%d", &v, &u); v--;u--; query(v, u); } return 0; } 
•  » » » 9 months ago, # ^ |   +8 This is not very helpful, actually we can see solutions in the csacademy, I was seeking for some tips.
•  » » 9 months ago, # ^ | ← Rev. 2 →   -30 Here is what you should do! SpoilerFirst you should read three integers NN, MM and QQ. After that, read MM pairs of integers representing two ndoes that share an edge.The QQ queries follow, each consisting of two nodes vv and uu. After reading each query, you should print your answer:If there is a unique simple path between vv and uu print 11 If the path is not unique, print 00 followed by two integers representing the edge you remove You should answer a query before reading the next one.
•  » » 9 months ago, # ^ |   +8 Fix any spanning tree T. We'll never delete the edges from T. A T-edge is an edge in T, a T-path is a path in T. Make a few observations: The path from u to v is unique iff the T-path from u to v consist of bridges only. If a non-tree edges u - v is present it prevents the edges on the T-path from u to v in T from being bridges. Let's say that this edges 'covers' the edges in that path. An edge is a bridge iff it it not covered. A path consists of bridges iff none of it's edges are covered. Any edge covering an edge of a path is a valid output when that path is queried. We'll use heavy-light decomposition. Maintain the number of edges covering a T-edge and query the sum on the T-path from u to v to get whether any edge on that path is covered. (Operations: path sum, path add) We can then find any covered edge on the path (Operations: path sum, walk the segtree down to find a non-zero segtree-leaf) (Can be replaced by walking up the tree and something like path-compression from union-find.) To Find any edge that covers a given edge e maintain an unordered set in each segtree node that stores the edges that did a range-add update to that node. Treat these sets like lazy updates that do not propagate. If we walk from the segtree-node of e to the segtree-root, we'll encounter all edges covering e in exactly in of the sets, so we can just find a non-empty set and pick an edge to delete from the sets, range add  - 1 and print for the query. The total runtime is .A simpler solution can pass for some reason (My solution with lowest memory usage uses #pragma, but it pases without it). (You might need to submit it a few times, as you can get "Something bad happened. Please resubmit and contact us.")To check whether any edge on the T-path from a to b is covered, iterate over all edges u - v and check whether the T-paths from a to b and from u to v share an edge. (If yes, then u - v covers that edge and can be output.) This can be done with a bunch of (but constant number of) LCA queries.
•  » » » 9 months ago, # ^ |   0 Thanks! It was easier than I thought.I was trying to keep the induced bridge tree of the graph, and recalculating at every query, or after K queries but I couldn't make it work.I'll be glad to here other solutions for this problem (perhaps using some sqrt-technique) (without hld), since I find it very useful for a lot of problems.
 » 9 months ago, # | ← Rev. 3 →   +8 My code for D didn't passed the examples during the contest and now it's is AC, amazing.
 » 9 months ago, # | ← Rev. 2 →   0 Is the checker of Limited Moves correct?I keep receiving Wrong Answer on sample test 2(1024000) during the contest. Now, I test it in the archive and the log prints 499712, 1, 1, 1, ..., 1. Can't I win? or I misread something?Edit: After removing one of the assert, it got Accepted now. But, I remember that I have tried the same code without assert during the contest.(Annoyed by lots of WA, I kept adding assert to find out the problem) Then, why the verdict is showing Wrong Answer when it went to an assertion failed?
•  » » 9 months ago, # ^ |   0 You should stop after 500 prints I guess?As it is stated that your program must be terminated after the piles become 0 or there are already 500 interactions occured.
•  » » 9 months ago, # ^ |   -8 I am surprised that no one asked if it is 500 "turns" or 500 "moves from both players" in the real time contest.
•  » » » 9 months ago, # ^ |   0 Check the note of the third example.
 » 9 months ago, # |   +53 You definitely need the experienced testers for rounds. I'm sure that problem Limited Moves was given several times before this round, and it's not the first problem this situation happens with.
 » 9 months ago, # |   -10 nice contest