I created this problem involving binary strings and have been thinking about putting it into a contest for some time, but it wasn't working out. So, I decided to post it here.
Problem Statement:
You are participating in a problem where an interactive judge holds n
binary strings, each of length n
. The value of n
is such that (3 < n < 100). You do not know these binary strings, but you can interact with the judge using two types of operations:
- OR Operation: You can select two different bit positions
(i1, j1)
and(i2, j2)
from any binary strings, and the judge will return the bitwise OR of the two bits at those positions. - AND Operation: You can select two different bit positions
(i1, j1)
and(i2, j2)
from any binary strings, and the judge will return the bitwise AND of the two bits at those positions.
You can perform at most 2 * n
operations in total.
Your task is to find a new binary string of length n
that is guaranteed not to be equal to any of the n
binary strings that the judge holds.
Operations:
- OR(i1, j1, i2, j2): This returns
1
if either bit(i1, j1)
or bit(i2, j2)
is1
. Otherwise, it returns0
. - AND(i1, j1, i2, j2): This returns
1
only if both bit(i1, j1)
and bit(i2, j2)
are1
. Otherwise, it returns0
.
Notes:
- Bit Position: Bit positions are represented as
(i, j)
, wherei
denotes the ith binary string, andj
denotes the jth bit of the ith binary string. Bothi
andj
range from1
ton
.
Let $$$s_{i,j}$$$ be the $$$j^{th}$$$ bit of the $$$i^{th}$$$ string.
We can use the equations mentioned here to find $$$s_{0,0}, s_{1,1}$$$ and $$$s_{2,2}$$$ in $$$6$$$ operations (using operations such as $$$\text{OR}(0, 0, 1, 1)$$$, $$$\text{AND}(0, 0, 1, 1)$$$, $$$\text{OR}(1, 1, 2, 2)$$$).
We can then use $$$\text{OR}(0, 0, i, i)$$$ and $$$\text{AND}(0, 0, i, i)$$$ to find $$$s_{i,i}$$$ (since we already know $$$s_{0,0}$$$) for $$$(3 \leq i \lt n)$$$ in $$$2n-6$$$ operations.
Finally we construct the answer: a string $$$t$$$ with length $$$n$$$ using $$$t_i = \bar {s_{i,i}}$$$.
Since the total number of operations is $$$2n$$$, this satisfies all constraints.
You can find $$$s_{i,i}$$$ in 1 operation, after knowing any one of $$$s_{x,y}$$$. So, it can be solved in $$$N+3$$$ operations as well. The $$$2n$$$ constraint was just to confuse.
Inspired by the video here. This can serve as a hint!