Editorial for DMOPC '17 Contest 3 P2 - Towers of Hanoi


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

For the first subtask, note that the order of steps doesn't matter and directly toggling the same tower twice does nothing. So we can brute-force all possible subsets of toggled towers and output the first one that works.

Time Complexity: \mathcal O(N \cdot 2^N)

For the second subtask, note that this problem is equivalent to solving a system of N linear equations taken mod 2. As such, we can solve it using Gaussian elimination.

The system of equations is:

\displaystyle \begin{align*}
x_1 + x_2 &\equiv a_1 \\
x_1 + x_2 + x_3 &\equiv a_2 \\
x_2 + x_3 + x_4 &\equiv a_3 \\
\vdots \\
x_{n-2}+x_{n-1}+x_n &\equiv a_{n-1} \\
x_{n-1}+x_n &\equiv a_n
\end{align*}

where a_i is the initial state of the i^\text{th} tower, x_i is the number of times you need to directly toggle the i^\text{th} tower, and these equations are taken modulo 2.

Time Complexity: \mathcal O(N^3)

For the final subtask, we use a greedy-ish approach. Say that at some point, you know that you will never have to directly toggle any towers with an index less than a certain i after already toggling some of them. Then if tower i-1 is not empty, the only way to empty it is to toggle tower i. If it is empty, then you cannot toggle tower i. Otherwise, there is no way to empty tower i-1 again. So essentially, if you know how to toggle the towers before tower i, then tower i is forced to be toggled or not.

Alternatively, look at the system of equations and it's clear that tower i is dependent on the previous two towers.

To begin this cascade of forcing toggles, you need to determine whether to directly toggle tower 1 or not. To do this, we try both possibilities: tower 1 is directly toggled or it isn't. After toggling tower 1 or not, proceed by toggling/not toggling the towers which must be forced.

If, at the end of these forced steps, everything is empty except for the last tower, then that means that something went wrong and the choice made with tower 1 was incorrect. That doesn't really matter though since both possibilities are tested and at least one of them is guaranteed to give a valid solution (since the problem guarantees that there exists a solution).

Time Complexity: \mathcal O(N)


Comments


  • 0
    ht2012  commented on Dec. 15, 2017, 3:04 a.m.

    xD I was pretty lost on the second part. Could you perhaps give me some examples where multiple repeated toggles around one tower could help solve the problem? Thanks!


    • 2
      r3mark  commented on Dec. 15, 2017, 12:11 p.m.

      Sorry, I'm not sure what you're asking. What do you mean by that?


      • 0
        ht2012  commented on Dec. 16, 2017, 3:06 a.m.

        LOL I have only come up with a solution that toggles i if i-1 is 1, and it solves all the test cases i can think of. In my understanding, doesn't each x require at max one toggle? What is an example that requires repeated toggling of one tower?


        • 0
          r3mark  commented on Dec. 16, 2017, 12:19 p.m.

          Yes, that is correct. You will never need to directly toggle the same tower twice. The main difficulty in this problem is realizing you need to consider both cases of whether the first tower is directly toggled or not.


          • 1
            ht2012  commented on Dec. 17, 2017, 4:56 a.m.

            Alright, it looks like its only a small problem that got me stuck in the first place. For some reason I thought if you toggled tower 1 you dont need to toggle tower 2 againt :P. Thx for answering!!