Editorial for COCI '22 Contest 4 #2 Zrinka

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.

The first two subtasks can be solved using a greedy approach.

For full points, we will use dynamic programming.

Let $dp(i, j, flag)$ $d p (i, j, f l a g)$ represent the solution if we only consider the first $i$ $i$ positions of the first array, the first $j$ $j$ positions of the second array, and if the largest number is in the first array, then $flag = 0$ $f l a g = 0$ , otherwise $flag = 1$ $f l a g = 1$ (and the largest number is in the second array).

For the transition we need only to consider $4$ $4$ states: $\{(i-1, j, 0), (i-1, j, 1), (i, j-1, 0), (i, j-1, 1)\}$ ${(i - 1, j, 0), (i - 1, j, 1), (i, j - 1, 0), (i, j - 1, 1)}$ , so the final complexity is $\mathcal O(nm)$ $O (n m)$ .

Comments

There are no comments at the moment.