Editorial for DMOPC '18 Contest 3 P2 - Bob and French Class

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.

Author: Kirito

For 10% of marks, we can try every possible arrangement of French words and English words, making sure that no three consecutive words are in French. It takes $\mathcal O(N)$ ~\mathcal O(N)~ time to check one arrangement, and there are $\mathcal O(2^N)$ ~\mathcal O(2^N)~ such arrangements, for an $\mathcal O(N2^N)$ ~\mathcal O(N2^N)~ algorithm.

For full marks, we will employ a dynamic programming approach. Let $f(n, k)$ ~f(n, k)~ be the maximum mark attainable given that the first $n$ ~n~ words have had their language determined, and the longest suffix of French words currently determined has length $k$ ~k~. $f(n+1, 0)$ ~f(n+1, 0)~ is therefore the maximum of $f(n, 0)$ ~f(n, 0)~, $f(n, 1)$ ~f(n, 1)~ and $f(n, 2)$ ~f(n, 2)~, incremented by the mark of word $n+1$ ~n+1~ in English. $f(n+1, 1) = f(n, 0) + a_{n+1}$ ~f(n+1, 1) = f(n, 0) + a_{n+1}~, and $f(n+1, 2) = f(n, 1) + a_{n+1}$ ~f(n+1, 2) = f(n, 1) + a_{n+1}~. The answer is therefore the maximum of $f(N, 0)$ ~f(N, 0)~, $f(N, 1)$ ~f(N, 1)~, and $f(N, 2)$ ~f(N, 2)~.

Comments

There are no comments at the moment.