Блог пользователя csacademy

Автор csacademy, 7 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +117
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +30 Проголосовать: не нравится

Just a reminder, the round starts in 4 hours.

»
7 лет назад, # |
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

»
7 лет назад, # |
  Проголосовать: нравится +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.

»
7 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

How can be solved the problem Eliminate Edge?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится -34 Проголосовать: не нравится
    #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 лет назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

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

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится -30 Проголосовать: не нравится

    Here is what you should do!

    Spoiler
  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится +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.

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится 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.

»
7 лет назад, # |
Rev. 3   Проголосовать: нравится +8 Проголосовать: не нравится

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

»
7 лет назад, # |
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?

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится 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.

  • »
    »
    7 лет назад, # ^ |
      Проголосовать: нравится -8 Проголосовать: не нравится

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

»
7 лет назад, # |
  Проголосовать: нравится +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.

»
7 лет назад, # |
  Проголосовать: нравится -10 Проголосовать: не нравится

nice contest