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 \le t~ (this victory is not stress-free)
$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)$ otherwise (either team can score next)

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

Comments

There are no comments at the moment.