Another solution for Google Code Jam 2022 Round 1B problem C (ASeDatAb, Test Set 2)

Правка en6, от Phantasy, 2022-04-27 03:26:12

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 + 4}{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?

Теги gcj, constructive algorithms

История

 
 
 
 
Правки
 
 
  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)