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: \mathcal{O}(NM2^{NM})

For the second subtask, let's assume N=2 since the N=1 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: \mathcal{O}(NM)

For the third subtask, observe that rows with more than \lceil \log_2(N) \rceil ? can be ignored due to Hall's marriage theorem. It essentially states that, each row that can yield at least N 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 3 ?. Therefore, it suffices to brute force all of these assignments as well.

Time complexity: \mathcal{O}(N2^{3N})

Using the same observation as the previous subtask, we can remove all rows with more than 9 ?. Now, each row can yield at most N 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 N^2 nodes on the right and at most N^2 edges in the graph. We can then run any bipartite matching algorithm to find a perfect matching.

Time complexity: \mathcal{O}(N^3)


Comments

There are no comments at the moment.