### maomao90's blog

By maomao90, history, 11 days 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