AtCoder ZONe Energy Programming Contest Problem F
Разница между en4 и en5, 0 символ(ов) изменены
### 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](https://atcoder.jp/contests/zone2021/tasks/zone2021_f)↵
#### 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.↵

<spoiler summary="Code">↵
~~~~~↵
REP(x,n){↵
    if(!inA[x]){↵
        REP(v,n){↵
            int a=v,b=(v^x);↵
            if(find(a)!=find(b)){↵
                edges.pb({a,b});↵
                merge(a,b);↵
            }↵
            else{↵
                break;↵
            }↵
        }↵
    }↵
}↵
~~~~~↵
[Submission](https://atcoder.jp/contests/zone2021/submissions/22214634)↵
</spoiler>↵

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?↵

<spoiler summary="Code">↵
~~~~~↵
for(int x=1;x<n;x++){↵
    if(!inA[x]) continue;↵
    if(uf.same(0,x)) continue;↵
    for(int v=0;v<n;v++) add_edge(v,v^x);↵
}↵
~~~~~↵
[Submission](https://atcoder.jp/contests/zone2021/submissions/22207964)↵
</spoiler>↵

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
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)