ManikantanV's blog

Doubt in editorial — Problem C, Good Bye 2014
By ManikantanV, 10 years ago, In English

Problem Link:

Won't the arrangement of books depend on the number of times each book is read? The book which has been read maximum number of times ought to lie closer to the top. Can someone explain how the author's approach yields optimal solution and not my line of thinking?

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
10 years ago, # |
← Rev. 2   Vote: I like it +2 Vote: I do not like it

You're solution is not correct, as you are not using the fact that after a book is read, it goes on the top of the stack. For example, if a book is read 10 times in a row, then that's in no way different than being read just once. So you see, the amount of times is not always connected with the position of the book.

Now let's say the books are read in order {1,3,5,4,2} for example. Then, no matter how the initial stack looked, after {1,3,5,4} are read, 2 will be below all of them. So, regardless of how you order them, you will have to lift those four to read book 2. Well, then it is logical to put 2 on the bottom.

Continuing with that logic then when picking up 4, regardless of the order, 1,3 and 5 will be lifted, so again, 4 should be directly above 2 and so on.

Then if you think about it, it's easy to come up with the author's solution, which is ordering the books as their relative order of first occurrences in the reading requirements.

→ Reply
»
10 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I didn't quite figure out the significance of placing the book on top after reading initially. Thanks for the answer!

→ Reply