### maomao90's blog

By maomao90, history, 3 years ago,

### Abridged statement

There are $N$ vertices in the graph where $N=2^n$ where $n$ is an integer. An array $A$ of size $M$ is given. An edge can be drawn from $i$ to $i\oplus x$ ($\oplus$ represents xor operation) if $x\notin A$. Print $N - 1$ edges such that the edges form a tree.

Statement

#### Issue

The intended solution uses xor basis / gaussian elimination. However, I found some submissions that uses completely different algorithms that ACs all the testcases.

In summary, the code iterates through all the $x\notin A$, and for each $x$, iterate through all the vertices $v$ from $0$ to $n - 1$. While $v$ and $v \oplus x$ are not connected, connect them and move on to vertex $v + 1$, otherwise, break. This algorithm runs in $O(n)$ as it will only connect edges $n - 1$ times and when it cannot connect edges, it breaks immediately. However, does anyone have a proof that it is correct? Will there be any case where breaking early results in the wrong answer? I tried creating a few test cases by hand and it seems to always generate the correct answer.

Code

In another submission, a similar idea was used, however, instead of breaking early, it iterated through all the vertices from $0$ to $n - 1$ as long as $0$ and $x$ are not connected. This clearly results in the correct answer as by looping through all the vertices from $0$ to $n - 1$, it will definitely result in at least one edge being created, so $n - 1$ edges will be created after all iterations. However, it looks as if the algorithm runs in $O(n^2)$. Why does it not TLE?

Code
• +14

 » 3 years ago, # |   0 Auto comment: topic has been updated by maomao90 (previous revision, new revision, compare).
 » 3 years ago, # |   +11 In fact, the second solution is equivalent to the solution used xor basis. Why? Consider how xor basis work: The new number will be put in xor basis if and only if it cannot be represented as xor value of some subset of current xor basis. On the other hand, $0$ and $x$ are connected if and only if $x$ can be represented as xor value of some subset of the numbers considered as edge values before. Therefore, the time complexity of the second solution is $O(N\log{N})$.I'm not sure whether the first solution is correct, but I know that it is almost the same as the second one. The reason is that j and j^i are not connected is equivalent to i cannot be represented as xor value of some subset of the numbers considered as edge values before. In other words, if it breaks, it will break at the very beginning. However, my doubt of the first solution is that, why it is still right, even though if it adds one edge between $a$ and $b$ (\$a