Editorial for DMOPC '19 Contest 5 P6 - Cecilia's Computational Crisis

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: george_chen

For the first subtask, it suffices to brute force all ways of replacing each ? with either an X or a . and checking if the resulting plan is efficient.

Time complexity:

For the second subtask, let's assume since the case is trivial. Let's suppose that there are no ? in either string. Then clearly there is an efficient plan if the strings are different and no efficient plan if the strings are equal. If there is a single ? in either string, there is always an efficient plan.

Time complexity:

For the third subtask, observe that rows with more than ? can be ignored due to Hall's marriage theorem. It essentially states that, each row that can yield at least distinct rows after replacing the ? with . or X can be ignored because they can always be matched to one of these rows. Therefore, if we ignore rows that don't satisfy the limit, each row contains at most ?. Therefore, it suffices to brute force all of these assignments as well.

Time complexity:

Using the same observation as the previous subtask, we can remove all rows with more than ?. Now, each row can yield at most distinct rows after performing all possible replacements. We can build a bipartite graph with each initial row on the left and every possible resulting row on the right. There are at most nodes on the right and at most edges in the graph. We can then run any bipartite matching algorithm to find a perfect matching.

Time complexity: