That’s One Hanoi-ed Teacher: Difference between revisions

Latest revision as of 22:27, 3 November 2017

This problem gives us an intermediate configuration of a game of "towers of hanoi" and asks us whether it is valid, and if so, how many moves are remaining.

Before trying to solve this problem, it behooves one to solve a few smaller games of towers of hanoi to see how the optimal solutions work, and how many moves it takes. One finds quickly that it is recursive in nature, and the number of moves is 2^n - 1. n is too large, however, to simulate all moves.

Given that n IS too large, we need some way to directly calculate from the state of the disks what our position is. It turns out this is quite simple. This is a classic select-an-element problem.

We know from our inspection that the game can be divided into 3 halves (jokes!):

the moves before the largest disk is moved (2^(n-1)-1 moves)
the move of the largest disk (1 move)
the moves after the largest disk is moved (2^(n-1)-1 moves)

If the disk has NOT moved, the remaining moves are the sum of steps 2 and 3 above, plus a bit of extra. If the disk HAS moved, the remaining moves are just a bit of extra. We can calculate that "extra" recursively by removing the largest disk and repeating the steps.

We have one further issue, though. When we are in the first section above, the "work" required is to move all the smaller disks from column 1->2. In the third section, it is from 2->3. This means when we recurse, we have to pass in which our starting and target pillars are to know whether the largest disk for that next recursion has moved or not. Considering the example images in the problem statement, if we recurse "after step 5," we see that the second largest disk has NOT moved yet despite being on the second pillar already. This makes sense because starting at step 4 (the move of the largest disk), the "starting pillar" is the middle one, and the "target pillar" is the right hand one, so we are in the FIRST of the steps above.

@@ Line 1: / Line 1: @@
-This problem asks us to simulate the filling of a champagne tower with arbitrarily placed glasses.
+This problem gives us an intermediate configuration of a game of "towers of hanoi" and asks us whether it is valid, and if so, how many moves are remaining.
-We need to calculate where water will go when any given glass is full. Since water falls down, we'll do this in descending z order. for each glass, look at the glasses above it and evaluate the circles for any intersection. if there is, the amount of water that goes into this glass relative to the total water in the above glass is proportional to how much the circumference of the upper glass overlaps relative to the total circumference. We track the contribution from each glass above us.
+Before trying to solve this problem, it behooves one to solve a few smaller games of towers of hanoi to see how the optimal solutions work, and how many moves it takes. One finds quickly that it is recursive in nature, and the number of moves is 2^n - 1. n is too large, however, to simulate all moves.
-Caveat: what if there is a glass between us and some higher glass which is "stealing" some of the overflow? Maintain a list of segments of "unused" portions of each glass, that is, the range of angles which, were there no more glasses, would be dumping water onto the floor. The rest of the water is currently being "consumed" by some other glass between, so we can only take the water falling from the unused portions. Modify the ranges accordingly. Clever ones can use a segment tree for this, but as there are 20 glasses, it is not necessary.
+Given that n IS too large, we need some way to directly calculate from the state of the disks what our position is. It turns out this is quite simple. This is a classic select-an-element problem.
-Once the graph of consumers is completed, simulate the fill. The maximum time is too large (10^8 centiseconds) to go timestep by timestep, so we have to figure out the next "interesting" thing occurs, namely when a glass fills next. This means we need to store total volume of each glass, and the current fill rate. Each time a glass fills, we update our fill rates based on the previously calculated values, and then calculate which glass will fill up next.
+We know from our inspection that the game can be divided into 3 halves (jokes!):
-If there is any glass other than the top glass that has no "filler," the problem is impossible.
+# the moves before the largest disk is moved (2^(n-1)-1 moves)
+# the move of the largest disk (1 move)
+# the moves after the largest disk is moved (2^(n-1)-1 moves)
+If the disk has NOT moved, the remaining moves are the sum of steps 2 and 3 above, plus a bit of extra. If the disk HAS moved, the remaining moves are just a bit of extra. We can calculate that "extra" recursively by removing the largest disk and repeating the steps.
+We have one further issue, though. When we are in the first section above, the "work" required is to move all the smaller disks from column 1->2. In the third section, it is from 2->3. This means when we recurse, we have to pass in which our starting and target pillars are to know whether the largest disk for that next recursion has moved or not. Considering the example images in the problem statement, if we recurse "after step 5," we see that the second largest disk has NOT moved yet despite being on the second pillar already. This makes sense because starting at step 4 (the move of the largest disk), the "starting pillar" is the middle one, and the "target pillar" is the right hand one, so we are in the FIRST of the steps above.
 [[Category:ICPC Problems]]
 [[Category:Ecna2016]]
 [[Category:Algorithm Medium]]
-[[Category:Implementation Medium]]
+[[Category:Implementation Easy]]
-[[Category:Simulation]]
+[[Category:Select an Element]]
-[[Category:Geometry]]
-[[Category:Interesting Points]]

That’s One Hanoi-ed Teacher: Difference between revisions

Latest revision as of 22:27, 3 November 2017

Navigation menu

Search