AtCoder ZONe Energy Programming Contest Problem F

Revision en4, by maomao90, 2021-05-03 06:41:55

### 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

#### History

Revisions

Rev. Lang. By When Δ Comment
en5 maomao90 2021-05-03 06:42:41 0 (published)
en4 maomao90 2021-05-03 06:41:55 2 Tiny change: ' a tree.\n[Stateme' -> ' a tree.\n\n[Stateme'
en3 maomao90 2021-05-03 06:41:36 68
en2 maomao90 2021-05-03 06:40:26 81
en1 maomao90 2021-05-02 17:23:59 2175 Initial revision (saved to drafts)