PROBLEM LINK: ZIO 2012 Question Paper
EDITORIALIST: Aryan Maskara
DIFFICULTY: Easy-Medium
PREREQUISITES: Basics of Backtracking (i.e given the final answer, find how did we reach there)
PROBLEM STATEMENT:
There are many cartons, each with a unique number on it. These cartons are stored on shelves. When a carton numbered K arrives in the shop, the manager places it according to the following rules.
1) If K is bigger than the serial numbers of all the cartons on the top shelf, he adds K at the right end of the top shelf.
2) Otherwise, he finds the carton with the smallest serial number bigger than K on the top shelf. Suppose this carton has number L. He replaces carton L by carton K and inserts carton L into the second shelf using the same rules for that shelf. See the image below for clarity.
Thus, the final order for the sequence is:
1 2
3
4
Given the final order, find how the cartons arrived.
QUICK EXPLANATION:
Firstly, there is a particular way of the displacement of the cartons. By the phrase a “particular way” I mean that when a carton comes to the shop, it can only displace a particular carton and not any of them. This narrows down the number of ways. Using this logic and starting from the final order of the notebook, find the order of the cartons after each particular event. This will give you the answer.
EXPLANATION:
The question has given us the final answer, and we need to find the order of the cartons. Even though only the final answer is given, we can deduce the sequence of cartons based on when they arrived.
Some important observations:
- If a number n is written in the notebook, this means that the position at that shelf was empty before this event (n - 1)th, and after this event (n)th, it got full.
Proof
The manager writes the number n in his notebook if that position of that shelf got filled on the nth event. The above point is just a converse of this.
–End of proof–
- If a number n is written on the ith(i > 1) shelf of the notebook, this means that carton was previously on the (i - 1)th shelf, and has been displaced to the ith shelf.
Proof
Whenever a carton is displaced, there are two options on the next shelf.
The number on the carton is bigger than the number on the rightmost carton of the shelf. This carton will be placed on the rightmost side of the shelf. Thus, it came from the (i - 1)th shelf to the ith shelf.
The carton displaces the carton with the lowest number greater than it, and takes its position, while the other carton goes to the next shelf. Here also, it came from the (i - 1)th shelf to the ith shelf.
–End of proof–
- If a number n is written on the 1st shelf, the serial number of the carton which has arrived is bigger than the rightmost carton on the 1st shelf.
Proof
Let us suppose it was not the biggest serial number of the carton. But, there would be some carton with a bigger serial number than the serial number of the carton. Thus, the carton had to displace that carton, but it did not, it was added to shelf 1. We arrive at a contradiction, and hence, the above observation is true.
–End of proof–
- A carton of the corresponding position and shelf on the notebook has been handled(kept or displaced) at the nth event, where n is the number written at the corresponding position and shelf on the notebook
Proof
As in observation (1), the place was empty after (n - 1)th event, and got filled after the nth event. If the carton was not handled, then it wouldn’t have changed its position. This implies, that the corresponding position in the corresponding shelf would be filled before the (n - 1)th event, which is false. Hence, the above observation is true.
–End of proof–
- When a carton arrives, it will always come on the first shelf.
Proof
There are 2 conditions:
The number on the carton is bigger than the number on the rightmost carton of the shelf. In this case, the carton will stay on shelf 1.
The carton displaces the carton with the lowest number greater than it, and takes its position, while the other carton goes to the next shelf. Here also, the carton will stay on shelf 1, while the displaced carton will move down to shelf 2.
–End of proof–
- When a carton X is displaced into the ith shelf, it has been displaced by the carton whose value is the biggest among all the cartons which have smaller value than the value of carton X.
Proof
The above shelf would have the N cartons + carton X(which is now displaced). According to condition (2) in the problem, only the carton which has the biggest value among all the cartons which have a smaller value than X, can displace carton X from the (i - 1)th shelf.
–End of proof–
Note: In backtracking, you will get the order in which cartons arrived in the reverse order. So for your answer, don’t forget to reverse the order.
I hope you understood how the displacement of cartons works. With these observations, you can work out on the order in which the cartons came, using backtracking. To familiarize you with the approach towards the problem, even more, I am going to solve the 1st subtask, in this editorial.
SOLVING SUBTASK A:
Answer = { }
Now, backtracking, the biggest number in notebook entry is 7, which is on shelf 2, and in position 2. In shelf contents, 95 corresponds to this. According to observation (2), 95 will come from the 1st shelf. So currently one out of {8, 11, 86} has arrived. As a carton will displace the smallest number greater to the number on it, it will be 86. This is because if 8 arrived, it would not have displaced 86, but would have displaced 11. Similarly, 11 would have displaced 86. Thus, we put 86 in our answer block. Now, the table looks like this:
Next, the biggest number in the notebook entry is 6. In shelf contents, 47 corresponds to it. According to observation (2), 47 has come from the 3rd
shelf ( (i - 1)th to ith). Similarly, 22 has come from the 2nd shelf, and 12 has come from the 1st shelf. As a carton will displace the smallest number greater to the number on it, it will be 11. You can figure it out, 8 would have displaced 11, and 95 wouldn’t have displaced anything. Thus, we put 11 in our answer, before the others. Our table looks like,
Now, the biggest number in the notebook is 5, which corresponds to 97 in the shelf contents. As in observation (3), the carton with the biggest serial number on shelf 1 had arrived before this. This can be easily found out to be 95.
Now, our table looks like this,
Now, the biggest number in the notebook is 4, which corresponds to 47 in the shelf contents. As in observation(2), 47 has come from the 2nd shelf, and likewise, 22 has come from the 1st shelf. The number which displaces 22, and is on the 1st shelf is 12. Because, if 8 would have arrived, it would have displaced 12. Thus, 12 has arrived before this event. Our table look like this,
Next, the biggest number in the notebook is 3, which corresponds to 22 in the shelf contents. As in observation(3), the carton with the biggest serial number on shelf 1 had arrived before this. This can be easily found out to be 22.
Now, our table looks like this,
Now, the biggest number in the notebook is 2, which corresponds to 47 in the shelf contents. As in observation(2), 47 has to come from shelf 1. The only element in shelf 1, is 8. Thus, the answer has to be 8.
Finally, we put the carton(i.e 47) in our answer, before the others, as it is the only option from which we can pick.
=> Final Answer = {47, 8, 22, 12, 95, 11, 86}
Thus, the intended solution for this subtask is {47, 8, 22, 12, 95, 11, 86}.
Likewise, you please try the rest of the sub-tasks, but if you get stuck, don’t hesitate to reply to this post, or if you want any clarifications, please reply, so that I can help you.
I hope that you have understood the editorial and how to go about the question.