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

home

What is this?

These are computer science problems I am trying out this week. I'll include notes. My goal is to seriously attempt/solve at least ALL of the problems (as of Jan 02, 2022). This starts the week of Jan 03, 2022 to Jan 09, 2022. It's okay if I don't solve all the problems.

Possible status for each problem: Not started, Started, Attempted Seriously, Solved

Week of May 09, 2022 - May 15, 2022

Click to show table
Problem Link Status Additional Notes
Feb 2022 USACO Gold Redistributing Gifts Not started
Feb 2022 USACO Gold Cow Camp Solved Did not have the idea of "jumping" through the DP like in the solution.
Feb 2022 USACO Gold Moo Network Started Tried sorting the cows by the x-coordinate and then by the y-coordinate. Then, I added possible edges between every 3 cows, and also connected all the groups. This method did not work.

Week of May 02, 2022 - May 08, 2022

Click to show table
Problem Link Status Additional Notes
2021 USACO Dec Gold Paired Up Solved

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.

Week of Apr 25, 2022 - May 01, 2022

Click to show table
Problem Link Status Additional Notes
2021 USACO Dec Gold HILO Solved Solved using 3 segment trees: one which stores the indices i with i > x + 0.5, one which stores the remaining indices not in the original array, and one which stores if there is a HI before a certain LO. I used tags for lazy propagation, and I found that if I wanted to set a section of a segment tree to zero, it wouldn't work because I wanted the tags to be GREATER than zero. Fixed by making the tags default to -1.
2021 USACO Dec Gold Paired Up Not started

Week of Apr 18, 2022 - Apr 24, 2022

Click to show table
Problem Link Status Additional Notes
Codeforces Repetitions Decoding Solved Once I found out I could "reverse" part of the array, I figured out a solution that grouped together the same numbers.

Week of Apr 11, 2022 - Apr 17, 2022

Click to show table
Problem Link Status Additional Notes
Codeforces Repetitions Decoding Not started
Codeforces Finding Zero Solved I noticed that by checking 4 numbers, with 4 queries, you can determine at most two possible positions that can be zero. Using this idea, we can break down n possible numbers into 2 * floor(n / 4) + n mod 4 possible numbers and so on... Missed a lot of cases with a messy implementation, so it took a couple tries to get AC.

Week of Apr 04, 2022 - Apr 10, 2022

Click to show table
Problem Link Status Additional Notes
Codeforces Weight The Tree Solved

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.

Codeforces Repetitions Decoding Not started
Codeforces Finding Zero Not started

Week of Mar 28, 2022 - Apr 03, 2022

Click to show table
Problem Link Status Additional Notes
Codeforces Weight The Tree Seriously attempted 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.
Codeforces Repetitions Decoding Not started
Codeforces Finding Zero Not started

Week of Mar 07, 2022 - Mar 13, 2022

Click to show table
Problem Link Status Additional Notes
2020 USACO December Gold Problem 3 Square Pasture Not started
2020 USACO December Gold Problem 2 Bovine Genetics Started Tried thinking of it, but can't come up with a solution. Decided to add Feb 2021 Gold because they are easier and maybe more of my level.
2021 USACO Feb Gold Problem 1 Stone Game Started Let M be the max value of all a_i. Let gte[j] be the number of values in a_i greater than or equal to j. Then, for all values j between floor(M / 2) + 1 to M, I believe if gte[j] is odd, then this value of j can be used on the first move. I'm tried dealing with values of j from 1 to floor(M / 2), but no progress yet.

Week of Feb 28, 2022 - Mar 06, 2022

Sorry that I didn't make any progress this week.

Click to show table
Problem Link Status Additional Notes
2020 USACO December Gold Problem 3 Square Pasture Not started
2020 USACO December Gold Problem 2 Bovine Genetics Started Tried thinking of it, but can't come up with a solution. Decided to add Feb 2021 Gold because they are easier and maybe more of my level.
2021 USACO Feb Gold Problem 1 Stone Game Started Let M be the max value of all a_i. Let gte[j] be the number of values in a_i greater than or equal to j. Then, for all values j between floor(M / 2) + 1 to M, I believe if gte[j] is odd, then this value of j can be used on the first move. I'm tried dealing with values of j from 1 to floor(M / 2), but no progress yet.

Week of Feb 21, 2022 - Feb 27, 2022

Click to show table
Problem Link Status Additional Notes
2020 USACO December Gold Problem 1 Replication Started I have the idea of floodfill, but when robots replicate, I'm not sure how to expand the floodfill. Also, with the possibility of D not being 1, it is harder to update the floodfill. I tried thinking of brute force, but it's difficult to implement cleanly.
2020 USACO December Gold Problem 2 Bovine Genetics Started Tried thinking of it, but can't come up with a solution. Decided to add Feb 2021 Gold because they are easier and maybe more of my level.
2020 USACO December Gold Problem 3 Square Pasture Not started
2021 USACO Feb Gold Problem 1 Stone Game Started Let M be the max value of all a_i. Let gte[j] be the number of values in a_i greater than or equal to j. Then, for all values j between floor(M / 2) + 1 to M, I believe if gte[j] is odd, then this value of j can be used on the first move. I'm tried dealing with values of j from 1 to floor(M / 2), but no progress yet.
2021 USACO Feb Gold Problem 2 Modern Art 3 Solved I defined dp[i][j] to be the cost of choosing between the range i to j (inclusive). But, I didn't think my dp equation was optimal yesterday, but after running through a few cases today, I realized it was infact optimal.
2021 USACO Feb Gold Problem 3 Count the Cows Solved

Let X represent how the pasture looks for 0 ≤ x, y ≤ 3n for some n. Let O represent an empty pasture for 0 ≤ x, y ≤ 3n for the same n. Then the pasture for 0 ≤ x, y ≤ 3n + 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 3n by 3n grid. We can find n using binary search.

As mentioned earlier, we can split the 3n by 3n grid into smaller 3n - 1 by 3n - 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.

View the Code

Week of Feb 14, 2022 - Feb 20, 2022

Note: sorry for making no progress for 2 weeks. Will try harder this week

Click to show table
Problem Link Status Additional Notes
USACO 2022 January Gold Drought Seriously attempted

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.

USACO 2022 January Gold Farm Updates Started Came up with a O(N^2) solution that for each query, calculates the number of active barns you can visit from each barn using DFS, then finds the barns that are not relevant, and computes the answers for those barns.

Week of Feb 07, 2022 - Feb 13, 2022

Note: I have problems to do for a computer science class, and also school work, so I may have less time...

Click to show table
Problem Link Status Additional Notes
USACO 2022 January Gold Drought Not started
USACO 2022 January Gold Farm Updates Not started

Week of Jan 31, 2022 - Feb 06, 2022

Didn't spend much time working on computer science...

Week of Jan 24, 2022 - Jan 30, 2022

Note: I have problems to do for a computer science class, and so school work, so I may have less time...

Click to show table
Problem Link Status Additional Notes
2020 USACO December Gold Problem 1 Replication Not started
2020 USACO December Gold Problem 2 Bovine Genetics Not started
2020 USACO December Gold Problem 3 Square Pasture Not started

Week of Jan 17, 2022 - Jan 23, 2022

Click to show table
Problem Link Status Additional Notes
CSES Range Update Queries Not started Solve if there is time. Read on BIT and Segment Tree.
CSES Distinct Values Queries Not started Solve if there is time. Read on BIT and Segment Tree.
Kattis Robot Turtles Solved
USACO Tractor (2013 Feb Silver) Not started
USACO Moocast (2016 Dec Silver) Solved I binary searched on the value of X, and used DSU to merge the components of two points, if the distance between the two points ≤ sqrt(X). The problem was that I checked the size of the component of 0, but the root of the DSU doesn't have to be 0.

Week of Jan 10, 2022 - Jan 16, 2022

I have to finish some homework for a computer science class. I will try to finish that, and will assign problems if there is time.

Update: Will assign problems for now.

Click to show table
Problem Link Status Additional Notes
Online Judge 10003 Cutting Sticks Solved
My solution First, sort the cuts and let the cuts in the input be cuts[1], cuts[2], ..., cuts[n]. Define cuts[0] = 0 and cuts[n + 1] = L. I defined cost[i][j] to be the cost of placing the cuts between i and j (inclusive) between cuts[i - 1] and cuts[j + 1]. Then cost[i][j] = min(cuts[j + 1] - cuts[i - 1] + cost[i][k - 1] + cost[k + 1][j]) for all possible k. (If k - 1 < i or k + 1 > i, ignore it.)
However, this solution got wrong answer.

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.

USACO Talent Show Seriously Attempted

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.

CS Academy Mountain Time Not started
USACO Lasers and Mirrors Solved Wrote a complicated solution. See the file. The mistakes I made were not including lines 25 and 26:

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

and on line 49 where I used N instead of points.size();
USACO Shortcut Solved My original solution stored the shortest path from the barn to each vertex in a vector. This was too inefficient, and I fixed it by storing the next node in the optimal path of each node. This is similar to the O(Mlog N + N^2) solution on USACO.
USACO Ski Course Rating Not started

Week of Jan 03, 2022 - Jan 09, 2022

Reflection: I think the problems I chose this week were too hard. I will try to do easier problems, and also not cram everything onto one weekend. I will look back on these problems, but probably in a month or so, since I don't understand enough to solve them.

Click to show table
Problem Link Status Additional Notes
Online Judge 10003 Cutting Sticks Seriously attempted
My solution First, sort the cuts and let the cuts in the input be cuts[1], cuts[2], ..., cuts[n]. Define cuts[0] = 0 and cuts[n + 1] = L. I defined cost[i][j] to be the cost of placing the cuts between i and j (inclusive) between cuts[i - 1] and cuts[j + 1]. Then cost[i][j] = min(cuts[j + 1] - cuts[i - 1] + cost[i][k - 1] + cost[k + 1][j] for all possible k. (If k - 1 < i or k + 1 > i, ignore it.)
However, this solution got wrong answer.
USACO Talent Show Seriously Attempted EDIT: may try to understand this week. 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).
USACO Ski Course Rating Not started
JOI 2018 Commuter Pass Not started
USACO Moortal Cowmbat Seriously Attempted Took a while to come up with a solution for this problem. First, I use Floyd-Warshall to find the minimum cost to change from button i to button j. Then, I found the minimum cost of changing the first i buttons in the combo to a letter j. After that, I let dp[i] be the minimum cost for the first i letters. The equation was dp[i] = min(dp[i - K] + cost, dp[i - K - 1] + cost, dp[i - K - 2] + cost, ...). Here, cost represents the cost to change the last letters. This is O(NK) and is therefore too slow.

Week of Dec 27, 2021 - Jan 02, 2022

Click to show table
Problem Link Status Additional Notes
NOI 18 Knapsack Solved Used the USACO Guide solution for this problem. Couldn't think of anything efficient, because I focused on the bonds of K instead of the bonds on S.
USACO Cow Poetry Solved See my code here. I made the mistake of making ways_group too small. The size of that should be M. I also used unordered_map and unordered_set because of the solution, but I don't think it had that big of an impact. Originally, I did a O(NM) solution by updating ways_group for every possible group size, and that TLE'd, but I think there was a constant factor from modpow that made it too slow.
CSES Edit Distance Solved Had to use the editorial. I didn't have any idea where to start originally. When I tried implementing the editorial solution, I messed up by leaving dp[i][0] undefined for i ≥ 1.
Online Judge 10003 Cutting Sticks Seriously attempted
My solution First, sort the cuts and let the cuts in the input be cuts[1], cuts[2], ..., cuts[n]. Define cuts[0] = 0 and cuts[n + 1] = L. I defined cost[i][j] to be the cost of placing the cuts between i and j (inclusive) between cuts[i - 1] and cuts[j + 1]. Then cost[i][j] = min(cuts[j + 1] - cuts[i - 1] + cost[i][k - 1] + cost[k + 1][j] for all possible k. (If k - 1 < i or k + 1 > i, ignore it.)
However, this solution got wrong answer.
USACO Talent Show Seriously Attempted EDIT: may try to understand this week. 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).
USACO MooTube Solved Should read about DSU before attempting. Another good DSU resource. For this problem, I used the solution. I had the idea of sorting the queries by largest weights (probably because I had done this problem before), but I didn't think to sort the edges, and this prevented me from solving the problem.
USACO Wormhole Sort Solved Used this solution on USACO guide. The DSU solution I thought of was adding an edge, and then checking if every node has the same parent. However, the correct solution is to go through each node i and its parent p[i] and add edges until both have the same parent. Additionally, I made cycles which are formed by connecting i to p[i], but it is not needed to check every node in a cycle having the same parent. Will need to do more dsu problems this week (if possible) or next week.
USACO Ski Course Rating Not started
CSES New Road Queries Not started
CSES Investigation Solved Should read about shortest paths before attempting. At first, I didn't think abou the problem seriously, so I took a quick look at the USACO guide solution and realized to use Dijsktra. I likely would have realized this as well, if I seriously thought of the problem. I got wrong answer on my first submission because I didn't read that the flights are ONE-WAY.
JOI 2018 Commuter Pass Not started
JOI 2021 Robot Not started
USACO Why Did the Cow Cross the Road (Gold) Solved Used the solution for this problem. I originally thought of using dijsktra, but I only moved to the 4 adjacent cells. This solution failed on the sample test case. I didn't realize that the proper solution was to move "3 moves" at a time. (One move is moving from a cell to its 4 adjacent cells.) Note that by moving "3 moves" at a time, it is possible to move from a cell to its adjacent cell. We move 3 moves at a time because Bessie eats every 3 fields she visits. If the distance to the end is less than two, Bessie doesn't need to eat again, so we can just update the answer.
CSES Flight Routes Solved I used the usaco.guide solution. I thought of using dijkstra for this problem, and maintaining a priority queue/multiset for each node. I thought this was too slow, but the priority queue for each node has size of at most 10... When implementing the solution, I skipped past a point without popping the priority queue, even though the priority queue should be popped. Also, I printed integers instead of long longs when printing out the answer.
USACO Moortal Cowmbat Not started

Week of Dec 20, 2021 - Dec 26, 2021

Click to show table
Problem Link Status Additional Notes
USACO Teamwork (2018 December Gold) Solved
USACO Snakes (2019 US Open Gold) Solved
USACO Time is Mooney (2020 January Gold) Solved Thought of solving the problem by noticing that we can only go through cycles that start and end at 1. However, I wasn't able to get a full solution still. I then looked online and realized that the trip can last at most 1000 days, but my original solution still wasn't going anywhere. I decided to use the solution on USACO.
CSES Array Description Solved
CSES Counting Towers Solved I used this comment on the Codeforces CSES DP editorial to solve this problem. Originally, I tried thinking of the number of ways to build a 1 by n tower, but it did not work.
CSES Coin Combinations I Solved
CSES Coin Combinations II Solved Used the USACO Guide solution. My original solution used ways[i][j] to represent the number of ways to get a coin sum of i using the first j coins (sorted). This is too slow, and a better way to do this is to compute ways[i] (the number of ordered ways to get a coin sum of i) for 0 ≤ i ≤ x using on the first j - 1 coins and then updating ways[i] for 0 ≤ i ≤ x with the jth coin.
CSES Removing Digits Solved
USACO Circular Barn Revisited Solved Originally thought of solving by considering all possible doors to choose, but that was too slow. Then, I thought of doing dp by the number of doors we have, but I didn't consider converting this problem into 2D and rotating to get the correct cases. I used the USACO Solution.
IOI 2004 Phidias Solved I thought of choosing one of the desired plates to remove and then somehow doing dp on that. The correct solution on USACO guide does dp based on the size of the rectangle. It works since each a slab of marble must have one vertical cut or one horizontal cut. So a marble of size n by m must be made up one of the following:
  • 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
where 1 ≤ a ≤ n - 1 and 1 ≤ b ≤ m - 1.
USACO Taming the Herd Solved
USACO Moortal Cowmbat Started Had no idea on how to find the minimum cost to from letter i to letter j. Need to use Floyd-Warshall, which I will do problems of next week.
USACO Talent Show Seriously Attempted 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).
NOI 18 Knapsack Not started
USACO Cow Poetry Not started
CSES Edit Distance Not started
Online Judge 10003 Cutting Sticks Not started

Week of Dec 13, 2021 - Dec 19, 2021

Click to show table
Problem Link Status Additional Notes
USACO Haybale Stacking Solved Did a prefix sum solution by finding the number of haybales in spot i using prefix sums. Got seg fault probably because the stack size is too small? I changed from using arrays to vector and it worked fine... Probably an issue with SPOJ.
CSES Array Division Solved I binary searched on the maximum sum of all subarrays. To check if a certain sum is possible, I made a new subarray every time the current subarray exceeded the sum we are checking. I didn't consider the case where a value in a[i] is greater than the sum we are checking.
Codeforces The Meeting Place Cannot Be Changed Solved Had some trouble implementing the eps binary search. I think the problem I had was using double instead of long double.
USACO The Great Revegetation Solved The answer to this problem was 2 to the power of the number of connected components. I output zero if there is an edge from cows u to v that requires u and v to have DIFFERENT colors and the SAME color. However, there could be a cycle which also makes the answer zero. So, I needed to try to paint the cows and see if there were any contradictions.
USACO Why Did the Cow Cross the Road III Solved

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.

USACO Dance Mooves Solved Solved by finding the cycle each cow was in. Then, found the cows the cows in a cycle can visit.
USACO No Time to Paint Solved Solved by using prefix and suffix sums. In the prefix sums, I found the cost from the beginning up to index i, and in the suffix sums, I found the cost from the end to index i. If we saw a color earlier, then we do not need to use another stroke as long as there IS NOT a smaller color in the way.
USACO Spaced Out Solved There are two cases. First case: in each row, every other column is occupied. Second case: in each column, every other row is occupied.
USACO Comfortable Cows Solved I basically reimplemented the USACO solution. That solution uses a queue for each cow we add. For each cow we add, we check if it has 3 adjacent cows and add a cow as necessary. We also check each of its adjacent cows to see if more cows need to be added. I thought in the most extreme case, the cows would be a diamond centered at the origin, but it should be a diamond centered at (500, 500).
USACO Year of the Cow Solved
USACO Just Green Enough Solved I thought of computing the number of subgrids where every cell is at least 100 and the number of subgrids where every cell is at least 101. However, I didn't know how to compute these numbers. To do this, you consider the subgrids that start at row i and row j. You check each column between rows i and j to see if each value is at least 100 or 101. A group of x consecutive columns contributes x * (x + 1) / 2 subgrids to the answer.
USACO Cowntagion Solved
USACO Rectangular Pasture Solved Tried finding the number of subsets enclosed by rectangles that start and end at a certain x-coordinate. But, I thought of using sweep line because I remember that being the solution for some reason, but the actual solution uses prefix sums.
USACO Stuck in a Rut Solved Didn't want to implement the old solution I learned. I read the USACO solution, and I think it is the cleanest. It stops the cows as early as possible, so we can update the answer without using DFS.

Week of Dec 06, 2021 - Dec 12, 2021

Click to show table
Problem Link Status Additional Notes
USACO Haybale Stacking Not started
CSES Movie Festival II Solved I had the idea of having the first person watch the movies in an optimal manner, then the second person doing the same thing and so on. The correct solution is to assign whoever is available the movie that ends the earliest. To do this, use a multiset with the ending times of everyone, and try the person that ends the earliest.
CSES Flight Routes Check Solved For this problem, I checked if each node had a parent and a child. I also checked if you can visit each node starting at 1. This managed to pass every test case except one, but it is wrong. To do it correctly, see the USACO guide solution.
USACO Wormhole Sort Solved As given in the problem input, p[i] is the ith cow. I let i → p[i] be an edge. Then, the permutation is a graph made up of multiple cycles that are unconnected. Then, I binary searched on the answer. From the swaps, I made a graph where a[i] → b[i] was an edge if w[i] is larger than or equal to the answer we are checking. This was an UNDIRECTED graph, and I FORGOT to add b[i] → a[i] as an edge. To find the answer, I found the component each node was in in the undirected graph created by the edges a[i] → b[i] for 1 ≤ i ≤ M. Each node in a cycle must have the same component. The USACO solution is similiar to this one and the wording is more clear.
USACO High Card Low Card Solved Wasn't sure where to begin initally, so I created a random test case and got the intution of the greedy algorithm.

Week of Nov 29, 2021 - Dec 05, 2021

Click to show table
Problem Link Status Additional Notes
USACO Splitting the Field Seriously Attempted My solution finds the max y-coordinate given each x-coordinate. This allows us to have a fence up to one x-coordinate and the remaining x-coordinates are another fence. Note I have a vector with all the x-coordinates that is generated using a set. But, I'm getting WA on 2 test cases.
USACO Haybale Stacking Not started
Atcoder GCD on Blackboard Solved
USACO Why Did the Cow Cross the Road Solved

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.

USACO Social Distancing Solved Binary searched on the value of D. My check function had a minor error. It only updated the location of a cow IF there was no interval for the cow to be in. It only needed me to swap the position of ONE line of code to fix it.
USACO Sabotage Started Had no idea on how to solve this problem within the time limits. Came up with a O(N^2) but not an O(N) or O(NlogN). Do not current understand the solution, and I feel it is too hard.
USACO Angry Cows Started Tried getting a solution similar to the silver version of the problem, but it does not work. USACO Guide says this is a hard problem, so it may not be worth doing in my current level.

Week of Nov 22, 2021 - Nov 28, 2021

Click to show table
Problem Link Status Additional Notes
USACO Cowntagion Solved The optimal solution is to double the cows in the current farm before moving the cows in the adjacent farms of the current farm.
USACO Rectangular Pasture Not started
USACO Stuck in a Rut Not started
CSES Tasks and Deadlines Solved I didn't understand why my solution of sorting the task durations in increasing order worked. Page 71 of the pdf of the CSES book gives a reason for why the solution works. Basically, if you have a task with duration a BEFORE a task with duration b so that a > b, swapping the tasks allows us to loose b points (from the longer task) and gain a points (from the shorter task).
CSES Movie Festival II Not started
CSES Collecting Numbers Solved
CSES Static Range Sum Queries Solved
CSES Longest Flight Route Started

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.

USACO Rental Service Solved Forgot to consider that the maximum milk that can be sold may be LESS than the milk the cows can produce in total.
USACO Mountain View Solved Didn't consider the case where two mountains STARTED at the same point and covered each other.

Week of Nov 15, 2021 - Nov 21, 2021

Click to show table
Problem Link Status Additional Notes
USACO Cowntagion Not started
USACO Rectangular Pasture Not started
USACO Stuck in a Rut Not started
CSES Tasks and Deadlines Not started
CSES Movie Festival II Not started
CSES Collecting Numbers Not started
CSES Static Range Sum Queries Not started

Week of Nov 08, 2021 - Nov 14, 2021

Click to show table
Problem Link Status Additional Notes
USACO Berry Picking Solved My original solution was to do a binary search on the answer, and keep the numbers in the buckets as close as possible. However, this is not enough to be the correct solution
CSES Round Trip Solved The problem asked for detecting cycles in undirected graphs, so I used this resource. However, to output the entire working path, I had to have a global path variable that updates when I visit a vertex, and deletes after it finishes visiting the vertex.
CSES Subordinates Solved
USACO Cowntagion Not started
USACO Rectangular Pasture Not started
USACO Stuck in a Rut Not started