USACO 2022 December Contest, Bronze

Problem 3. Reverse Engineering


Contest has ended.

Log in to allow submissions in analysis mode


Elsie has a program that takes as input an array of $N$ ($1\le N\le 100$) variables $b[0],\dots,b[N-1]$, each equal to zero or one, and returns the result of applying a sequence of if / else if / else statements on the input. Each statement examines the value of at most one input variable, and returns either zero or one. An example of such a program might be: 

if (b[1] == 1) return 1;
else if (b[0] == 0) return 0;
else return 1;

For example, if the input to the program above is "10" (that is, $b[0] = 1$ and $b[1] = 0$), then the output should be 1.

Elsie has told Bessie the correct output for $M$ ($1\le M\le 100$) different inputs. Bessie is now trying to reverse engineer Elsie's program. Unfortunately, Elsie might have lied; it may be the case that no program of the form above is consistent with what Elsie said.

For each of $T$ ($1\le T\le 10$) test cases, determine whether Elsie must be lying or not.

INPUT FORMAT (input arrives from the terminal / stdin):

The first line contains $T$, the number of test cases.

Each test case starts with two integers $N$ and $M$, followed by $M$ lines, each containing a string of $N$ zeros and ones representing an input (that is, the values of $b[0] \ldots b[N-1]$) and an additional character (zero or one) representing the output. Consecutive test cases are separated by newlines.

OUTPUT FORMAT (print output to the terminal / stdout):

For each test case, output "OK" or "LIE" on a separate line.

SAMPLE INPUT:

4

1 3
0 0
0 0
1 1

2 4
00 0
01 1
10 1
11 1

1 2
0 1
0 0

2 4
00 0
01 1
10 1
11 0

SAMPLE OUTPUT:

OK
OK
LIE
LIE

Here's a valid program for the first test case: 

if (b[0] == 0) return 0;
else return 1;

Another valid program for the first test case: 

if (b[0] == 1) return 1;
else return 0;

A valid program for the second test case: 

if (b[1] == 1) return 1;
else if (b[0] == 0) return 0;
else return 1;

Clearly, there is no valid program corresponding to the third test case, because Elsie's program must always produce the same output for the same input.

It may be shown that there is no valid program corresponding to the last test case.

SCORING:

  • Inputs 2 and 3 have $N = 2$.
  • Inputs 4 and 5 have $M = 2$.
  • Inputs 6 through 12 have no additional constraints.

Problem credits: Benjamin Qi

Contest has ended. No further submissions allowed.