Need help with two variants of 16.1 (DP Problem)

#1

Hi all,

I’ve solved all variants of 16.1 except two of them (p.305). And I totally have no idea about these two questions. Could you guys give some hints to solve this? The questions are below.

  1. Suppose the final score is (s,s’). Team 1 scored s points and Team 2 scored s’ points. How would you compute the number of distinct scoring sequences which result in this score?

  2. Suppose the final score is (s,s’). How would you compute the maximum number of times the team that leads could have changed?

Thank you

0 Likes
#2

Hi @archerleonard,

The key of solving these two variants is trying to add s and s’ both into the considerations of DP. It means you need to think about all possible combinations of (s, s’).

0 Likes
#4

For Variant #3, I have first explicitly calculated all possible combinations using an approach similar to the optimal one presented for the main problem, but instead of storing the number of combinations, I stored the sequences encoded in the form of [n_scores1, n_scores2, n_scores3, etc]. So for example, if you have 2, 3 and 7 as individual scores, and the sequence is 2,2,3,3,3,7, it would be encoded as [2,3,1]

Then, grabbed the sequences from each of the teams scores, and used the permutations with repetition formula to find the final result.

For variant #4, I took the two combination sets and go over each team1/team2 possible match of combinations to find which yielded the maximum number of lead changes.

0 Likes