Be kind for 2020 (bkf2020)'s Computer science log

First, I read the first sentence of the solution to get a hint on how to solve this problem. Let's call two adjacent cows "linked" if they are able to pair up with each other. We can split the cows up into chains where each pair of adjacent cows in a chain are linked, and no two cows in different chains are linked.

Using this idea, I was able to solve the T = 1 case correctly, and my solution the T = 2 case was pretty similar to the solution. However, it was wrong and more complicated. After reading the solution, I understood that if there are an ODD number of cows already unpaired, and you leave an unpaired cow i at an EVEN index, then you must pair up cows i - 1 and i + 1. If there are an ODD number of cows already unpaired and you leave an unpaired cow at an ODD index, you must pair up an even number of adjacent cows (0 is fine).

Similarly, I understood that if there are an EVEN number of cows already unpaired, and you leave an unpaired cow i at an ODD index, then you must pair up cows i - 1 and i + 1. If there are an EVEN number of cows already unpaired and you leave an unpaired EVEN at an even index, you must pair up an even number of adjacent cows (0 is fine).

This approach lets you transition dp[i][j] = dp[i + 1][j] instead of dp[i][j] = dp[i + 2][j] (which is what I did in my original solution).

If the current number of cows already unpaired DOES NOT have the SAME PARITY of the total number of cows in a link, then we MUST be able to pair up addition cows. Otherwise, we don't consider it.

My idea is to try to weight all nodes that are currently unweighted and are only connected to zero or one other unweighted nodes. This is done by setting those nodes to the sum of their already weighted neighbors, and setting the ONE node they are connected to to weight one (if it exists). If there is a component with ONLY two unweighted nodes connected, then we should consider the two possible ways to weight one of the nodes as 1. However, this does not guarantee the minimal possible sum of weights. Not sure what is wrong yet.

Found a failing test case using CF Stress. I ended up using the editorial to figure out what I was missing. I basically got the observation that all bad nodes should be set to one, and all good nodes are a sum of their neighbors, but didn't use this to motivate a tree-dp.

Let X represent how the pasture looks for 0 ≤ x, y ≤ 3ⁿ for some n. Let O represent an empty pasture for 0 ≤ x, y ≤ 3ⁿ for the same n. Then the pasture for 0 ≤ x, y ≤ 3^{n + 1} looks like this:

XOX
OXO
XOX

n = 2 may suggest this idea, but I got this idea from writing a simple script to visualize the pattern. I had the idea of doing this, because there must be some kind of pattern if you want to solve this problem efficiently. I believe this is NOT against the USACO rules, so I can do this during a contest. I DID NOT SOLVE THIS PROBLEM DURING AN OFFICIAL CONTEST.

Code for the script

After I wrote the script, I came up with the following idea: Let num_cows(x, y, d) count the number of cows from (x, y) to (x + d, y + d).

Then, we can enclose all such cows within a 3ⁿ by 3ⁿ grid. We can find n using binary search.

As mentioned earlier, we can split the 3ⁿ by 3ⁿ grid into smaller 3^{n - 1} by 3^{n - 1} grids, and we can find the places the diagonal intersects these grids.

Thus, we split up the original problem into many smaller problems.

This is a rough outline, but my implemenation was quit messy. It gets accepted but is borderline TLE.

I only can solve this problem if N is even.

To do this, I let dp[i][a] be the number of ordered tuples (h[i], ..., h[N]) from cows i to N with h[i] ≥ a.

Then, it is easy to get the values for dp[N - 2][a] (2 cow case). After that I loop through values of i from N - 4 to 0 (decreasing by 2 each time), and for each value of i, I loop through values of a from H[i] to 0 (decreasing by 1 each time). I set dp[i][a] = dp[i][a + 1] The cow at i + 1 has a value b and for each value of a, I loop through values of b from a to H[i + 1]. For each value of b, I update dp[i][a] += dp[i + 2][0] - dp[i + 2][max(H[i + 2] - b + a + 1, 0)].

What we do here is make cows i + 1 and i + 2 equal to a by subtracting b - a from them. Thus, cow i + 2 can be at most H[i + 2] - b + a. If H[i + 2] - b + a + 1 is negative, I just use 0 instead.

The mistake I made was that dp[i][a] could be negative because of the mod. (I found out with the USACO test data.) Thus, I need to do dp[i][a] += MOD to combat this issue.

I only pass the sample input if N is odd.

Update: After talking to another person, I redefined cost[i][j] to be the cost of performing all cuts between positions cuts[i] and cuts[j] on the piece of wood. This caused the transition equation to become cost[i][j] = min(cuts[j] - cuts[i] + cost[i][k] + cost[k][j]) for all possible k.

My first solution was to greedily add the cows with the highest ratios, but I think it doesn't work because adding a cow with a lower ratio and lower weight might result in a higher overall ratio. As a result, I used the USACO solution, but I don't understand why dp[k1] will always have the optimal value, because dp[k] can be updated and it doesn't guarantee dp[k1] gets updated. I believe if dp[k] can get updated by a cow with weight w, dp[k1] can get updated for the same cow with weight w by using dp[k1 - w] (or dp[W] if k1 = W).

Update: After talking to another person, I realized that dp[k1] shouldn't get updated by the same cow that dp[k] gets updated by. Still need to finish implementing this problem.

points.push_back({xl, yl}); points.push_back({xb, yb});

• a marble of size a by m and a marble of size n - a by m
• a marble of size n by b and a marble of size n by m - b

The first solution I had was testing if a path between any two cows existed. After knowing this was a floodfill problem, I realized that I could just find which cows a cow can visit.

However, I also misread the problem and didn't realize the roads were between ADJACENT cows. Furthermore, I didn't realize there could be MULTIPLE roads in each row or column. I thought there was at most one road for each row or column.

Before: Tried solving this problem by sorting the cows by their endpoint in increasing order. Then, each cow got the earliest chicken possible. Getting WA on every test case except 3, and can't find a counterexample yet.

After: used a multiset instead of a set, since chickens may start at the same time. Got accepted.

I solved this problem by doing dijsktra in reverse. Basically, I wanted the maximum distance to each node instead of the minimum, but I think something is too slow with this. Not sure what, though.

Note I will probably not do this problem for now. It uses topological sorting, and I don't think USACO silver needs this.