maomao90's blog

By maomao90, history, 11 days ago, In English

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?


Read more »

  • Vote: I like it
  • +14
  • Vote: I do not like it