Blog #2

Beautiful idea behind the problem D of last Kazakhstan NOI

When I was 11th grade, I competed in Kazakhstan National Olympiad in Informatics. To be honest, the problemset was awesome, I really liked it. I suggest you to check it out. And one of my favourite problems from that contest was problem D of the first day. Check the statement.


Subtask 1 — 9 points
This subtask can be solved with the brute-force solution: by checking all possible 2^n subsequences of sequence a.

Subtask 2 — 9 points
Check the solution for the third subtask, which is O(min(n, m)^2 * max(n, m)). Or you can solve it by checking all possible 2^m subsequences of sequence b.

Subtask 3 — 28 points
Unlike previous subtasks, in this subtask you need to come up with a much more efficient solution. For now, let’s forget the memory limit for this problem, I’ll explain how we can reduce our memory usage after. :) Let’s solve it using dynamic programming. maxLen[j][i][tp], where 1 ≤ j ≤ m,1 ≤ i ≤ n,0 ≤ tp ≤ 1, is equal to the maximum possible length of a beautiful sequence which is a subsequence of arrays a[1],a[2],...,a[i] and b[1],b[2],...,b[j]. The length is odd if tp = 1 or even if tp = 0. And the last element of a beautiful sequence is equal to a[i]. f[j][i][tp], with same parameters, is equal to the number of distinct beautiful sequences of maximum length.

Subtask 4 — 54 points
To solve for full points we need to get rid of the last for. We can get rid of it by keeping the maximum lengths of odd/even beautiful sequences (with keeping number of different sequences, also).
That’s it! Now the only question is: how to reduce the memory usage. Fortunately, we can get rid of parameter j, by creating 2 new arrays (one for the j − 1 and one for j). If it’s still not clear to you, then take a look at the solution code by downloading the archive of this problem.

P.S. You can find more detailed solution in the editorial.