Lately, while solving a problem list I came across IOI 2017 Coins (don't worry, it's a practice problem, so it shouldn't be a problem to "spoil" the statement). I highly recommend you giving the problem a shot before finishing reading the blog, but if you already know it (after all it's a relatively well-known problem) or don't care, please continue reading!
Statement
Alice will be given an 8x8 checkerboard where every cell has a coin that is either heads or tails. She will also be given the index of a cell $$$c$$$. She must flip exactly one coin. Then, the checkerboard will be given to Bob (who doesn't know the previous state, or anything else except the state of the checkerboard after Alice's move), and he will have to say the integer $$$c$$$ that was informed to Alice.
My thought process
I found this problem to be quite hard (I spent over 6 hours on it, over the course of 3 days), so I want to give an in-depth view of how I approached the problem to make it a bit easier to understand the solution.
The first thing I thought after reading the statement was that it was rather strange thing that this was possible, but after thinking a bit more I realized the problem can be stated as something simpler. If we look at it from Bob's point of view, all he is going to get is a $$$64$$$-bit string and then he will spit out a number between 0 and 63 without any other information; so he has to have a mapping from each string to an unique number. As if he was assigning one of $$$64$$$ colors to each string.
And one cool fact is that you can give names to each vertex of a $$$d$$$-dimensional hypercube using binary strings of length $$$d$$$! And each of the $$$d$$$ neighbors of any vertex with name $$$v$$$ are going to be just the same string $$$v$$$ except exactly one bit is flipped. This fits really well with our problem! And if we can just color this hypercube with $$$64$$$ colors such that every vertex points to every single color (all $$$64$$$ in our case) we will be able to solve it. This idea of transforming binary strings to a hypercube is well-known in some level, I knew it from a Brazilian IOI TST problem, but I felt super hyped when I saw it in this problem.
We are clearly going to have to be smart with our coloring, as our $$$64$$$-dimensional hypercube has $$$2^{64}$$$ vertexes (a lot ._.) which we can't just brute force. The first thing I did was to try and see if we can color every single dimensions of hypercubes this way. The solutions for $$$1$$$ and $$$2$$$ dimensions are pretty simple (colors in blue):
Now, after a bit of tinkering with $$$3$$$ dimensions (just draw a cube), you can easily see that it isn't possible testing 2-3 cases. After noticing this a nice guess would be that this scheme is only possible for dimensions that are powers of $$$2$$$. So let's test for $$$4$$$ dimensions! At first, it might seem hard to draw the dimensional case, specially if you never seen the visualization of a tesseract; but following our naming pattern of bit strings you can see that you only need to "duplicate" a cube, and then connect the corresponding vertexes. Here is a drawing that should make it simpler to see: 
And if we see it this way, it is quite direct that if we can color a cube with $$$4$$$ colors so that each vertex connects to every color except its own color, then if we duplicate it and connect the vertexes we got a valid coloring for $$$4$$$ dimensions, as every vertex will have $$$3$$$ colors distinct for its own + its own after the doubling. Coloring the cube this way is pretty easy:
Ok, so now we know that the coloring for $$$4$$$ dimensions is possible. At that point I just assumed that the answer is possible for all dimensions that are powers of $$$2$$$, and began to look for a construction that made use of this property. Now, this was the hardest part of the problem by far for me. I wanted to figure out how we go from instead of doubling the number of vertexes (one more dimensions), to doubling the number of dimensions (which as you can see from the binary string visualization, squares the number of vertexes).
The idea that dawned on me is pretty nice! If you want to get from a coloring of a $$$d$$$ dimensional hypercube to a $$$2 \cdot d$$$ dimensional, just "transform" every vertex of the original $$$d$$$ dimensional hypercube into it's own $$$d$$$ dimensional hypercube. For example with $$$2$$$ to $$$4$$$ dimensions:
If you consider these edges that connect the "squares" to mean that they should connect the respective vertexes from each square, then that is a precise representation of a $$$4$$$-dimensional hypercube. The next natural step is to check how we can apply this to expand the coloring as well. Lets call these "squares" in the general case groups, so each group has a bunch of vertexes and we are going to connect them in order to double the amount of dimensions.
We should consider that in each group every vertex already connects to all colors that exist in the group, so a nice way do to things is to create two tripes of groups: $$$f$$$ and $$$g$$$. The type $$$f$$$ contains all colors from $$$0$$$ to $$$d - 1$$$, and the type $$$g$$$ contains all colors from $$$d$$$ to $$$2 \cdot d - 1$$$. But notice we also need to create different types of groups even inside the types $$$f$$$ and $$$g$$$, because we need a group to connect to all possible "shifted" version of the other type, so that each vertex connects to each color in the other half of colors. So lets make the definition of $$$f_0, f_1, \ldots, f_{d-1}$$$, and for $$$g$$$ define that $$$g_i$$$ is just $$$f_i$$$ but with every color being added $$$d$$$. Ok, so what is $$$f_i$$$? It is the base $$$f = f_0$$$ but where every color $$$c_v$$$ of the vertex $$$v$$$ is now $$$c_v + i~(mod~d)$$$. Here is all the $$$f$$$s and $$$g$$$s for the case where we are expanding from $$$2$$$ to $$$4$$$ dimensions.
And now to form the valid $$$4$$$-dimensional coloring:
For the general case, where we are trying to expand from $$$d$$$ to $$$2 \cdot d$$$ dimensions, to make the edges between different groups we need to follow two conditions:
1. Edges need to have one side in $$$f_x$$$ and the other one in $$$g_y$$$.
2. A vertex $$$f_x$$$ needs to connect to all groups $$$g_0, g_1, \ldots, g_{d - 1}$$$, and vice-versa.
That second condition should remind you of the original problem: color the graph such that every vertex points to every color. The only thing is that we also need to decide who is going to be type $$$f$$$ and $$$g$$$. And the way to do that is pretty direct: look at the parity of active bits. As to be connected you flip exactly one bit, the parity is always different between connected vertexes, so when we divide like that we get a bipartite partition!
To implement the function int color(vector<int> v) in our code, which is the only thing we need (in Alice's side just test all neighbors, and in Bob's just return the color), let's say the first half of bits determine the type of group which the vertex is in, and the second half determine which vertex he is inside that group. Now we can do the code recursively to find the solution! I think it will be easier to see the code than to explain all the details, so here it is:
#include <bits/stdc++.h>
#include "coins.h"
using namespace std;
int color(vector<int> v) {
int n = v.size();
if (n == 1) return 0; // base case -> 1 dimension, only color zero
// build each half
vector<int> h1, h2;
int groupType = 0;
for (int i = 0; i < (n/2); i++) {
h1.push_back(v[i]);
groupType = ((groupType + v[i]) % 2);
}
for (int i = n/2; i < n; i++) h2.push_back(v[i]);
// decide which type of group he is on
// groupType decide if he is on f or g (sum n/2 or not)
// the colorGroup decide how much we sum (mod n/2)
int colorGroup = color(h1);
int ans = color(h2);
ans = ((ans + colorGroup) % (n/2));
if (groupType) ans = (ans + (n/2));
return ans;
}
vector<int> coin_flips(vector<int> t, int c) {
for (int i = 0; i < 64; i++) {
t[i] = (1 - t[i]);
if (color(t) == c) return {i};
t[i] = (1 - t[i]);
}
}
int find_coin(vector<int> b) {
return color(b);
}
Conclusion
After solving the problem I quickly searched for the solution to see if it was really this way (because I found it quite strange that such a hard problem appeared on a list where the other problems were normal). Then I got really surprised to learn of the simple XOR solution that exists; and after searching a bit more I was even more shocked to realize that apparently no one had ever published the solution I had thought of! I opened a 3blue1brown YouTube video I found, and a bunch of other tutorials as well. And to my surprise, most of them start talking about the hypercube visualization, but they stop there! Saying that in this path there is, most likely, no solution. The one that better exemplifies this is this blog. Specially these two paragraphs: 
And while he might have been overthinking it, there was indeed a solution on precisely the path he was thinking about (though I have no idea what is grey's encoding). I learned a lot with this problem, specially that sometimes it's better to step back and search for a simpler solution. But for IOI I think, even if there was no simple XOR solution, the problem would be a pretty ok difficult. So his writing with:
I thought for a while and concluded that there’s no way IOI contestents are asked to come up with such a complex mapping. There has to be a simpler way.
Is wrong in that sense. Hope you liked the solution and the blog, bye and see ya!
