bkf2020 website mirrored here.
You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

#### 1731 lines 63 KiB Raw Permalink Blame History

 `` `` `` ` ` ` ` ` ` ` ` ` Computer Science Log -- Be kind for 2020 (bkf2020)'s Website!` ` ` `` `` `
` `

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` ` ` `
Feb 2022 USACO Gold Redistributing GiftsNot started
Feb 2022 USACO Gold Cow CampSolved` ` Did not have the idea of "jumping" through the DP like in the solution.` `
Feb 2022 USACO Gold Moo NetworkStarted` ` 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` ` ` `
2021 USACO Dec Gold Paired UpSolved` `

` ` 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` ` ` `
2021 USACO Dec Gold HILOSolved` ` 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 UpNot started
` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `

Week of Apr 18, 2022 - Apr 24, 2022

` `
` ` Click to show table` ` ` `
Codeforces Repetitions DecodingSolved` ` 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` ` ` `
Codeforces Repetitions DecodingNot started
Codeforces Finding ZeroSolved` ` 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` ` ` `
Codeforces Weight The TreeSolved` `

` ` 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 DecodingNot started
Codeforces Finding ZeroNot started
` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `

Week of Mar 28, 2022 - Apr 03, 2022

` `
` ` Click to show table` ` ` `
Codeforces Weight The TreeSeriously 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 DecodingNot started
Codeforces Finding ZeroNot started
` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `

Week of Mar 07, 2022 - Mar 13, 2022

` `
` ` Click to show table` ` ` `
2020 USACO December Gold Problem 3 Square PastureNot started
2020 USACO December Gold Problem 2 Bovine GeneticsStarted` ` 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 GameStarted` ` 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` ` ` `
2020 USACO December Gold Problem 3 Square PastureNot started
2020 USACO December Gold Problem 2 Bovine GeneticsStarted` ` 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 GameStarted` ` 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` ` ` `
2020 USACO December Gold Problem 1 ReplicationStarted` ` 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 GeneticsStarted` ` 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 PastureNot started
2021 USACO Feb Gold Problem 1 Stone GameStarted` ` 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 3Solved` ` 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 CowsSolved` `

` ` 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` ` ` `
USACO 2022 January Gold DroughtSeriously 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 UpdatesStarted` ` 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` ` ` `
USACO 2022 January Gold DroughtNot started
USACO 2022 January Gold Farm UpdatesNot 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` ` ` `
2020 USACO December Gold Problem 1 ReplicationNot started
2020 USACO December Gold Problem 2 Bovine GeneticsNot started
2020 USACO December Gold Problem 3 Square PastureNot started
` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `

Week of Jan 17, 2022 - Jan 23, 2022

` `
` ` Click to show table` ` ` `
CSES Range Update QueriesNot started` ` Solve if there is time. Read on BIT and Segment Tree.` `
CSES Distinct Values QueriesNot started` ` Solve if there is time. Read on BIT and Segment Tree.` `
Kattis Robot TurtlesSolved
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` ` ` `
Online Judge 10003 Cutting SticksSolved` `
` ` 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 ShowSeriously 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.` `

` `
USACO Lasers and MirrorsSolved` ` 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 ShortcutSolved` ` 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 RatingNot 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` ` ` `
Online Judge 10003 Cutting SticksSeriously 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 ShowSeriously 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 RatingNot started
JOI 2018 Commuter PassNot started
USACO Moortal CowmbatSeriously 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` ` ` `
NOI 18 KnapsackSolved` ` ` ` 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 PoetrySolved` ` 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 DistanceSolved` ` 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 SticksSeriously 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 ShowSeriously 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 MooTubeSolved` ` 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 SortSolved` ` ` ` 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 RatingNot started
CSES InvestigationSolved` ` 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 PassNot started
JOI 2021 RobotNot 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 RoutesSolved` ` 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 CowmbatNot started
` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `

Week of Dec 20, 2021 - Dec 26, 2021

` `
` ` Click to show table` ` ` `
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 DescriptionSolved
CSES Counting TowersSolved` ` 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 ISolved
CSES Coin Combinations IISolved` ` 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 DigitsSolved
USACO Circular Barn RevisitedSolved` ` 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 PhidiasSolved` ` 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 HerdSolved
USACO Moortal CowmbatStarted` ` 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 ShowSeriously 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 KnapsackNot started
USACO Cow PoetryNot started
CSES Edit DistanceNot started
Online Judge 10003 Cutting SticksNot started
` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `

Week of Dec 13, 2021 - Dec 19, 2021

` `
` ` Click to show table` ` ` `
USACO Haybale StackingSolved` ` 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 DivisionSolved` ` 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 ChangedSolved` ` Had some trouble implementing the eps binary search.` ` I think the problem I had was using double` ` instead of long double.` `
USACO The Great RevegetationSolved` ` 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 IIISolved` `

` ` 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 MoovesSolved` ` Solved by finding the cycle each cow was in.` ` Then, found the cows the cows in a cycle can visit.` `
USACO No Time to PaintSolved` ` 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 OutSolved` ` 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 CowsSolved` ` 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 CowSolved
USACO Just Green EnoughSolved` ` 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 CowntagionSolved
USACO Rectangular PastureSolved` ` 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 RutSolved` ` 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` ` ` `
` ` ` ` 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` ` ` `
` ` 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 StackingNot started
Atcoder GCD on BlackboardSolved
USACO Why Did the Cow Cross the RoadSolved` `

` ` 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 DistancingSolved` ` 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 SabotageStarted` ` 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 CowsStarted` ` 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` ` ` `
USACO CowntagionSolved` ` 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 PastureNot started
USACO Stuck in a RutNot started
CSES Tasks and DeadlinesSolved` ` 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 IINot started
CSES Static Range Sum QueriesSolved
CSES Longest Flight RouteStarted` `

` ` 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 ServiceSolved` ` 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 ViewSolved` ` 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` ` ` `
USACO CowntagionNot started
USACO Rectangular PastureNot started
USACO Stuck in a RutNot started
CSES Movie Festival IINot started
CSES Collecting NumbersNot started
CSES Static Range Sum QueriesNot started
` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `

Week of Nov 08, 2021 - Nov 14, 2021

` `
` ` Click to show table` ` ` `
USACO Berry PickingSolvedMy 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 TripSolved` ` 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 SubordinatesSolved
USACO CowntagionNot started
USACO Rectangular PastureNot started
USACO Stuck in a RutNot started
` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` ` `
` `

` ` home` `

` `

` ` all code/content on this website is under CC0` ` unless otherwise stated.` `

` `

` ` other projects I have may have different licenses` `

` `
` `` ``` ``` ``` ```