p250, very similar to a previous tc 250 problem. The first step is to identify components, that is, nodes with L1 distance <= dist with 'v'. Then we have the count of each component. Let odd and even be the number of components with odd and even number of nodes, to get an overall even count, we must choose an even number of odd components and any number of even components.
An analytical solution is 2^even * (2^odd / 2), because binomial sum is even, and (n choose 0) + (n choose 2) + ... + (n choose 2k) = (n choose 1) + (n choose 3) + (n choose 5) + ... + (n choose 2k+1)
A dp approach is to use dp[n][0] and dp[n][1] denote the number of sets with component 1 to n, and [0] if sum is even and [1] if sum is odd. Then the empty set is dp[0][0] = 1, and dp[0][1] = 0
The recurrence is
let components be numbered 1, 2, ..., n
if (cnt[i] is odd) dp[i][0] = (dp[i-1][0] + dp[i-1][1])
dp[i][1] = (dp[i-1][0] + dp[i-1][1])
because we can use the odd component to make odd become even, and not use it leaves the sum odd.
if (cnt[i] is even) then dp[i][0] = dp[i-1][0] * 2, since use cnt[i] or not leaves even as even, and dp[i][1] = dp[i-1][1] * 2 for the same reason.
Some contestant even implemented choose[n][r] and do the actual summation.
One catch, we need to return dp[n][0] - 1. And since we are doing mod 10^9+7, we need to be a bit careful. If dp[n][0] = 0 MOD 10^9+7, then we would return -1 which is bad. Fortunately for me and many contestants with ignorance, since the real answer is 2^k, the mod will never return 0. So we are saved. What a relieve.
p500, I got almost everything, but still could not finish. The dp solution is
dp[l][r] counts number of ways to place wolves with last two at l and r.
dp[0][0] indicates no wolves.
dp[0][l] indicates only one wolf at location[l], which is 1-based.
dp[l][r] = sum of p = 0 to l-1, dp[p][l] such that [p,r] is not contained in any of the L[i], R[i] intervals. Notice that we need to shift the L[i], R[i] value to the right by 1 to make it 1-based.
No comments:
Post a Comment