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) time to check one arrangement, and there are \mathcal O(2^N) such arrangements, for an \mathcal O(N2^N) algorithm.

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


There are no comments at the moment.