lce4113 and Security Game

The whole problem turns on one small observation: we do not need to recover either the operation or the complete value of $v$. One known bit of $v$ is enough.

The one-bit primitive

Suppose we know $v_i=c$ for some bit $i$. Send

$m_0=0,\qquad m_1=2^i.$

The $i$-th bit of $m_b$ is exactly $b$, so for the returned value $r=m_b\oplus v$,

$r_i=b\oplus v_i=b\oplus c.$

Therefore

$b=r_i\oplus c.$

That solves the test immediately once any bit of $v$ becomes known.

Extracting a known bit from the first response

Let the first query be $x$, and let the response be $o$.

If some bit differs between $x$ and $o$, only one operation could have caused that change:

| $x_i$ | $o_i$ | Forced operation | $v_i$ | |---:|---:|:---:|---:| | $1$ | $0$ | AND | $0$ | | $0$ | $1$ | OR | $1$ |

Thus, whenever $o_i\ne x_i$, we know $v_i=o_i$.

Now choose the extremely fancy query

$x=1.$

Yes, just one. Bitmasks occasionally reward being aggressively boring.

There are three possibilities:

• If $o=0$, bit $0$ changed from $1$ to $0$. Hence the operation is AND and $v_0=0$.
• If $o>1$, AND is impossible because $v\mathbin{\&}1$ is at most $1$. Therefore the operation is OR, and any set bit of $o$ above bit $0$ is a known $1$-bit of $v$.
• If $o=1$, then $o=x$, so no bit changed. This is the only difficult branch.

The first two cases are exactly the generic $o\ne x$ case: find a differing bit $i$, send $(0,2^i)$, and output $r_i\oplus o_i$.

What does $o=1$ actually mean?

Consider both possible operations:

• With AND, $v\mathbin{\&}1=1$, so $v$ must be odd.
• With OR, $v\mathbin{|}1=1$, so every bit above bit $0$ of $v$ is zero. Therefore $v$ is either $0$ or $1$.

Combining them, the possible values are

$v=0\quad\text{or}\quad v\text{ is odd}.$

Consequently, every possible nonzero $v$ has known least significant bit $1$. We only need to distinguish $v=0$ from a nonzero odd value.

Why fresh randomness is necessary

After receiving the first query, the interactor is allowed to choose $v$, so a deterministic second query can be targeted.

More generally, suppose $o=x$ and a deterministic algorithm sends $m_0,m_1$. Put $d=m_0\oplus m_1$. We can construct two values $u,w$ as follows:

• Where $x_i=1$, set $w_i=1$ and $u_i=1\oplus d_i$.
• Where $x_i=0$, set $u_i=0$ and $w_i=d_i$.

Then $u\mathbin{|}x=x$, $w\mathbin{\&}x=x$, and $u\oplus w=d$. Hence

$m_0\oplus u=m_1\oplus w.$

So the worlds $(b=0,v=u,\mathrm{ty}=|)$ and $(b=1,v=w,\mathrm{ty}=\&)$ produce identical replies. A deterministic algorithm cannot always distinguish them.

The important timing detail is that all hidden values become fixed before we send $m_0,m_1$. We can therefore use fresh private randomness after reading $o$. The interactor gets to be annoying, but it does not get to be clairvoyant.

The randomized second query

In the $o=1$ branch, choose $q$ uniformly among all odd integers in $[0,2^{30})$. There are exactly $2^{29}$ such integers. Send

$m_0=q,\qquad m_1=0.$

The possible responses are:

| Hidden value | $b=0$ | $b=1$ | |:---|:---|:---| | $v=0$ | $q$ | $0$ | | nonzero odd $v$ | $q\oplus v$, which is even | $v$, which is odd |

This gives the decoder:

1. If $r=q$, output $0$.
2. Otherwise, if $r=0$, output $1$.
3. Otherwise, output the parity of $r$.

For $v=0$, one of the first two conditions always applies and is correct.

For odd $v$ with $q\ne v$:

• If $b=0$, then $r=q\oplus v$ is even and nonzero, so the decoder outputs $0$.
• If $b=1$, then $r=v$ is odd and different from $q$, so the decoder outputs $1$.

The sole bad event is $q=v$. In that case, $b=0$ produces $r=0$ and $b=1$ produces $r=q$, so both are mistaken for the corresponding $v=0$ cases.

Since $v$ is fixed before the uniformly random odd $q$ is chosen,

$\Pr[q=v]=\frac{1}{2^{29}}.$

All other branches are deterministic. For at most $10^5$ tests, the union bound gives total failure probability at most

$\frac{10^5}{2^{29}}<1.87\cdot10^{-4}.$

This is genuinely a Monte Carlo solution; the tiny failure probability is the point of the problem, not an implementation blemish.

Complexity and interaction details

Each test uses constant computation and constant memory. It performs exactly the required two query rounds. Every query and final answer must be flushed, and receiving $-1$ must terminate the program immediately.