USACO December 2021, Gold Problem 1 - Paired Up

[dixksud]

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!

[Benq]

@dixksud

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?

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].

@dixksud

• why does the return value from the max_span_cost method depends on whether the size of span is even or odd?
• why are there two if statements which depend on whether the number of cows from i to the end is even or odd?

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

[dixksud]

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!

[dixksud]

@Benq

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].

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!

[Benq]

@dixksud

Please let me know if my understanding is correct.

Yes

@dixksud

Then, what is the definition of dp[i][0] and dp[i][1] in the code?

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.

@dixksud

Moreover, what is the relationship between j_1 and j_2 in your explanation?

They’re integers with the same parity.

[dixksud]

It makes more sense. Thank you so much Banq!