Submission #159928

#	Time	Username	Problem	Language	Result	Execution time	Memory
159928		rama_pang	Game (IOI14_game)	C++14	100 / 100	460 ms	16160 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;

/*  The ideal strategy is to keep saying no unless it is the last
    edge such that if we say no, then the graph becomes disconnected.

    Assume that the graph is partially filled, such that there are two
    components now. How to check if the guessed edge is the last edge?
    The number of possible edges between the two components are
    sizeA * sizeB. If cur_edge == sizeA * sizeB, then we can add an edge.

    Observe that the optimal strategy for the asker is to ask questions
    on two disjoint vertices. All already connected vertices are meaningless.
    By denying edges, we ensure that the asker would need all Q = N * (N - 1) / 2
    questions.

    Proof: assume that there are n disjoint components. Let A, B, C, D be sets
    with sizeA <= sizeB <= sizeC <= sizeD. What is the optimal strategy of
    minimum questions needed? There are a few cases:
    1.  sizeA * sizeB + sizeC * sizeD + (sizeA + sizeB) * (sizeC + sizeD) total questions.
        = sizeA * sizeB + sizeA * sizeC + sizeA * sizeD + sizeB * sizeC + sizeB * sizeD
          + sizeC * sizeD

    2.  sizeA * sizeB + (sizeA + sizeB) * sizeC + (sizeA + sizeB + sizeC) * sizeD
        = sizeA * sizeB + sizeA * sizeC + sizeA * sizeD + sizeB * sizeC + sizeB * sizeD
          + sizeC * sizeD

    for any permutation of A, B, C, and D. Thus we can see that for any strategy, if we
    give the asker an edge at the last possible edge between two currently disjoint 
    components, then asker would require the same number of questions.
    The total questions needed is: 1 * 1 + 2 * 1 + 3 * 1 + ... = N * (N - 1) / 2.
    So the strategy of waiting until last edge of two currently disjoint components is an
    optimal strategy.

    We can keep track of components' size with disjoint set data structure and countEdges
    with adjacency matrix.

*/

struct Disj {
    vector<int> p, sz;
    
    void init(int n) {
        p.resize(n);
        iota(p.begin(), p.end(), 0);
        sz.assign(n, 1);
    }

    int par(int n) {
        return p[n] == n ? n : p[n] = par(p[n]);
    }

    bool join(int a, int b) {
        a = par(a), b = par(b);
        if (a == b) return false;
        p[a] = b;
        sz[b] += sz[a];
        sz[a] = 0;
        return true;
    }

};

int N;
vector<vector<int>> cnt;
Disj dsu;

void initialize(int n) {
    N = n;
    cnt.assign(n, vector<int>(n, 0));
    dsu.init(n);
}

int hasEdge(int u, int v) {
    u = dsu.par(u), v = dsu.par(v);
    if (u > v) swap(u, v);
    if (++cnt[u][v] == dsu.sz[u] * dsu.sz[v]) {
        dsu.join(u, v);
        for (int i = 0; i < N; i++) cnt[min(v, i)][max(v, i)] += cnt[min(u, i)][max(u, i)];
        return 1;
    } else {
        return 0;
    }
}

• Subtask 1: 15 / 15
• Subtask 2: 27 / 27
• Subtask 3: 58 / 58