So I was thinking about this CSES problem: link. I saw that the answer is (x-1) ^ (y-1), but I have absolutely no idea why it works. Could someone explain or at least give some hints? Thanks.
№ | Пользователь | Рейтинг |
---|---|---|
1 | tourist | 3845 |
2 | jiangly | 3707 |
3 | Benq | 3630 |
4 | orzdevinwang | 3573 |
5 | Geothermal | 3569 |
5 | cnnfls_csy | 3569 |
7 | jqdai0815 | 3532 |
8 | ecnerwala | 3501 |
9 | gyh20 | 3447 |
10 | Rebelz | 3409 |
Страны | Города | Организации | Всё → |
№ | Пользователь | Вклад |
---|---|---|
1 | maomao90 | 171 |
2 | awoo | 163 |
2 | adamant | 163 |
4 | maroonrk | 152 |
5 | nor | 151 |
5 | -is-this-fft- | 151 |
7 | TheScrasse | 147 |
7 | atcoder_official | 147 |
9 | Petr | 145 |
10 | pajenegod | 144 |
Название |
---|
(forgive my poor English)
This can be proved with induction .
Now we calculate the answer for $$$(x,y)$$$
Assume that we already know that the answer is $$$(tx-1)xor(y-1)$$$ for $$$(tx,y),tx<x$$$ and $$$(ty-1)xor (x-1)$$$ for $$$(x,ty),ty<y$$$ .
(make $$$x\leftarrow x-1,y\leftarrow y-1$$$)
What we need to prove is that $$$Mex(tx\ xor\ y,ty\ xor\ x )=x\ xor\ y$$$
We can see that $$$x\ xor\ y$$$ is not in $$${tx\ xor\ y,ty\ xor\ x}$$$ , so we only need to prove that for all $$$k\in[0,x\ xor\ y)$$$ , $$$k$$$ can be represented as $$$tx\ xor\ y$$$ or $$$ty\ xor\ x$$$ which is same as $$$k\ xor\ x<y$$$ or $$$k\ xor\ x<y$$$
We will prove that it is impossible for $$$k\in[0,x\ xor\ y)$$$ to satisfy $$$k\ xor\ x\geq y$$$ and $$$k\ xor\ x\geq y$$$
We can remove the equal sign.
The restriction becomes $$$k\ xor\ x> y$$$ and $$$k\ xor\ y> x$$$
Consider the first bit where $$$x\ xor\ k$$$ and $$$y$$$ differs .
It can be found that for all bits higher than this bit $$$k=x\ xor\ y$$$
And in this bit $$$y=0,x\ xor\ k=1$$$
And it is impossible for $$$x=0,k=1$$$ as it will break the limit of $$$k\in[0,x\ xor\ y)$$$ . So this must be $$$x=1,k=0$$$ , but in this way $$$k\ xor\ y$$$ and $$$x$$$ will differ at this bit and $$$k\ xor y=0,x=1$$$ , which will break the limit $$$k\ xor\ y> x$$$.
So it is impossible for $$$k\in[0,x\ xor\ y)$$$ to satisfy $$$k\ xor\ x\geq y$$$ and $$$k\ xor\ x\geq y$$$.
So $$$Mex(tx\ xor\ y,ty\ xor\ x )=x\ xor\ y$$$