Holes (Medium)
One fateful day, 6 people numbered 1,2,3,4,5,6 are trying to cross a road that contains several deep holes. To pass through a hole with depth 3, the 3 leading people have to go into the holes in order so that the other people can safely cross the hole. Then, the last people who crossed the hole will pull the highest people from the hole up, and so on. For clarity, look at the diagram below where 4 people are crossing a hole with depth 3 :
If the output sequence is and the holes they must pass through in order has depth of respectively, what is the input sequence ?
If you think the output sequence is
, input your answer as
654321
.
You are advised to solve the Easy version of this problem first.
The answer is 651432.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
Let the input sequence be a 1 , a 2 , … , a 6 . From the Easy version we know that the output is a 3 , a 6 , a 5 , a 4 , a 2 , a 1 . Substitute it with the output sequence 1 , 2 , 3 , 4 , 5 , 6 we get that a 3 = 1 , a 6 = 2 , a 5 = 3 , a 4 = 4 , a 2 = 5 , a 1 = 6 . Reorder the sequence we get the input sequence
651432.