Editorial for DMOPC '18 Contest 3 P2 - Bob and French Class
Submitting an official solution before solving the problem yourself is a bannable offence.
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 time to check one arrangement, and there are such arrangements, for an algorithm.
For full marks, we will employ a dynamic programming approach. Let be the maximum mark attainable given that the first words have had their language determined, and the longest suffix of French words currently determined has length . is therefore the maximum of , and , incremented by the mark of word in English. , and . The answer is therefore the maximum of , , and .