Submission #673782

#	Time	Username	Problem	Language	Result	Execution time	Memory
673782		jophyyjh	Coins (IOI17_coins)	C++14	100 / 100	9 ms	1564 KiB

coins

/**
 * I'd like to layout how I've solved this classic problem, and possibly even give a
 * systematic way of handling communication problems.
 * 
 * Let's directly approach the whole problem. The actions of A and B can best be
 * viewed as functions. Indeed, given the same input, both of them should yield the
 * same output (if our algo is non-deterministic). Let the two functions be A(), B().
 * Let C be the set of (all) configurations of the board (|C|=2^64), and let P be the
 * set of all positions on the board (|P|=64). Informally, we have:
 *              A: (C x P) -> P,    B: C -> P,    B(c ⊕ A(c,p)) = p.
 * 
 * We now have 1 crucial fact: A is "kind of" injective. Namely, if a, b are in P and
 * c is any board configuration, then       A(c, a) != A(c, b).
 * (When the output of A() is given to B as input, B can only have a unique output.)
 * In other words, for any configuration c, A(c, p) are all distinct. Loosely
 * writing, A(c, P) = P (a set equals a set).
 * 
 * Let the neighbours of board c (N(c)) be the boards with #hamming_dist = 1. For
 * every neighbour c' of c, there exists a pos of the cursed coin p s.t.
 * c ⊕ A(c,p) = c'. (We've proven this!)
 * This fact is equivalent to the one below:
 *                      for every nc in N(c), B(nc) is distinct;
 *          OR          every c1, c2 with #hamming_dist = 2, B(c1) != B(c2).
 * The equivalence is established easily because when the "B(..)"s are distinct, we
 * can simply find the unique neighbour of c that is linked to a certain cursed pos.
 * 
 * It remains to find a construction. I first thought of summing the positions of the
 * 1s. However, we wanan flip a coin, but not necessarily flipping 0 to 1. This leads
 * us to xor~
 * Well, I assume that you already know that xor is commutative, associative, and any
 * integer's inverse is itself. For any board, we define its "value" to be the xor
 * sum of (the positions of) ones (0-indexed). Flipping the coin of a certain pos is
 * equivalent to adding its position's value to our xor sum, so we can always have
 * B(c) = #value_of_c.
 * So in fact, 64=2^6 is somehow useful because {0,1,2,3,...,63} is "closed" under
 * the xor operation. It can be proven that a construction exists iff the num of
 * cells is a power of 2, but that is beyond our interest at the moment. 3Blue1Brown
 * also did an amazing video on youtube: https://www.youtube.com/watch?v=wTJI_WuZSwE.
 * 
 * Num of Flips: 1
 * Implementation 1             (Full solution, construction, maths)
*/

#include <bits/stdc++.h>
#include "coins.h"

typedef std::vector<int>    vec;


vec coin_flips(vec board, int cursed) {
    int xor_sum = cursed;
    for (int k = 0; k < 64; k++) {
        if (board[k])
            xor_sum ^= k;
    }
    return vec{xor_sum};
}

int find_coin(vec board) {
    int xor_sum = 0;
    for (int k = 0; k < 64; k++) {
        if (board[k])
            xor_sum ^= k;
    }
    return xor_sum;
}

• Subtask 1: 10 / 10
• Subtask 2: 15 / 15
• Subtask 3: 10 / 10
• Subtask 4: 15 / 15
• Subtask 5: 50 / 50