YNOUTPUT - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest

DIFFICULTY

SIMPLE

PREREQUISITES

Ad Hoc

PROBLEM

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.

QUICK EXPLANATION

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.

EXPLANATION

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 (I-1) is NO, and the output for case I is 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.

SETTERS SOLUTION

Can be found here

TESTERS SOLUTION

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.

1 Like
2

what about the case-
2
YES
NO
NO
YES
both the cases are valid outputs. The problem statement was not clear wrt such cases.

3

what would be the output of 3 NO YES YES NO NO YES NO NO NO?

1 Like
4

And what about the input

2
NO
NO
NO
NO

What is the correct answer?

Setter’s and tester’s solution fail for this input.

Is it invalid input? What did I missed in statement?

1 Like
5

In the “Constraints” section, there is this sentence:
“There is only one unique valid output that you can print”

It is probably not the most understandable sentence, but it is what it is. Anyway, this input is invalid.

1 Like
6

I think this input is invalid, because of the same constraint on the input that there will be a unique valid output. Here, there is no valid output.

3 Likes
7

Alternate Solution:
If no test case contains all NOs, print all NOs.
Otherwise at least one of the outputs is YES.
If the ith output is YES, (then all other cases which are identical must have YES too. If some other test case does not match , then it must be NO. Assuming that ith is YES, all its entries must be correct. If for all j, the jth string in the ith testcase is the same as the result for the jth testcase considering i to be true, then ith is YES). Otherwise ith is NO.
My accepted solution: http://www.codechef.com/viewsolution/1269815

1 Like
8

My approach in this problem was similar to @bminus’, but at the beginning (and also at the end) I did a conversion: convert test case to string (from first letters).

For such input we simply choose one string (representing test case) as proposal and try if it matches with other string -> we are creating new string. When all test cases are compared, we simply compare if this temporary result is the same as proposal. If so, we have answer, otherwise String NNN…NNN (t-times N) is the result.

Java code (main loops):

	// the input is in: StringBuilder[] tc = new StringBuilder[t];
	// tc[ i ] represents one test input (as described in statement)
	final StringBuilder res = new StringBuilder();
	for ( int i = 0; i < t; ++i ) {
		res.append( 'N' );
	}

	final StringBuilder tmp = new StringBuilder();
	String proposal;
	for ( int i = 0; i < t; ++i ) {
		proposal = tc[ i ].toString();
		tmp.setLength( 0 );
		for ( int j = 0; j < t; ++j ) {
			tmp.append( proposal.equals( tc[ j ].toString() ) ? 'Y' : 'N' );
		}
		if ( proposal.equals( tmp.toString() ) ) {
			// res = proposal
			res.setLength( 0 );
			res.append( proposal );
			break;
		}
	}

You can find whole solution here.

9

We got our set S of bitmasks. Where S[i][j] stands for the jth bit of the ith bitmask.
Here is my O(n²) approach:

    for(int i = 0; i < T; i++){
    		bool notgood = false;
    		for(int j = 0; j < T && !notgood; j++){
    			if( i  !=  j){
    				if( (S[i] == S[j]) ^ S[i][j] )
    					notgood = true;
    			}
    		}
    		if(!notgood)    // found solution
    			print S[i] and exit
    }

Here’s my code: http://www.codechef.com/viewsolution/1271428

1 Like
10

is S[i]==S[j] is similar to i==j ?

11

please explain your logic

12

I converted “YES” and “NO” to bits. 1 stands for “YES” and 0 means “NO”. S[i] is the bitmask. S[i][j] is the bit. The set S has T bitmasks and one of them is going to be our solution. That’s why I iterate through S and compare with the other bitmasks and look if it’s the solution.

13

so S[i]==S[j] should take O(n) time and not O(1). this would automatically make your algorithm O(n^3). Am i right ?

14

If you implement it wrong, then it takes O(n) to compare.

15

how to do it in O(1) time. please explian. is it bitset<> ?

16

Use std::bitset