csacademy's blog

By csacademy, 7 years ago, In English

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.

Facebook event

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$

About the penalty system:

  • 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.

If you find any bugs please email us at [email protected]

Don't forget to like us on Facebook, VK and follow us on Twitter.

  • Vote: I like it
  • +117
  • Vote: I do not like it

»
7 years ago, # |
  Vote: I like it +30 Vote: I do not like it

Just a reminder, the round starts in 4 hours.

»
7 years ago, # |
Rev. 2   Vote: I like it -21 Vote: I do not like it

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

»
7 years ago, # |
  Vote: I like it +65 Vote: I do not like it

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.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +49 Vote: I do not like it

    It's easy. My solution gets AC because checker (or interactor) is incorrect.

    • »
      »
      »
      7 years ago, # ^ |
      Rev. 2   Vote: I like it +3 Vote: I do not like it

      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?

      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        There was a public question during the contest.

        anachor: Can the graph have multiple edges between same pair of nodes?

        Answer: no

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Will be the round still rated or rejudge expected? So many people found that it is incorrect, while I tried to find minimum number :/

  • »
    »
    7 years ago, # ^ |
      Vote: I like it +28 Vote: I do not like it

    The official editorial is ready! https://csacademy.com/contest/round-64/analysis/

    It seems they don't care about correctness.

»
7 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How can be solved the problem Eliminate Edge?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it -34 Vote: I do not like it
    #include <iostream>
    #include <cstdio>
    #include <cstdlib>
    #include <algorithm>
    #include <vector>
    #include <set>
    #include <map>
    #include <string>
    #include <cstring>
    #include <cmath>
    #include <complex>
    using namespace std;
    
    typedef long long ll;
    typedef pair<int, int> pii;
    #define mp make_pair
    
    const int N = 1 << 14;
    const int NN = N + 5;
    const int LOG = 15;
    vector<int> g[NN];
    int n, m, q;
    int par[NN][LOG];
    set<int> 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;
    }
    
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      This is not very helpful, actually we can see solutions in the csacademy, I was seeking for some tips.

  • »
    »
    7 years ago, # ^ |
    Rev. 2   Vote: I like it -30 Vote: I do not like it

    Here is what you should do!

    Spoiler
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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.

    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

»
7 years ago, # |
Rev. 3   Vote: I like it +8 Vote: I do not like it

My code for D didn't passed the examples during the contest and now it's is AC, amazing.

»
7 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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?

  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

  • »
    »
    7 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    I am surprised that no one asked if it is 500 "turns" or 500 "moves from both players" in the real time contest.

»
7 years ago, # |
  Vote: I like it +53 Vote: I do not like it

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.

»
7 years ago, # |
  Vote: I like it -10 Vote: I do not like it

nice contest