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

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

The system of equations is:

where is the initial state of the tower, is the number of times you need to directly toggle the tower, and these equations are taken modulo .

Time Complexity:

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 after already toggling some of them. Then if tower is not empty, the only way to empty it is to toggle tower . If it is empty, then you cannot toggle tower . Otherwise, there is no way to empty tower again. So essentially, if you know how to toggle the towers before tower , then tower is forced to be toggled or not.

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

To begin this cascade of forcing toggles, you need to determine whether to directly toggle tower or not. To do this, we try both possibilities: tower is directly toggled or it isn't. After toggling tower 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 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:

## Comments

• 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!

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

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

• 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?

• 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.

• 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!!