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.
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 and space complexity , scoring .
A better solution exploits the fact that we don't need to know the positions of all numbers, just the numbers that appear as 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 and the space complexity .
Comments