Editorial for Back From Summer '17 P4: Pair Programming


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Author: kobortor

Note that the code can be represented as a tree. If a line begins with C, then it is the root of a tree. If it begins with E, then the variable it is dependent on is its parent. If a line is correct, then the number of mistakes in that subtree is simply the number of errors in all its subtrees. If the line is incorrect, then the number of mistakes is the size of the tree minus the number of mistakes in the subtree.

Subtask 1

Since N \leq 20, it is possible to brute force every possible combination, and pick those that match the tree, then out of those, pick the least and greatest number of errors.

Runtime complexity: \mathcal O(2^N \times N)

Subtask 2

Notice that only the lines that are unreadable are can be changed. In this case, we can iterate through each possibility of true/false for the few unreadable lines and check the errors in each tree.

Runtime complexity: \mathcal O(2^{20} \times N)

Subtask 3

Let dp[x][0] be the minimum value we can achieve at x, and let dp[x][1] be the maximum value we can achieve at x.

Let us prove that we don't need to store any values between the minimum and the maximum to solve for the trees above.

If line x is correct, then the number of errors is achieved by adding the number of errors underneath it. Clearly, to find the minimums and maximums are the only values we need from the lines below it.

If line x is wrong, then the number of errors is maximized by subtracting the least possible number of errors in the subtree, and the number of errors is minimized by subtracting the greatest number of errors in the subtree.

If line x is unreadable, then we can take the better of the two options.

After running the algorithm on each of the tree roots, we can simply add up the minimum and maximum errors to get the final answer.

Runtime complexity: \mathcal O(N)


Comments

There are no comments at the moment.