Editorial for Facebook Hacker Cup '15 Round 1 P3 - Winning at Sports - Olympiads Online Judge

Editorial for Facebook Hacker Cup '15 Round 1 P3 - Winning at Sports

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.

This problem has a fairly standard dynamic programming formulation:

Let $f(u, t, U, T)$ $f (u, t, U, T)$ be the number of ways to achieve a stress-free victory when we currently have $u$ $u$ points, the opponent has $t$ $t$ points, and the final score will be $U$ $U$ - $T$ $T$ . The answer we're looking for is then $f(0, 0, U, T)$ $f (0, 0, U, T)$ . We can define $f$ $f$ recursively as follows, assuming $u < U$ $u < U$ and $t < T$ $t < T$ :

$f(U, T, U, T) = 1$ $f (U, T, U, T) = 1$ (we're done!)
$f(u, T, U, T) = 1$ $f (u, T, U, T) = 1$ if $u > T$ $u > T$ (all that's left is for us to finish scoring)
$f(u, T, U, T) = 0$ $f (u, T, U, T) = 0$ otherwise (this victory is not stress-free)
$f(U, t, U, T) = 1$ $f (U, t, U, T) = 1$ (all that's left is for them to finish scoring)
$f(u, t, U, T) = 0$ $f (u, t, U, T) = 0$ if $u > 0$ $u > 0$ and $u \le t$ $u \leq t$ (this victory is not stress-free)
$f(u, t, U, T) = f(u+1, t, U, T) + f(u, t+1, U, T)$ $f (u, t, U, T) = f (u + 1, t, U, T) + f (u, t + 1, U, T)$ otherwise (either team can score next)

Similarly, let $g(u, t, U, T)$ $g (u, t, U, T)$ be the number of ways to achieve a stressful victory:

$g(U, T, U, T) = 1$ $g (U, T, U, T) = 1$ (we're done!)
$g(u, T, U, T) = 1$ $g (u, T, U, T) = 1$ (all that's left is for us to finish scoring)
$g(U, t, U, T) = 0$ $g (U, t, U, T) = 0$ (this victory is not stressful)
$g(u, t, U, T) = 0$ $g (u, t, U, T) = 0$ if $u > t$ $u > t$ (this victory is not stressful)
$g(u, t, U, T) = g(u+1, t, U, T) + g(u, t+1, U, T)$ $g (u, t, U, T) = g (u + 1, t, U, T) + g (u, t + 1, U, T)$ otherwise (either team can score next)

Obviously, the latter two parameters don't change, so we just need $\mathcal O(UT)$ $O (U T)$ memory to memoize the results, and the time complexity will also be $\mathcal O(UT)$ $O (U T)$ .

Comments

There are no comments at the moment.