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
1if either bit(i1, j1)or bit(i2, j2)is1. Otherwise, it returns0. - AND(i1, j1, i2, j2): This returns
1only if both bit(i1, j1)and bit(i2, j2)are1. Otherwise, it returns0.
Notes:
- Bit Position: Bit positions are represented as
(i, j), whereidenotes the ith binary string, andjdenotes the jth bit of the ith binary string. Bothiandjrange from1ton.
