Observation 1:↵
We first notice that no matter how the judge shifts $V$ (the value we send), there are only 2 kinds of situations.↵
↵
1. the odd bits of $V$ xor the odd bits of $X$, and the even bits of $V$ xor the even bits of $X$↵
↵
2. the odd bits of $V$ xor the even bits of $X$, and the even bits of $V$ xor the odd bits of $X$↵
↵
Here "odd bits" represents the bits in position 1, 3, 5, 7, and "even bits" represents the bits in position 0, 2, 4, 6↵
↵
Observation 2:↵
If odd bits of $X$ are all 1s, and even bits of $X$ are all 0s (or the opposite), then we can send value $01010101$ to change $X$ to $00000000$ or $11111111$. It means that we only need to make odd bits of $X$ be all the same, and also for even bits of $X$.↵
↵
Observation 3:↵
Let $last$ be the number of 1s after last query, and if we send value $01010101$ and receive $k$, we can calculate the number of 1s for odd bits and for even bits. That is $x = \frac{last - k +k4}{2}$, $y = k - x$. Although we can't determine which value represents odd bits or even bits, it doesn't matter. It means that we can use 1 query to get the number of 1s for odd bits and for even bits. Let's call this operation $getNum$. We do this operation after each change we make.↵
↵
Observation 4:↵
If the number of 1s for odd bits is odd, and the other is even, then we can send value $00000001$ to make them both odd or both even. If they are both odd, then we can send value $00000011$ to make them both even.↵
↵
Observation 5:↵
Let's consider 4 odd bits. Because the shift is cyclic, there are only 3 kinds of state.↵
↵
1. two 0s are adjacent(cyclic), and two 1s are adjacent, including $0011$, $0110$, $1100$, $1001$. We call it $C$ (combined).↵
↵
2. two 0s are seperated, and also for two 1s, including $0101$, $1010$. We call it $S$ (seperated).↵
↵
3. four 0s or four 1s. We call it $A$ (all).↵
↵
The same as 4 even bits. Note that the operation $getNum$ will not change the state. For example, $00110110$'s 4 odd bits are $0101$, 4 even bits are $0110$, so the state is $SC$. Because the odd bits is equivalent to the even bits, we don't need to figure out whether the odd bits are $S$ or the even bits are $S$. We need to make the state of $X$ be $AA$.↵
↵
Observation 6:↵
With ordering some queries appropriately, we can change all value of $X$ whose odd bits and even bits both contains even number of 1s, to $AA$.↵
↵
1. If now $X$ is $AS$ or $AC$ (2 or 6 bits are 1), let $V$ be $0S$ ($00010001$), that changes $AS, AC$ to $AA, AC, SS, SC$. Now we may have $AA, AC, SS, SC, CC$.↵
↵
2. If now $X$ is $SS$, $SC$ or $CC$ (two 1s for odd bits and two 1s for even bits), let $V$ be $SS$ ($00010001$), that changes $SS, SC, CC$ to $CC, AC, AA$. Now we may have $AA, AC, CC$.↵
↵
3. If now $X$ is $AC$ (2 or 6 bits are 1), let $V$ be $0C$ ($00000101$), that changes $AC$ to $CC, AS, AA$. Now we may have $AA, AS, CC$.↵
↵
4. If now $X$ is $CC$ (two 1s for odd bits and two 1s for even bits), let $V$ be $CC$ ($00001111$), that changes $CC$ to $SS, AS, AA$. Now we may have $AA, AS, SS$.↵
↵
5. If now $X$ is $SS$ (two 1s for odd bits and two 1s for even bits), let $V$ be $SS$ ($00110011$), that changes $SS$ to $AA$. now we may have $AA, AS$.↵
↵
6. If now $X$ is $AS$ (2 or 6 bits are 1), let $V$ be $0S$ ($00010001$), that changes $AS$ to $SS$. Now we may have $AA, SS$.↵
↵
7. If now $X$ is $SS$ (two 1s for odd bits and two 1s for even bits), let $V$ be $SS$ ($00110011$), that changes $SS$ to $AA$. now we must have $AA$.↵
↵
The solution makes no more than $20$ queries.↵
↵
PS: Is there anyone who can tell me how to insert highlighted code in the blog?
We first notice that no matter how the judge shifts $V$ (the value we send), there are only 2 kinds of situations.↵
↵
1. the odd bits of $V$ xor the odd bits of $X$, and the even bits of $V$ xor the even bits of $X$↵
↵
2. the odd bits of $V$ xor the even bits of $X$, and the even bits of $V$ xor the odd bits of $X$↵
↵
Here "odd bits" represents the bits in position 1, 3, 5, 7, and "even bits" represents the bits in position 0, 2, 4, 6↵
↵
Observation 2:↵
If odd bits of $X$ are all 1s, and even bits of $X$ are all 0s (or the opposite), then we can send value $01010101$ to change $X$ to $00000000$ or $11111111$. It means that we only need to make odd bits of $X$ be all the same, and also for even bits of $X$.↵
↵
Observation 3:↵
Let $last$ be the number of 1s after last query, and if we send value $01010101$ and receive $k$, we can calculate the number of 1s for odd bits and for even bits. That is $x = \frac{last - k +
↵
Observation 4:↵
If the number of 1s for odd bits is odd, and the other is even, then we can send value $00000001$ to make them both odd or both even. If they are both odd, then we can send value $00000011$ to make them both even.↵
↵
Observation 5:↵
Let's consider 4 odd bits. Because the shift is cyclic, there are only 3 kinds of state.↵
↵
1. two 0s are adjacent(cyclic), and two 1s are adjacent, including $0011$, $0110$, $1100$, $1001$. We call it $C$ (combined).↵
↵
2. two 0s are seperated, and also for two 1s, including $0101$, $1010$. We call it $S$ (seperated).↵
↵
3. four 0s or four 1s. We call it $A$ (all).↵
↵
The same as 4 even bits. Note that the operation $getNum$ will not change the state. For example, $00110110$'s 4 odd bits are $0101$, 4 even bits are $0110$, so the state is $SC$. Because the odd bits is equivalent to the even bits, we don't need to figure out whether the odd bits are $S$ or the even bits are $S$. We need to make the state of $X$ be $AA$.↵
↵
Observation 6:↵
With ordering some queries appropriately, we can change all value of $X$ whose odd bits and even bits both contains even number of 1s, to $AA$.↵
↵
1. If now $X$ is $AS$ or $AC$ (2 or 6 bits are 1), let $V$ be $0S$ ($00010001$), that changes $AS, AC$ to $AA, AC, SS, SC$. Now we may have $AA, AC, SS, SC, CC$.↵
↵
2. If now $X$ is $SS$, $SC$ or $CC$ (two 1s for odd bits and two 1s for even bits), let $V$ be $SS$ ($00010001$), that changes $SS, SC, CC$ to $CC, AC, AA$. Now we may have $AA, AC, CC$.↵
↵
3. If now $X$ is $AC$ (2 or 6 bits are 1), let $V$ be $0C$ ($00000101$), that changes $AC$ to $CC, AS, AA$. Now we may have $AA, AS, CC$.↵
↵
4. If now $X$ is $CC$ (two 1s for odd bits and two 1s for even bits), let $V$ be $CC$ ($00001111$), that changes $CC$ to $SS, AS, AA$. Now we may have $AA, AS, SS$.↵
↵
5. If now $X$ is $SS$ (two 1s for odd bits and two 1s for even bits), let $V$ be $SS$ ($00110011$), that changes $SS$ to $AA$. now we may have $AA, AS$.↵
↵
6. If now $X$ is $AS$ (2 or 6 bits are 1), let $V$ be $0S$ ($00010001$), that changes $AS$ to $SS$. Now we may have $AA, SS$.↵
↵
7. If now $X$ is $SS$ (two 1s for odd bits and two 1s for even bits), let $V$ be $SS$ ($00110011$), that changes $SS$ to $AA$. now we must have $AA$.↵
↵
The solution makes no more than $20$ queries.↵
↵
PS: Is there anyone who can tell me how to insert highlighted code in the blog?
