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)$ $O (K N^{2})$ and space complexity $\mathcal O(N^2)$ $O (N^{2})$ , scoring $30\%$ $30 %$ .

A better solution exploits the fact that we don't need to know the positions of all numbers, just the $K$ $K$ numbers that appear as $X$ $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)$ $O (K^{2})$ and the space complexity $\mathcal O(K)$ $O (K)$ .

Comments

There are no comments at the moment.