Another solution for Google Code Jam 2022 Round 1B problem C (ASeDatAb, Test Set 2)
Разница между en4 и en5, 0 символ(ов) изменены
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}{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?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en6 Английский Phantasy 2022-04-27 03:26:12 6 Tiny change: 'frac{last + k}{2}$, $y ' -> 'frac{last - k + 4}{2}$, $y '
en5 Английский Phantasy 2022-04-26 20:48:58 0 (published)
en4 Английский Phantasy 2022-04-26 20:48:38 133
en3 Английский Phantasy 2022-04-26 20:34:53 1416 Tiny change: 'ary="code">\n#inclu' -> 'ary="code" class="c++">\n#inclu'
en2 Английский Phantasy 2022-04-26 19:52:08 845 Tiny change: 'is $SC$.\n~~~~~\nYour code here...\n~~~~~\n\n\n\nThe ' -> 'is $SC$.\n\n\nThe '
en1 Английский Phantasy 2022-04-26 19:27:38 1309 Initial revision (saved to drafts)