Editorial for VMSS '15 #0 - Head Data Slave Applications

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.

Authors: awaykened, kobortor

Despite being the first (or 0th) problem, this is one of the more difficult ones in the contest. The militants must be arranged such that the last militant with label $K$ ~K~ must be placed before $K+1$ ~K+1~. This can be reworded to having militants with labels $J$ ~J~ must be after $J-1$ ~J-1~.

Now, let's assume we have $Q$ ~Q~ spots where $Q$ ~Q~ is the sum of all militants. The $Q^\text{th}$ ~Q^\text{th}~ spot must be filled by a militant with the label $N$ ~N~. The order of the rest of the militants labeled $N$ ~N~ (all $m_N-1$ ~m_N-1~ of them) do not matter.

Now those familiar with combinatorics will recognize how we can choose to organize all $m_N-1$ ~m_N-1~ militants however we want, this bringing in the classical question " $N$ ~N~ choose $K$ ~K~". We can repeat this backwards with each group of militants starting with $N, N-1, N-2, \dots$ ~N, N-1, N-2, \dots~.

To do this, we can build a Pascal's triangle and query the answer in $\mathcal O(1)$ ~\mathcal O(1)~ time.

Final complexity: $\mathcal O(N)$ ~\mathcal O(N)~

Comments

There are no comments at the moment.