Editorial for ICPC NEERC 2014 I - Improvements

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.

Consider transposition $a_j$ ~a_j~ — the number of ships at coordinate $j$ ~j~, that is reverse to what is given in the input
It is easy to prove that the chain of ships that remain on their initial position corresponds to a subsequence of $a_j$ ~a_j~ with a special property:
- it is an increasing sequence of numbers $a_j$ ~a_j~ followed by decreasing sequence of numbers $a_j$ ~a_j~
Increasing/decreasing subsequence is a well-known problem with $\mathcal O(n \log n)$ ~\mathcal O(n \log n)~ solution using dynamic programming

$\text{[math]}$

Comments

There are no comments at the moment.