Editorial for COCI '08 Regional #4 Tablica


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Directly implementing the algorithm given in the problem statement gives a solution of time complexity \mathcal O(KN^2) and space complexity \mathcal O(N^2), scoring 30\%.

A better solution exploits the fact that we don't need to know the positions of all numbers, just the K numbers that appear as X in the moves. We go about simulating the moves as before, but only move numbers whose positions will be significant sometime later. The time complexity of this solution is \mathcal O(K^2) and the space complexity \mathcal O(K).


Comments

There are no comments at the moment.