Madhavan Mukund

Assignment 7: Backtracking

19 November, 2022
Due 30 November 6 December, 2022

• The Task
• Solving the Task

The Task

Your task is to solve the problem Depot from the International Olympiad in Informatics, 2001.

• Official IOI-2001 problem statement for Depot
• Official IOI-2001 solution for Depot

Solving the Task

When we add a number to a depot, it results in a sequence of moves that ends with some value being appended as the last element in a row. Hence, we can start with the last element in each row and try to "undo" the move that brought it there.

For instance, consider the depot

	1 4 5
	2 9
	3
      

• If we assume the last move resulted in the 3 in the third row, it must have been pushed there because 2 displaced it from the previous row. This 2 must have come from the first row, where it must have been displaced by 1. So the last move consisted of inserting 1 into the depot

  	2 4 5
  	3 9
        

• If we assume the last move resulted in the 9 at the end of the second row, it must have been pushed there because 5 displaced it from the first row. So the last move consisted of inserting 5 into the depot

  	1 4 9
  	2
  	3
        

• If the last move resulted in the 5 at the end of the first row, the last move consisted of inserting 5 into the depot

  	1 4
  	2 9
  	3
        

We can then repeat this analysis to extract the number inserted at the second last step etc, so we reconstruct the original input sequences in reverse order.

Notice that any legal depot will have each row in ascending order and no row can be longer than the row above it.

Submit your solution via Moodle, as a Jupyter notebook, with explanatory comments.