AtCoder ZONe Energy Programming Contest Problem F

Revision en5, by maomao90, 2021-05-03 06:42:41

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.



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.


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?

Tags #atcoder, atcoder beginner, #xor


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