# USACO December 2021, Gold Problem 1 - Paired Up

I tried to understand the official solution.

I could not associate the explanation of Case 2: T = 2 with the `max_span_cost` method in the given code. Can anyone explain

1. why the second dimension of `dp` in the code only has two values of `dp[i].first` and `dp[i].second`, instead of `j` values?
2. why does the return value from the `max_span_cost` method depends on whether the size of `span` is even or odd?
3. why are there two `if` statements which depend on whether the number of cows from `i` to the end is even or odd?

In the explanation, it says “we only care about the parity of the number of unpaired cows”. But it seems to me that the code cares about the parity of the number of cows (not just unpaired) from `i` to the end.

It seems to me that the final code dramatically simplifies the DP explanation. Any more hints would be really appreciated! Thanks so much!

Since the parity of `j` determines whether we can transition from `dp[ub[i]][j-1]` to `dp[i][j]`. In other words, when `j_1` and `j_2` have the same parity, we can transition from `dp[ub[i]][j_1-1]` to `dp[i][j_1]` if and only if we can transition from `dp[ub[i]][j_2-1]` to `dp[i][j_2]`.

because we need to be able to pair up all the cows besides those that we chose not to pair

Thank you so much, Benq, for your quick response during the holiday season! I will think about it more and raise more questions if I have any. Happy new year! Hi Banq,

I am still confused. In the official solution, it said that Let `dp[i][j]` be the maximum sum of values of unpaired cows if we only consider `i` to `n` cows in the current chain and there are `j` unpaired ones. I assume that it means there are `j` unpaired ones from `i` to `n` so far. Please let me know if my understanding is correct.

Then, what is the definition of `dp[i]` and `dp[i]` in the code? They must have a different meaning from `dp[i][j]`.

Moreover, what is the relationship between `j_1` and `j_2` in your explanation? Why is the transition to `dp[i][j_1]` dependent on the transition to `dp[i][j_2]`?

Thanks so much for your time!

Yes

I assume you mean `dp[i].first` and `dp[i].second`. These correspond to the min over all even `j` of `dp[i][j]`, and the min over all odd `j` of `dp[i][j]`, respectively.

They’re integers with the same parity.

It makes more sense. Thank you so much Banq!