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

<!DOCTYPE html>
<html>
<head>
<meta charset="utf-8" />
<meta name="HandheldFriendly" content="true" />
<meta name="MobileOptimized" content="320" />
<meta name="viewport" content="width=device-width, initial-scale=1.0">
<title>Computer Science Log -- Be kind for 2020 (bkf2020)'s Website!</title>
<link rel="stylesheet" href="style.css">
</head>
<body>
<header>
<h1>Be kind for 2020 (bkf2020)'s Computer science log</h1>
<p>
<a href="/">home</a>
</p>
</header>
<article>
<h2>What is this?</h1>
<p>
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.
</p>
<p>
Possible status for each problem:
<mark class="ns">Not started</mark>,
<mark class="s">Started</mark>,
<mark class="sa">Attempted Seriously</mark>,
<mark class="so">Solved</mark>
</p>
<!-- Template
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
</tr>
<tr>
<th><a href=""></a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href=""></a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href=""></a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href=""></a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href=""></a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href=""></a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
</table>
</details>
-->
<h2>Week of May 09, 2022 - May 15, 2022</h2>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1209">Feb 2022 USACO Gold Redistributing Gifts</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1210">Feb 2022 USACO Gold Cow Camp</a></th>
<th class="so">Solved</th>
<th>
Did not have the idea of "jumping" through the DP like in the solution.
</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1211">Feb 2022 USACO Gold Moo Network</a></th>
<th class="s">Started</th>
<th>
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.
</th>
</tr>
</table>
</details>
<h2>Week of May 02, 2022 - May 08, 2022</h2>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1161">2021 USACO Dec Gold Paired Up</a></th>
<th class="so">Solved</th>
<th>
<p>
First, I read the first sentence of
<a href="http://usaco.org/current/data/sol_prob1_gold_dec21.html">the solution</a>
to get a hint on how to solve this problem.
<q>
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.
</q>
</p>
<p>
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 <var>i</var> at an EVEN index,
then you must pair up cows <var>i - 1</var> and <var>i + 1</var>. 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).
</p>
<p>
Similarly, I understood that if there are an EVEN number of cows already unpaired, and
you leave an unpaired cow <var>i</var> at an ODD index,
then you must pair up cows <var>i - 1</var> and <var>i + 1</var>. 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).
</p>
<p>
This approach lets you transition <code>dp[i][j] = dp[i + 1][j]</code> instead of
<code>dp[i][j] = dp[i + 2][j]</code> (which is what I did in my original solution).
</p>
<p>
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.
</p>
</th>
</tr>
</table>
</details>
<h2>Week of Apr 25, 2022 - May 01, 2022</h2>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1162">2021 USACO Dec Gold HILO</a></th>
<th class="so">Solved</th>
<th>
Solved using 3 segment trees: one
which stores the indices i with
i &gt; 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.
</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1161">2021 USACO Dec Gold Paired Up</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
</table>
</details>
<h2>Week of Apr 18, 2022 - Apr 24, 2022</h2>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
</tr>
<tr>
<th><a href="https://codeforces.com/problemset/problem/1641/B">Codeforces Repetitions Decoding</a></th>
<th class="so">Solved</th>
<th>
Once I found out I could "reverse" part of the array, I figured out a solution
that grouped together the same numbers.
</th>
</tr>
</table>
</details>
<h2>Week of Apr 11, 2022 - Apr 17, 2022</h2>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
</tr>
<tr>
<th><a href="https://codeforces.com/problemset/problem/1641/B">Codeforces Repetitions Decoding</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="https://codeforces.com/problemset/problem/1634/D">Codeforces Finding Zero</a></th>
<th class="so">Solved</th>
<th>
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 <code>2 * floor(n / 4) + n mod 4</code> possible numbers and so on...
Missed a lot of cases with a messy implementation, so it took a couple tries to get AC.
</th>
</tr>
</table>
</details>
<h2>Week of Apr 04, 2022 - Apr 10, 2022</h2>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
</tr>
<tr>
<th><a href="https://codeforces.com/problemset/problem/1646/D">Codeforces Weight The Tree</a></th>
<th class="so">Solved</th>
<th>
<p>
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.
</p>
<p>
Found a failing test case using <a href="https://cfstress.com/">CF Stress</a>.
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.
</p>
</th>
</tr>
<tr>
<th><a href="https://codeforces.com/problemset/problem/1641/B">Codeforces Repetitions Decoding</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="https://codeforces.com/problemset/problem/1634/D">Codeforces Finding Zero</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
</table>
</details>
<h2>Week of Mar 28, 2022 - Apr 03, 2022</h2>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
</tr>
<tr>
<th><a href="https://codeforces.com/problemset/problem/1646/D">Codeforces Weight The Tree</a></th>
<th class="sa">Seriously attempted</th>
<th>
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.
</th>
</tr>
<tr>
<th><a href="https://codeforces.com/problemset/problem/1641/B">Codeforces Repetitions Decoding</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="https://codeforces.com/problemset/problem/1634/D">Codeforces Finding Zero</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
</table>
</details>
<h2>Week of Mar 07, 2022 - Mar 13, 2022</h2>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1067">2020 USACO December Gold Problem 3 Square Pasture</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1066">2020 USACO December Gold Problem 2 Bovine Genetics</a></th>
<th class="s">Started</th>
<th>
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.
</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1113">2021 USACO Feb Gold Problem 1 Stone Game</a></th>
<th class="s">Started</th>
<th>
Let M be the max value of all a_i. Let <code>gte[j]</code> 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
<code>gte[j]</code> 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.
</th>
</tr>
</table>
</details>
<h2>Week of Feb 28, 2022 - Mar 06, 2022</h2>
<p>Sorry that I didn't make any progress this week.</p>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1067">2020 USACO December Gold Problem 3 Square Pasture</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1066">2020 USACO December Gold Problem 2 Bovine Genetics</a></th>
<th class="s">Started</th>
<th>
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.
</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1113">2021 USACO Feb Gold Problem 1 Stone Game</a></th>
<th class="s">Started</th>
<th>
Let M be the max value of all a_i. Let <code>gte[j]</code> 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
<code>gte[j]</code> 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.
</th>
</tr>
</table>
</details>
<h2>Week of Feb 21, 2022 - Feb 27, 2022</h2>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1065">2020 USACO December Gold Problem 1 Replication</a></th>
<th class="s">Started</th>
<th>
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.
</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1066">2020 USACO December Gold Problem 2 Bovine Genetics</a></th>
<th class="s">Started</th>
<th>
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.
</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1067">2020 USACO December Gold Problem 3 Square Pasture</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1113">2021 USACO Feb Gold Problem 1 Stone Game</a></th>
<th class="s">Started</th>
<th>
Let M be the max value of all a_i. Let <code>gte[j]</code> 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
<code>gte[j]</code> 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.
</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1114">2021 USACO Feb Gold Problem 2 Modern Art 3</a></th>
<th class="so">Solved</th>
<th>
I defined <code>dp[i][j]</code> 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.
</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1115">2021 USACO Feb Gold Problem 3 Count the Cows</a></th>
<th class="so">Solved</th>
<th>
<p>
Let X represent how the pasture looks for 0 &le; x, y &le; 3<sup>n</sup> for some <var>n</var>.
Let O represent an empty pasture for 0 &le; x, y &le; 3<sup>n</sup> for the same <var>n</var>.
Then the pasture for 0 &le; x, y &le; 3<sup>n + 1</sup> looks like this:
</p>
<pre><code>XOX
OXO
XOX</code></pre>
<p>
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.
<u>I DID NOT SOLVE THIS PROBLEM DURING AN OFFICIAL CONTEST</u>.
</p>
<p>
<a href="https://codeberg.org/bkf2020/pages/src/branch/main/cpp/count_visual.cpp">
Code for the script</a>
</p>
<p>
After I wrote the script, I came up with the following idea:
Let <code>num_cows(x, y, d)</code>
count the number of cows from (x, y) to (x + d, y + d).
</p>
<p>
Then, we can enclose all such cows within a
3<sup>n</sup> by 3<sup>n</sup> grid. We
can find n using binary search.
</p>
<p>
As mentioned earlier, we can split the
3<sup>n</sup> by 3<sup>n</sup> grid into
smaller
3<sup>n - 1</sup> by 3<sup>n - 1</sup> grids,
and we can find the places the diagonal intersects
these grids.
</p>
<p>
Thus, we split up the original problem into
many smaller problems.
</p>
<p>
This is a rough outline, but my implemenation
was quit messy. It gets accepted but is
borderline TLE.
</p>
<a href="https://codeberg.org/bkf2020/pages/src/branch/main/cpp/count.cpp">
View the Code</a>
</p>
</th>
</tr>
</table>
</details>
<h2>Week of Feb 14, 2022 - Feb 20, 2022</h2>
<p>Note: sorry for making no progress for 2 weeks. Will try harder this week</p>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
<tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1185">USACO 2022 January Gold Drought</a></th>
<th class="sa">Seriously attempted</th>
<th>
<p>
I only can solve this problem if N is even.
</p>
<p>
To do this, I let <code>dp[i][a]</code> be the number of ordered tuples
<code>(h[i], ..., h[N])</code> from cows i to N with <code>h[i] &ge; a</code>.
</p>
<p>
Then, it is easy to get the values for <code>dp[N - 2][a]</code> (2 cow case).
After that I loop through values of <code>i</code> from <code>N - 4</code> to <code>0</code>
(decreasing by 2 each time), and for each value of <code>i</code>,
I loop through values of <code>a</code> from <code>H[i]</code> to <code>0</code>
(decreasing by 1 each time). I set <code>dp[i][a] = dp[i][a + 1]</code>
The cow at <code>i + 1</code> has a value <code>b</code> and for each value of <code>a</code>,
I loop through values of <code>b</code> from <code>a</code> to <code>H[i + 1]</code>.
For each value of <code>b</code>, I update
<code>dp[i][a] += dp[i + 2][0] - dp[i + 2][max(H[i + 2] - b + a + 1, 0)]</code>.
</p>
<p>
What we do here is make cows <code>i + 1</code> and <code>i + 2</code> equal to <code>a</code>
by subtracting <code>b - a</code> from them. Thus, cow <code>i + 2</code> can be at most
<code>H[i + 2] - b + a</code>. If <code>H[i + 2] - b + a + 1</code> is negative, I just use 0 instead.
</p>
<p>
The mistake I made was that <code>dp[i][a]</code> could be negative because of the mod. (I found out
with the USACO test data.) Thus, I need to do <code>dp[i][a] += MOD</code> to combat this issue.
</p>
<p>
I only pass the sample input if N is odd.
</p>
</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1186">USACO 2022 January Gold Farm Updates</a></th>
<th class="s">Started</th>
<th>
Came up with a <code>O(N^2)</code> 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.
</th>
</tr>
</table>
</details>
<h2>Week of Feb 07, 2022 - Feb 13, 2022</h2>
<p>Note: I have problems to do for a computer science class, and also school work, so I may have less time...</p>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
<tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1185">USACO 2022 January Gold Drought</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1186">USACO 2022 January Gold Farm Updates</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
</table>
</details>
<h2>Week of Jan 31, 2022 - Feb 06, 2022</h2>
<p>Didn't spend much time working on computer science...</p>
<h2>Week of Jan 24, 2022 - Jan 30, 2022</h2>
<p>Note: I have problems to do for a computer science class, and so school work, so I may have less time...</p>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
<tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1065">2020 USACO December Gold Problem 1 Replication</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1066">2020 USACO December Gold Problem 2 Bovine Genetics</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1067">2020 USACO December Gold Problem 3 Square Pasture</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
</table>
</details>
<h2>Week of Jan 17, 2022 - Jan 23, 2022</h2>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
<tr>
<tr>
<th><a href="https://cses.fi/problemset/task/1651">CSES Range Update Queries</a></th>
<th class="ns">Not started</th>
<th>
Solve if there is time. Read on BIT and Segment Tree.
</th>
</tr>
<tr>
<th><a href="https://cses.fi/problemset/task/1734">CSES Distinct Values Queries</a></th>
<th class="ns">Not started</th>
<th>
Solve if there is time. Read on BIT and Segment Tree.
</th>
</tr>
<tr>
<th><a href="https://open.kattis.com/problems/robotturtles">Kattis Robot Turtles</a></th>
<th class="so">Solved</th>
<th></th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=245">USACO Tractor (2013 Feb Silver)</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=669">USACO Moocast (2016 Dec Silver)</a></th>
<th class="so">Solved</th>
<th>
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 &le; 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.
</th>
</tr>
</table>
</details>
<h2>Week of Jan 10, 2022 - Jan 16, 2022</h2>
<p>
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.
</p>
<p>
<b>Update:</b> Will assign problems for now.
</p>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
</tr>
<tr>
<th><a href="https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=944">Online Judge 10003 Cutting Sticks</a></th>
<th class="so">Solved</th>
<th>
<details>
<summary>My solution</summary>
First, sort the cuts and let the cuts in the input
be <code>cuts[1], cuts[2], ..., cuts[n]</code>.
Define <code>cuts[0] = 0</code> and <code>cuts[n + 1] = L</code>.
I defined <code>cost[i][j]</code> to be the cost
of placing the cuts between i and j (inclusive) between
<code>cuts[i - 1]</code> and <code>cuts[j + 1]</code>.
Then <code>cost[i][j] = min(cuts[j + 1] - cuts[i - 1] + cost[i][k - 1] + cost[k + 1][j])</code>
for all possible k. (If <code>k - 1 &lt; i</code> or <code>k + 1 &gt; i</code>, ignore it.)
</details>
However, this solution got wrong answer.
<p>
<u>Update:</u> After talking to another person, I redefined <code>cost[i][j]</code>
to be the cost of performing all cuts between positions
<code>cuts[i]</code> and <code>cuts[j]</code> on the piece of wood.
This caused the transition equation to become
<code>cost[i][j] = min(cuts[j] - cuts[i] + cost[i][k] + cost[k][j])</code>
for all possible k.
</p>
</th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=839">USACO Talent Show</a></th>
<th class="sa">Seriously Attempted</th>
<th>
<p>
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
<a href="http://www.usaco.org/current/data/sol_talent_gold_open18.html">
the USACO solution</a>, but I don't understand why <code>dp[k1]</code>
will always have the optimal value, because <code>dp[k]</code> can be updated
and it doesn't guarantee <code>dp[k1]</code> gets updated.
I believe if <code>dp[k]</code> can get updated by a cow with weight w,
<code>dp[k1]</code> can get updated for the same cow with weight w by using
<code>dp[k1 - w]</code> (or <code>dp[W]</code> if k1 = W).
</p>
<p>
<u>Update:</u> After talking to another person, I realized that
<code>dp[k1]</code> shouldn't get updated by the same cow that
<code>dp[k]</code> gets updated by. Still need to finish implementing this problem.
</p>
</th>
</tr>
<tr>
<th><a href="https://csacademy.com/contest/archive/task/mountain-time">CS Academy Mountain Time</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=671">USACO Lasers and Mirrors</a></th>
<th class="so">Solved</th>
<th>
Wrote a complicated solution. See <a href="https://codeberg.org/bkf2020/pages/src/branch/main/cpp/lasers.cpp">
the file</a>.
The mistakes I made were not including lines
25 and 26:
<p>
<code>
points.push_back({xl, yl});
points.push_back({xb, yb});
</code>
</p>
and on line 49 where I used <code>N</code>
instead of <code>points.size();</code>
</th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=899">USACO Shortcut</a></th>
<th class="so">Solved</th>
<th>
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 <a href="http://www.usaco.org/current/data/sol_shortcut_gold_jan19.html">
the <code>O(Mlog N + N^2)</code> solution on USACO</a>.
</th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=384">USACO Ski Course Rating</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
</table>
</table>
</table>
</details>
<h2>Week of Jan 03, 2022 - Jan 09, 2022</h2>
<details>
<p>
<b>Reflection:</b>
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.
</p>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
</tr>
<tr>
<th><a href="https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=944">Online Judge 10003 Cutting Sticks</a></th>
<th class="sa">Seriously attempted</th>
<th>
<details>
<summary>My solution</summary>
First, sort the cuts and let the cuts in the input
be <code>cuts[1], cuts[2], ..., cuts[n]</code>.
Define <code>cuts[0] = 0</code> and <code>cuts[n + 1] = L</code>.
I defined <code>cost[i][j]</code> to be the cost
of placing the cuts between i and j (inclusive) between
<code>cuts[i - 1]</code> and <code>cuts[j + 1]</code>.
Then <code>cost[i][j] = min(cuts[j + 1] - cuts[i - 1] + cost[i][k - 1] + cost[k + 1][j]</code>
for all possible k. (If <code>k - 1 &lt; i</code> or <code>k + 1 &gt; i</code>, ignore it.)
</details>
However, this solution got wrong answer.
</th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=839">USACO Talent Show</a></th>
<th class="sa">Seriously Attempted</th>
<th>
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
<a href="http://www.usaco.org/current/data/sol_talent_gold_open18.html">
the USACO solution</a>, but I don't understand why <code>dp[k1]</code>
will always have the optimal value, because <code>dp[k]</code> can be updated
and it doesn't guarantee <code>dp[k1]</code> gets updated.
I believe if <code>dp[k]</code> can get updated by a cow with weight w,
<code>dp[k1]</code> can get updated for the same cow with weight w by using
<code>dp[k1 - w]</code> (or <code>dp[W]</code> if k1 = W).
</th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=384">USACO Ski Course Rating</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="https://oj.uz/problem/view/JOI18_commuter_pass">JOI 2018 Commuter Pass</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=971">USACO Moortal Cowmbat</a></th>
<th class="sa">Seriously Attempted</th>
<th>
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 <code>dp[i]</code> be the minimum cost for the first
i letters. The equation was
<code>dp[i] = min(dp[i - K] + cost, dp[i - K - 1] + cost, dp[i - K - 2] + cost, ...)</code>.
Here, <code>cost</code> represents the cost to change the last letters.
This is O(NK) and is therefore too slow.
</th>
</tr>
</table>
</details>
<h2>Week of Dec 27, 2021 - Jan 02, 2022</h2>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
<tr>
<tr>
<th><a href="https://oj.uz/problem/view/NOI18_knapsack">NOI 18 Knapsack</a></th>
<th class="so">Solved</th>
<th>
<a href="https://usaco.guide/problems/noi-knapsack/solution">
Used the USACO Guide solution for this problem</a>.
Couldn't think of anything efficient, because I focused on the bonds of K
instead of the bonds on S.
</th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=897">USACO Cow Poetry</a></th>
<th class="so">Solved</th>
<th>
See my code <a href="https://codeberg.org/bkf2020/pages/raw/branch/main/cpp/poetry.cpp">here</a>.
I made the mistake of making <code>ways_group</code> too small. The size of that should be M.
I also used <code>unordered_map</code> and <code>unordered_set</code> 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
<code>ways_group</code> for every possible group size, and that TLE'd, but I think there was
a constant factor from <code>modpow</code> that made it too slow.
</th>
</tr>
<tr>
<th><a href="https://cses.fi/problemset/task/1639">CSES Edit Distance</a></th>
<th class="so">Solved</th>
<th>
<a href="https://codeforces.com/blog/entry/70018">Had to use the editorial</a>.
I didn't have any idea where to start originally.
When I tried implementing the editorial solution, I messed up
by leaving <code>dp[i][0]</code> undefined for i &ge; 1.
</th>
</tr>
<tr>
<th><a href="https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=944">Online Judge 10003 Cutting Sticks</a></th>
<th class="sa">Seriously attempted</th>
<th>
<details>
<summary>My solution</summary>
First, sort the cuts and let the cuts in the input
be <code>cuts[1], cuts[2], ..., cuts[n]</code>.
Define <code>cuts[0] = 0</code> and <code>cuts[n + 1] = L</code>.
I defined <code>cost[i][j]</code> to be the cost
of placing the cuts between i and j (inclusive) between
<code>cuts[i - 1]</code> and <code>cuts[j + 1]</code>.
Then <code>cost[i][j] = min(cuts[j + 1] - cuts[i - 1] + cost[i][k - 1] + cost[k + 1][j]</code>
for all possible k. (If <code>k - 1 &lt; i</code> or <code>k + 1 &gt; i</code>, ignore it.)
</details>
However, this solution got wrong answer.
</th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=839">USACO Talent Show</a></th>
<th class="sa">Seriously Attempted</th>
<th>
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
<a href="http://www.usaco.org/current/data/sol_talent_gold_open18.html">
the USACO solution</a>, but I don't understand why <code>dp[k1]</code>
will always have the optimal value, because <code>dp[k]</code> can be updated
and it doesn't guarantee <code>dp[k1]</code> gets updated.
I believe if <code>dp[k]</code> can get updated by a cow with weight w,
<code>dp[k1]</code> can get updated for the same cow with weight w by using
<code>dp[k1 - w]</code> (or <code>dp[W]</code> if k1 = W).
</th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=789">USACO MooTube</a></th>
<th class="so">Solved</th>
<th>
Should <a href="https://usaco.guide/gold/dsu?lang=cpp">read about DSU</a> before attempting.
<a href="https://cp-algorithms.com/data_structures/disjoint_set_union.html">Another good DSU resource</a>.
For this problem, I <a href="http://www.usaco.org/current/data/sol_mootube_gold_jan18.html">used the solution</a>.
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.
</th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=992">USACO Wormhole Sort</a></th>
<th class="so">Solved</th>
<th>
<a href="https://usaco.guide/problems/usaco-992-wormhole-sort/solution#solution-3---dsuuf">
Used this solution on USACO guide</a>.
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 <code>i</code> and its parent <code>p[i]</code>
and add edges until both have the same parent.
Additionally, I made cycles which are formed by connecting <code>i</code>
to <code>p[i]</code>, 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.
</th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=384">USACO Ski Course Rating</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="https://cses.fi/problemset/task/2101/">CSES New Road Queries</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="https://cses.fi/problemset/task/1202">CSES Investigation</a></th>
<th class="so">Solved</th>
<th>
Should <a href="https://usaco.guide/gold/shortest-paths?lang=cpp">read about shortest paths</a> before attempting.
At first, I didn't think abou the problem seriously, so I took a quick look
at the <a href="https://usaco.guide/problems/cses-1202-investigation/solution">USACO guide solution</a>
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.
</th>
</tr>
<tr>
<th><a href="https://oj.uz/problem/view/JOI18_commuter_pass">JOI 2018 Commuter Pass</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="https://oj.uz/problem/view/JOI21_ho_t4">JOI 2021 Robot</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=717">USACO Why Did the Cow Cross the Road (Gold)</a></th>
<th class="so">Solved</th>
<th>
<a href="http://www.usaco.org/current/data/sol_visitfj_gold_feb17.html">
Used the solution for this problem</a>.
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.
</th>
</tr>
<tr>
<th><a href="https://cses.fi/problemset/task/1196">CSES Flight Routes</a></th>
<th class="so">Solved</th>
<th>
I used <a href="https://usaco.guide/problems/cses-1196-flight-routes/solution">the usaco.guide solution</a>.
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.
</th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=971">USACO Moortal Cowmbat</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
</table>
</details>
<h2>Week of Dec 20, 2021 - Dec 26, 2021</h2>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
<tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=863">USACO Teamwork (2018 December Gold)</a></th>
<th class="so">Solved</th>
<th></th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=945">USACO Snakes (2019 US Open Gold)</a></th>
<th class="so">Solved</th>
<th></th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=993">USACO Time is Mooney (2020 January Gold)</a></th>
<th class="so">Solved</th>
<th>
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
<a href="http://www.usaco.org/current/data/sol_time_gold_jan20.html">
the solution on USACO.</a>
</th>
</tr>
<tr>
<th><a href="https://cses.fi/problemset/task/1746">CSES Array Description</a></th>
<th class="so">Solved</th>
<th></th>
</tr>
<tr>
<th><a href="https://cses.fi/problemset/task/2413">CSES Counting Towers</a></th>
<th class="so">Solved</th>
<th>
I used
<a href="https://codeforces.com/blog/entry/70018?#comment-820275">
this comment on the Codeforces CSES DP editorial</a>
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.
</th>
</tr>
<tr>
<th><a href="https://cses.fi/problemset/task/1635">CSES Coin Combinations I</a></th>
<th class="so">Solved</th>
<th></th>
</tr>
<tr>
<th><a href="https://cses.fi/problemset/task/1636">CSES Coin Combinations II</a></th>
<th class="so">Solved</th>
<th>
<a href="https://usaco.guide/problems/cses-1636-coin-combinations-ii-ordered/solution">Used the USACO Guide solution</a>.
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 &le; i &le; x
using on the first j - 1 coins and then updating ways[i]
for 0 &le; i &le; x with the jth coin.
</th>
</tr>
<tr>
<th><a href="https://cses.fi/problemset/task/1637">CSES Removing Digits</a></th>
<th class="so">Solved</th>
<th></th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=622">USACO Circular Barn Revisited</a></th>
<th class="so">Solved</th>
<th>
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.
<a href="http://www.usaco.org/current/data/sol_cbarn2_gold_feb16.html">
I used the USACO Solution</a>.
</th>
</tr>
<tr>
<th><a href="https://dmoj.ca/problem/ioi04p4">IOI 2004 Phidias</a></th>
<th class="so">Solved</th>
<th>
I thought of choosing one of the desired plates to remove
and then somehow doing dp on that.
<a href="https://usaco.guide/problems/dmoj-phidias/solution">
The correct solution on USACO guide</a>
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:
<ul style="text-align: left;">
<li>
a marble of size <i>a</i> by <i>m</i>
and a marble of size <i>n - a</i> by <i>m</i>
</li>
<li>
a marble of size <i>n</i> by <i>b</i>
and a marble of size <i>n</i> by <i>m - b</i>
</li>
</ul>
where 1 &le; a &le; n - 1 and 1 &le; b &le; m - 1.
</th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=815">USACO Taming the Herd</a></th>
<th class="so">Solved</th>
<th></th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=971">USACO Moortal Cowmbat</a></th>
<th class="s">Started</th>
<th>
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.
</th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=839">USACO Talent Show</a></th>
<th class="sa">Seriously Attempted</th>
<th>
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
<a href="http://www.usaco.org/current/data/sol_talent_gold_open18.html">
the USACO solution</a>, but I don't understand why <code>dp[k1]</code>
will always have the optimal value, because <code>dp[k]</code> can be updated
and it doesn't guarantee <code>dp[k1]</code> gets updated.
I believe if <code>dp[k]</code> can get updated by a cow with weight w,
<code>dp[k1]</code> can get updated for the same cow with weight w by using
<code>dp[k1 - w]</code> (or <code>dp[W]</code> if k1 = W).
</th>
</tr>
<tr>
<th><a href="https://oj.uz/problem/view/NOI18_knapsack">NOI 18 Knapsack</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=897">USACO Cow Poetry</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="https://cses.fi/problemset/task/1639">CSES Edit Distance</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=944">Online Judge 10003 Cutting Sticks</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
</table>
</details>
<h2>Week of Dec 13, 2021 - Dec 19, 2021</h2>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
<tr>
<tr>
<th><a href="https://www.spoj.com/problems/HAYBALE/">USACO Haybale Stacking</a></th>
<th class="so">Solved</th>
<th>
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.
</th>
</tr>
<tr>
<th><a href="https://cses.fi/problemset/task/1085">CSES Array Division</a></th>
<th class="so">Solved</th>
<th>
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.
</th>
</tr>
<tr>
<th><a href="https://codeforces.com/contest/782/problem/B">Codeforces The Meeting Place Cannot Be Changed</a></th>
<th class="so">Solved</th>
<th>
Had some trouble implementing the eps binary search.
I think the problem I had was using <code>double</code>
instead of <code>long double</code>.
</th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=920">USACO The Great Revegetation</a></th>
<th class="so">Solved</th>
<th>
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.
</th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=716">USACO Why Did the Cow Cross the Road III</a></th>
<th class="so">Solved</th>
<th>
<p>
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.
</p>
<p>
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.
</p>
</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1086">USACO Dance Mooves</a></th>
<th class="so">Solved</th>
<th>
Solved by finding the cycle each cow was in.
Then, found the cows the cows in a cycle can visit.
</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1087">USACO No Time to Paint</a></th>
<th class="so">Solved</th>
<th>
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.
</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1088">USACO Spaced Out</a></th>
<th class="so">Solved</th>
<th>
There are two cases.
First case: in each row, every other column
is occupied.
Second case: in each column, every other row
is occupied.
</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1110">USACO Comfortable Cows</a></th>
<th class="so">Solved</th>
<th>
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).
</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1111">USACO Year of the Cow</a></th>
<th class="so">Solved</th>
<th></th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1112">USACO Just Green Enough</a></th>
<th class="so">Solved</th>
<th>
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.
</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1062">USACO Cowntagion</a></th>
<th class="so">Solved</th>
<th></th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1063">USACO Rectangular Pasture</a></th>
<th class="so">Solved</th>
<th>
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.
</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1064">USACO Stuck in a Rut</a></th>
<th class="so">Solved</th>
<th>
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.
</th>
</tr>
</table>
</details>
<h2>Week of Dec 06, 2021 - Dec 12, 2021</h2>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
<tr>
<tr>
<th>
<a href="https://www.spoj.com/problems/HAYBALE/">
USACO Haybale Stacking
</a>
</th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th>
<a href="https://cses.fi/problemset/task/1632">
CSES Movie Festival II
</a>
</th>
<th class="so">Solved</th>
<th>
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.
</th>
</tr>
<tr>
<th>
<a href="https://cses.fi/problemset/task/1682">
CSES Flight Routes Check
</a>
</th>
<th class="so">Solved</th>
<th>
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
<a href="https://usaco.guide/problems/cses-1682-flight-routes-check/solution">
USACO guide solution.</a>
</th>
</tr>
<tr>
<th>
<a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=992">
USACO Wormhole Sort
</a>
</th>
<th class="so">Solved</th>
<th>
As given in the problem input, p[i] is the ith cow.
I let i &rarr; 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] &rarr; 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] &rarr; 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] &rarr; b[i] for 1 &le; i &le; M.
Each node in a cycle must have the same component.
<a href="http://www.usaco.org/current/data/sol_wormsort_silver_jan20.html">
The USACO solution is similiar to this one and the wording is more clear</a>.
</th>
</tr>
<tr>
<th>
<a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=573">
USACO High Card Low Card
</a>
</th>
<th class="so">Solved</th>
<th>
Wasn't sure where to begin initally, so I created a random test
case and got the intution of the greedy algorithm.
</th>
</tr>
</table>
</details>
<h2>Week of Nov 29, 2021 - Dec 05, 2021</h2>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
<tr>
<tr>
<th>
<a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=645">USACO Splitting the Field</a>
</th>
<th class="sa">Seriously Attempted</th>
<th>
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.
</th>
</tr>
<tr>
<th><a href="https://www.spoj.com/problems/HAYBALE/">USACO Haybale Stacking</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="https://atcoder.jp/contests/abc125/tasks/abc125_c">Atcoder GCD on Blackboard</a></th>
<th class="so">Solved</th>
<th></th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=714">USACO Why Did the Cow Cross the Road</a></th>
<th class="so">Solved</th>
<th>
<p>
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.
</p>
<p>
After: used a multiset instead of a set, since chickens may start at the same time.
Got accepted.
</p>
</th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=1038">USACO Social Distancing</a></th>
<th class="so">Solved</th>
<th>
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.
</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=419">USACO Sabotage</a></th>
<th class="s">Started</th>
<th>
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.
</th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=597">USACO Angry Cows</a></th>
<th class="s">Started</th>
<th>
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.
</th>
</tr>
</table>
</details>
<h2>Week of Nov 22, 2021 - Nov 28, 2021</h2>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
<tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1062">USACO Cowntagion</a></th>
<th class="so">Solved</th>
<th>
The optimal solution is to double the cows in the current
farm before moving the cows in the adjacent farms
of the current farm.
</th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1063">USACO Rectangular Pasture</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1064">USACO Stuck in a Rut</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="https://cses.fi/problemset/task/1630">CSES Tasks and Deadlines</a></th>
<th class="so">Solved</th>
<th>
I didn't understand why my solution of sorting
the task durations in increasing order worked.
Page 71 of the pdf of the
<a href="https://cses.fi/book/book.pdf">CSES book</a>
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 &#62; b, swapping the
tasks allows us to loose b points (from the longer task)
and gain a points (from the shorter task).
</th>
</tr>
<tr>
<th><a href="https://cses.fi/problemset/task/1632">CSES Movie Festival II</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="https://cses.fi/problemset/task/2216">CSES Collecting Numbers</a></th>
<th class="so">Solved</th>
<th></th>
</tr>
<tr>
<th><a href="https://cses.fi/problemset/task/1646">CSES Static Range Sum Queries</a></th>
<th class="so">Solved</th>
<th></th>
</tr>
<tr>
<th><a href="https://cses.fi/problemset/task/1680">CSES Longest Flight Route</a></th>
<th class="s">Started</th>
<th>
<p>
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.
</p>
<p>
Note I will probably not do this problem for now.
It uses topological sorting, and I don't think USACO
silver needs this.
</p>
</th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=787">USACO Rental Service</a></th>
<th class="so">Solved</th>
<th>
Forgot to consider that the maximum
milk that can be sold may be LESS than
the milk the cows can produce in total.
</th>
</tr>
<tr>
<th><a href="http://www.usaco.org/index.php?page=viewproblem2&cpid=896">USACO Mountain View</a></th>
<th class="so">Solved</th>
<th>
Didn't consider the case where
two mountains STARTED at the same point
and covered each other.
</th>
</tr>
</table>
</details>
<h2>Week of Nov 15, 2021 - Nov 21, 2021</h2>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
<tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1062">USACO Cowntagion</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1063">USACO Rectangular Pasture</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1064">USACO Stuck in a Rut</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="https://cses.fi/problemset/task/1630">CSES Tasks and Deadlines</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="https://cses.fi/problemset/task/1632">CSES Movie Festival II</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="https://cses.fi/problemset/task/2216">CSES Collecting Numbers</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="https://cses.fi/problemset/task/1646">CSES Static Range Sum Queries</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
</table>
</details>
<h2>Week of Nov 08, 2021 - Nov 14, 2021</h2>
<details>
<summary>Click to show table</summary>
<table>
<tr>
<th>Problem Link</th>
<th>Status</th>
<th>Additional Notes</th>
<tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=990">USACO Berry Picking</a></th>
<th class="so">Solved</th>
<th>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</th>
</tr>
<tr>
<th><a href="https://cses.fi/problemset/task/1669">CSES Round Trip</a></th>
<th class="so">Solved</th>
<th>
The problem asked for
<a href="https://www.geeksforgeeks.org/detect-cycle-undirected-graph/">detecting cycles in undirected graphs</a>, 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.
</th>
</tr>
<tr>
<th><a href="https://cses.fi/problemset/task/1674">CSES Subordinates</a></th>
<th class="so">Solved</th>
<th></th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1062">USACO Cowntagion</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1063">USACO Rectangular Pasture</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
<tr>
<th><a href="http://usaco.org/index.php?page=viewproblem2&cpid=1064">USACO Stuck in a Rut</a></th>
<th class="ns">Not started</th>
<th></th>
</tr>
</table>
</details>
</article>
<footer>
<p>
<a href="/">home</a>
</p>
<p>
all code/content on this website is under CC0
unless otherwise stated.
</p>
<p>
other projects I have may have different licenses
</p>
</footer>
</body>
</html>