Problem link: http://www.usaco.org/index.php?page=viewproblem2&cpid=673
Solution link: http://www.usaco.org/current/data/sol_team_platinum_dec16.html
I don’t understand much of the editorial at all, but let’s start with the fact that i don’t get how there’s an O(N^2M^2K) solution to compute f(N, M, K).
This problem uses dynamic programming, which you can read about here:
Starting with the O(N^2M^2K) solution, we’ll let f(n,m,k) equal the number of ways to choose teams using the first n of Farmer John’s cows and the first m of Farmer Paul’s cows, such that they have each picked k cows so far such that the most recently picked pair of cows is (n, m).
To compute f(n,m,k), we’ll sort the array, because this ensures that cows are paired off based on the pairs we choose.
For some pair (n, m) such that a_n > b_m (so we satisfy the condition that FJ wins), we can iterate over every possible previous pair (n', m'), and say f(n,m,k) += f(n', m', k - 1). In other words, f(n,m,k) = \sum f(n',m',k - 1) for all (n',m').
This gives us an O(n^2m^2k) algorithm because we can iterate over all (n',m') in O(nm) time. To speed this up, we can use prefix sums to compute \sum f(n', m', k) in O(1) time.