The output for each test case is YES or NO. The input is a candidate output for the file, that you might print. If the candidate output provided is indeed the correct output, you print YES; and if and only if it isn’t, you print NO.
Carefully checking each candidate output and matching it to know if it could be the correct output is sufficient.
The only edge case to consider is when the candidate output is not part of the input - in which case the output is all NO. You should also take care that a candidate output must print YES compulsorily for all the inputs which match the candidate output completely and none other.
First let us consider which inputs can be considered candidate outputs.
Parse the entire input and store the same. Considering cases one by one will be insufficient in this problem. Now for a case number
I for which the output for all cases 1 to
NO, and the output for case
YES. If this candidate output is the correct output, then
I would be the first such entry in the list of candidate outputs.
Validating candidate outputs this way reduces the number of candidates that are considered.
Now, carefully iterate through each case and check what would output would be generated if the candidate output was assumed correct. If the output generated is same as the candidate output, then this is the answer (since there will always only be
1 unique answer).
This can be processed in O(T3) time in code which looks like
Let A(i,j) be all the inputs. A(i) is the candidate output in case i for i = 1 to T, inclusive if A(i,j) for all j < i is NO and A(i,i) is YES Let C denote the output assuming A(i) is the expected output for k = 1 to T, inclusive if A(k,j) == A(i,j) for all j = 1 to T, inclusive C(k) = YES else C(k) = NO if(C == A(i)) print C if no answer was found, then answer is all NO.
The last line takes care of the edge case where none of the candidate outputs in the input were correct.
Can be found here
Can be found here
The tester generated a table
same(i,k) which is true if
A(i) == A(k). This way, the only candidate outputs to consider are those for which there is no
k such that
A(i) == A(k) and k > i.