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! :slight_smile:

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][0] and dp[i][1] 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!


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!