Editorial for ICPC NEERC 2014 I - Improvements - Olympiads Online Judge

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)$ $O (n \log n)$ solution using dynamic programming

$\text{[math]}$

Comments

There are no comments at the moment.