redheadphone's blog

By redheadphone, 3 months ago, In English

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:

  1. 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.
  2. 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) is 1. Otherwise, it returns 0.
  • AND(i1, j1, i2, j2): This returns 1 only if both bit (i1, j1) and bit (i2, j2) are 1. Otherwise, it returns 0.

Notes:

  • Bit Position: Bit positions are represented as (i, j), where i denotes the ith binary string, and j denotes the jth bit of the ith binary string. Both i and j range from 1 to n.
  • Vote: I like it
  • +62
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it +5 Vote: I do not like it
My solution
  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Inspired by the video here. This can serve as a hint!