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

Revision en1, by Phantasy, 2022-04-26 19:27:38

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$$$.

The solution makes no more than 20 queries.

Tags gcj, constructive algorithms

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en6 English Phantasy 2022-04-27 03:26:12 6 Tiny change: 'frac{last + k}{2}$, $y ' -> 'frac{last - k + 4}{2}$, $y '
en5 English Phantasy 2022-04-26 20:48:58 0 (published)
en4 English Phantasy 2022-04-26 20:48:38 133
en3 English Phantasy 2022-04-26 20:34:53 1416 Tiny change: 'ary="code">\n#inclu' -> 'ary="code" class="c++">\n#inclu'
en2 English 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 English Phantasy 2022-04-26 19:27:38 1309 Initial revision (saved to drafts)