diff options
author | Benjamin Qi | 2020-07-20 15:41:38 -0400 |
---|---|---|
committer | Benjamin Qi | 2020-07-20 15:41:38 -0400 |
commit | 8399c7dbcd15b9f80975028ce09849ff603e3f28 (patch) | |
tree | a348a41e9cdb7206fd10b83df0d81747d2ff18ab | |
parent | 5e07091a0356ca87aa4fbab0e36ff6fa4ebd6866 (diff) |
change bronze order, queues back in gold
-rw-r--r-- | content/1_Intro/Running_Code.mdx | 11 | ||||
-rw-r--r-- | content/2_Bronze/Ad_Hoc.mdx | 31 | ||||
-rw-r--r-- | content/2_Bronze/Intro_Greedy.mdx | 117 | ||||
-rw-r--r-- | content/2_Bronze/Simulation.mdx | 2 | ||||
-rw-r--r-- | content/2_Bronze/Unordered.mdx | 2 | ||||
-rw-r--r-- | content/3_Silver/Greedy.mdx | 90 | ||||
-rw-r--r-- | content/4_Gold/Queues.mdx (renamed from content/3_Silver/Queues.mdx) | 4 | ||||
-rw-r--r-- | content/4_Gold/Stacks.mdx | 2 | ||||
-rw-r--r-- | content/authors/authors.ts | 2 | ||||
-rw-r--r-- | content/authors/images/cow.png | bin | 0 -> 5242 bytes | |||
-rw-r--r-- | content/ordering.ts | 7 |
11 files changed, 147 insertions, 121 deletions
diff --git a/content/1_Intro/Running_Code.mdx b/content/1_Intro/Running_Code.mdx index 19cbc02..8e7a54f 100644 --- a/content/1_Intro/Running_Code.mdx +++ b/content/1_Intro/Running_Code.mdx @@ -160,7 +160,7 @@ If you want to code in (neo)vim, you can install WSL and code through WSL bash. probably suffices. -5. You should be able to compile with `g++` or maybe `g++-#`, where # is the version number (ex. 9). Running the following command +5. You should be able to compile with `g++-#`, where # is the version number (ex. 9). Running the following command ``` g++-9 --version @@ -175,6 +175,15 @@ If you want to code in (neo)vim, you can install WSL and code through WSL bash. warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. ``` +6. If you want to be able to compile with just `g++`, create a symbolic link as mentioned [here](https://stackoverflow.com/questions/28970935/osx-replace-gcc-version-4-2-1-with-4-9-installed-via-homebrew/28982564#28982564). + + ``` + cd /usr/local/bin + ln -s g++-9 g++ + ``` + + `g++ --version` should now output the same thing as `g++-9 --version`. + ## Running With the Command Line Consider a simple program such as the following, which we'll save in `name.cpp`. diff --git a/content/2_Bronze/Ad_Hoc.mdx b/content/2_Bronze/Ad_Hoc.mdx new file mode 100644 index 0000000..3582bb3 --- /dev/null +++ b/content/2_Bronze/Ad_Hoc.mdx @@ -0,0 +1,31 @@ +--- +id: ad-hoc +title: Ad Hoc Problems +author: Michael Cao +description: "Problems that don't fall under any well-defined category." +frequency: 1 +--- + +Most bronze problems fall into specific categories, such as simulation and complete search. Those which don't often require more thought, although they are not necessarily more difficult to implement. + +Any problem that doesn't fall under any well-defined category can be labelled as **Ad Hoc**. Since there is no fixed algorithm or idea to solving these problems, they can be hard to generalize. In this module, we'll go over some general tips that may be useful in approaching these problems. + +<ul> + <li> Draw lots of small cases to gain a better understanding of the problem. If you're having trouble debugging, draw more cases. If you don't know how to start with a problem, draw more cases. Whenever you don't know how to further approach a problem, you're probably missing an important observation, so draw more cases and make observations about properties of the problem. </li> + <li> Whenever you find an observation that seems useful, write it down! Writing down ideas lets you easily come back to them later, and makes sure you don't forget about ideas that could potentially be the solution. </li> + <li> Don't get stuck on any specific idea, unless you see an entire solution. Trying to complete search an Ad Hoc problem could end up wasting a lot of your time in contest. </li> + <li> Try to approach the problem from a lot of different perspectives. Try to draw a visual depiction of the problem, mess around with formulas, or draw a graph (see Graph Theory module). One of the most helpful things you can do when solving Ad Hoc problems is to keep trying ideas until you make progress. This is something you get better at as you do more problems.</li> +</ul> + +These tips are helpful in solving Ad Hoc problems. However, in the end, the best way to get better at Ad Hoc problems (or any type of problem) is to do a lot of them. Try to solve as many practice problems below as you can, and click the solution sketch tab if you can't figure the solution out. + +<!-- If anyone disagrees with any of the tips / ideas presented in the blogs below, just let me know and you can remove it if you want. I think they're quite interesting, though I haven't tried it out myself. --> + +<Resources> + <Resource source="ZLE" title="The Art of Thinking" url="https://kauntaofficial.github.io/the-art-of-thinking">blog with more tips</Resource> + <Resource source="ZLE" title="Developing Intuition" url="https://kauntaofficial.github.io/developing-intuition">developing intuition while practicing</Resource> +</Resources> + +## Problems + +<IncompleteSection />
\ No newline at end of file diff --git a/content/2_Bronze/Intro_Greedy.mdx b/content/2_Bronze/Intro_Greedy.mdx index ec3294c..bbcc925 100644 --- a/content/2_Bronze/Intro_Greedy.mdx +++ b/content/2_Bronze/Intro_Greedy.mdx @@ -1,9 +1,12 @@ --- id: intro-greedy -title: Introduction to Greedy Algorithms & Ad Hoc -author: Michael Cao, Darren Yao +title: Introduction to Greedy Algorithms +author: Darren Yao description: "Selecting the choice that seems to be the best at the moment at every step of your algorithm." frequency: 2 +prerequisites: + - ad-hoc + - intro-ds --- import { Problem } from "../models"; @@ -18,32 +21,9 @@ export const problems = { ], }; -## Ad Hoc - -Most bronze problems fall into specific categories, such as simulation and complete search. Those which don't often require more thought, although they are not necessarily more difficult to implement. - -Any problem that doesn't fall under any well-defined category can be labelled as **Ad Hoc**. Since there is no fixed algorithm or idea to solving these problems, they can be hard to generalize. In this module, we'll go over some general tips that may be useful in approaching these problems. - -<ul> - <li> Draw lots of small cases to gain a better understanding of the problem. If you're having trouble debugging, draw more cases. If you don't know how to start with a problem, draw more cases. Whenever you don't know how to further approach a problem, you're probably missing an important observation, so draw more cases and make observations about properties of the problem. </li> - <li> Whenever you find an observation that seems useful, write it down! Writing down ideas lets you easily come back to them later, and makes sure you don't forget about ideas that could potentially be the solution. </li> - <li> Don't get stuck on any specific idea, unless you see an entire solution. Trying to complete search an Ad Hoc problem could end up wasting a lot of your time in contest. </li> - <li> Try to approach the problem from a lot of different perspectives. Try to draw a visual depiction of the problem, mess around with formulas, or draw a graph (see Graph Theory module). One of the most helpful things you can do when solving Ad Hoc problems is to keep trying ideas until you make progress. This is something you get better at as you do more problems.</li> -</ul> - -These tips are helpful in solving Ad Hoc problems. However, in the end, the best way to get better at Ad Hoc problems (or any type of problems) is to do a lot of them. Try to solve as many practice problems below as you can, and click the solution sketch tab if you can't figure the solution out. - -<!-- If anyone disagrees with any of the tips / ideas presented in the blogs below, just let me know and you can remove it if you want. I think they're quite interesting, though I haven't tried it out myself. --> - -<Resources> - <Resource source="ZLE" title="The Art of Thinking" url="https://kauntaofficial.github.io/the-art-of-thinking">blog with more tips</Resource> - <Resource source="ZLE" title="Developing Intuition" url="https://kauntaofficial.github.io/developing-intuition">developing intuition while practicing</Resource> -</Resources> - - ## Greedy Algorithms -Most USACO Bronze problems that appear to be Ad Hoc can actually be solved using **greedy** algorithms. This idea will be covered in a future [module](../silver/greedy), but we'll introduce the general mindset in this section. +Some USACO Bronze problems that appear to be Ad Hoc can actually be solved using **greedy** algorithms. This idea will be covered in a future [module](../silver/greedy), but we'll introduce the general mindset in this section. <Resources> <Resource source="CPH" title="6.1 - Coin Problem" starred>other examples are outside scope of bronze</Resource> @@ -58,90 +38,7 @@ algorithms are usually very efficient. **Greedy** does not refer to a single algorithm, but rather a way of thinking that is applied to problems; there's no one way to do greedy algorithms. Hence, we use a selection of well-known examples to help you understand the greedy paradigm. -### Example: Studying Algorithms - -Steph wants to improve her knowledge of algorithms over winter break. She has a total of $X$ ($1 \leq X \leq 10^4$) minutes to dedicate to learning algorithms. There are $N$ ($1 \leq N \leq 100$) algorithms, and each one of them requires $a_i$ ($1 \leq a_i \leq 100$) minutes to learn. Find the maximum number of algorithms she can learn. - -#### Solution - -<Spoiler title="Solution"> - -The first observation we make is that Steph should prioritize learning algorithms from easiest to hardest; in other words, start with learning the algorithm that requires the least amount of time, and then choose further algorithms in increasing order of time required. Let's look at the following example: - -$$ -X = 15, \qquad N = 6, \qquad a_i = \{ 4, 3, 8, 4, 7, 3 \} -$$ - -After sorting the array, we have $\{ 3, 3, 4, 4, 7, 8 \}$. Within the maximum of 15 minutes, Steph can learn four algorithms in a total of $3+3+4+4 = 14$ minutes. - -The implementation of this algorithm is very simple. We sort the array, and then take as many elements as possible while the sum of times of algorithms chosen so far is less than $X$. Sorting the array takes $O(N \log N)$ time, and iterating through the array takes $O(N)$ time, for a total time complexity of $O(N \log N)$. - -<LanguageSection> - -<CPPSection> - -```cpp -// read in the input, store the algorithms in a vector, algorithms -sort(algorithms.begin(), algorithms.end()); -int count = 0; // number of minutes used so far -int i = 0; -while(count + algorithms[i] <= x){ - // while there is enough time, learn more algorithms - count += algorithms[i]; - i++; -} -cout << i << endl; // print the ans -``` - -</CPPSection> - -<JavaSection> - -```java -// read in the input, store the algorithms in int[] algorithms -Arrays.sort(algorithms); -int count = 0; // number of minutes used so far -int i = 0; -while(count + algorithms[i] <= x){ - // while there is enough time, learn more algorithms - count += algorithms[i]; - i++; -} -pw.println(i); // print the ans -pw.close(); -``` - -</JavaSection> - -</LanguageSection> - -</Spoiler> - -### When Greedy Fails - -We'll provide a few common examples of when greedy fails, so that you can avoid falling into obvious traps and wasting time getting wrong answers in contest. - -#### Coin Change - -This problem gives several coin denominations, and asks for the minimum number of coins needed to make a certain value. Greedy algorithms can be used to solve this problem only in very specific cases (it can be proven that it works for the American as well as the Euro coin systems). However, it doesn't work in the general case. For example, let the coin denominations be $\{1, 3, 4\}$, and say the value we want is 6. The optimal solution is $\{3, 3\}$, which requires only two coins, but the greedy method of taking the highest possible valued coin that fits in the remaining denomination gives the solution $\{4, 1, 1\}$, which is incorrect. - -#### Knapsack - -The knapsack problem gives a number of items, each having a **weight** and a **value**, and we want to choose a subset of these items. We are limited to a certain weight, and we want to maximize the value of the items that we take. - -Let's take the following example, where we have a maximum capacity of 4: - -<center> - -| Item | Weight | Value | Value Per Weight | -|------|--------|-------|------------------| -| A | 3 | 18 | 6 | -| B | 2 | 10 | 5 | -| C | 2 | 10 | 5 | - -</center> - -If we use greedy based on highest value first, we choose item A and then we are done, as we don't have remaining weight to fit either of the other two. Using greedy based on value per weight again selects item A and then quits. However, the optimal solution is to select items B and C, as they combined have a higher value than item A alone. In fact, there is no working greedy solution. The solution to this problem uses **dynamic programming**, which is covered in gold. +<IncompleteSection /> ### Example: Mad Scientist diff --git a/content/2_Bronze/Simulation.mdx b/content/2_Bronze/Simulation.mdx index 9f51e74..fcb79d9 100644 --- a/content/2_Bronze/Simulation.mdx +++ b/content/2_Bronze/Simulation.mdx @@ -2,7 +2,7 @@ id: simulation title: "Simulation" author: Darren Yao -description: "Directly simulating the problem statement, which many Bronze problems allow you to do, illustrated by an example problem." +description: "Directly simulating the problem statement, which many Bronze problems allow you to do." frequency: 4 --- diff --git a/content/2_Bronze/Unordered.mdx b/content/2_Bronze/Unordered.mdx index 7fa2a76..073fd5b 100644 --- a/content/2_Bronze/Unordered.mdx +++ b/content/2_Bronze/Unordered.mdx @@ -2,7 +2,7 @@ id: unordered title: Unordered Maps & Sets author: Darren Yao, Benjamin Qi -description: "Two useful data structures that can greatly simplify some problems." +description: "?" frequency: 2 prerequisites: - pairs-tuples diff --git a/content/3_Silver/Greedy.mdx b/content/3_Silver/Greedy.mdx index a4eaf64..4d1d13a 100644 --- a/content/3_Silver/Greedy.mdx +++ b/content/3_Silver/Greedy.mdx @@ -6,7 +6,7 @@ prerequisites: - intro-greedy - sorting-custom - intro-ordered -description: "Continuation of greedy problems that were introduced in Bronze." +description: "?" frequency: 3 --- @@ -59,6 +59,66 @@ Usually, when using a greedy algorithm, there is a **heuristic** or **value func Here, we'll focus on problems where some sorting step is involved. + +## Example: Studying Algorithms + +Steph wants to improve her knowledge of algorithms over winter break. She has a total of $X$ ($1 \leq X \leq 10^4$) minutes to dedicate to learning algorithms. There are $N$ ($1 \leq N \leq 100$) algorithms, and each one of them requires $a_i$ ($1 \leq a_i \leq 100$) minutes to learn. Find the maximum number of algorithms she can learn. + +### Solution + +<Spoiler title="Solution"> + +The first observation we make is that Steph should prioritize learning algorithms from easiest to hardest; in other words, start with learning the algorithm that requires the least amount of time, and then choose further algorithms in increasing order of time required. Let's look at the following example: + +$$ +X = 15, \qquad N = 6, \qquad a_i = \{ 4, 3, 8, 4, 7, 3 \} +$$ + +After sorting the array, we have $\{ 3, 3, 4, 4, 7, 8 \}$. Within the maximum of 15 minutes, Steph can learn four algorithms in a total of $3+3+4+4 = 14$ minutes. + +The implementation of this algorithm is very simple. We sort the array, and then take as many elements as possible while the sum of times of algorithms chosen so far is less than $X$. Sorting the array takes $O(N \log N)$ time, and iterating through the array takes $O(N)$ time, for a total time complexity of $O(N \log N)$. + +<LanguageSection> + +<CPPSection> + +```cpp +// read in the input, store the algorithms in a vector, algorithms +sort(algorithms.begin(), algorithms.end()); +int count = 0; // number of minutes used so far +int i = 0; +while(count + algorithms[i] <= x){ + // while there is enough time, learn more algorithms + count += algorithms[i]; + i++; +} +cout << i << endl; // print the ans +``` + +</CPPSection> + +<JavaSection> + +```java +// read in the input, store the algorithms in int[] algorithms +Arrays.sort(algorithms); +int count = 0; // number of minutes used so far +int i = 0; +while(count + algorithms[i] <= x){ + // while there is enough time, learn more algorithms + count += algorithms[i]; + i++; +} +pw.println(i); // print the ans +pw.close(); +``` + +</JavaSection> + +</LanguageSection> + +</Spoiler> + ## Example: The Scheduling Problem <Problems problems={problems.movie} /> @@ -172,6 +232,34 @@ pw.close(); </LanguageSection> +## When Greedy Fails + +We'll provide a few common examples of when greedy fails, so that you can avoid falling into obvious traps and wasting time getting wrong answers in contest. + +### Coin Change + +This problem gives several coin denominations, and asks for the minimum number of coins needed to make a certain value. Greedy algorithms can be used to solve this problem only in very specific cases (it can be proven that it works for the American as well as the Euro coin systems). However, it doesn't work in the general case. For example, let the coin denominations be $\{1, 3, 4\}$, and say the value we want is 6. The optimal solution is $\{3, 3\}$, which requires only two coins, but the greedy method of taking the highest possible valued coin that fits in the remaining denomination gives the solution $\{4, 1, 1\}$, which is incorrect. + +### Knapsack + +The knapsack problem gives a number of items, each having a **weight** and a **value**, and we want to choose a subset of these items. We are limited to a certain weight, and we want to maximize the value of the items that we take. + +Let's take the following example, where we have a maximum capacity of 4: + +<center> + +| Item | Weight | Value | Value Per Weight | +|------|--------|-------|------------------| +| A | 3 | 18 | 6 | +| B | 2 | 10 | 5 | +| C | 2 | 10 | 5 | + +</center> + +If we use greedy based on highest value first, we choose item A and then we are done, as we don't have remaining weight to fit either of the other two. Using greedy based on value per weight again selects item A and then quits. However, the optimal solution is to select items B and C, as they combined have a higher value than item A alone. In fact, there is no working greedy solution. The solution to this problem uses **dynamic programming**, which is covered in gold. + + + ## CSES Problems <Problems problems={problems.cses} /> diff --git a/content/3_Silver/Queues.mdx b/content/4_Gold/Queues.mdx index 6509db1..20a4a0f 100644 --- a/content/3_Silver/Queues.mdx +++ b/content/4_Gold/Queues.mdx @@ -1,8 +1,8 @@ --- id: queues -title: Queues +title: Queues & Deques author: Darren Yao -description: "Two data structures to efficently add and remove the first and last element." +description: "Data structures that allow insertion and deletion at both ends." prerequisites: - intro-ds - sliding diff --git a/content/4_Gold/Stacks.mdx b/content/4_Gold/Stacks.mdx index e37cd96..9beae4d 100644 --- a/content/4_Gold/Stacks.mdx +++ b/content/4_Gold/Stacks.mdx @@ -2,7 +2,7 @@ id: stacks title: Stacks author: Darren Yao -description: "Two data structures to efficently add and remove the first and last element." +description: "A data structures that only allows insertion and deletion at one end." prerequisites: - intro-ds --- diff --git a/content/authors/authors.ts b/content/authors/authors.ts index 869d717..6b12580 100644 --- a/content/authors/authors.ts +++ b/content/authors/authors.ts @@ -59,7 +59,7 @@ export const Authors: Author[] = [ github: "darren-yao", }, { - photo: 'michael', + photo: 'cow', name: 'Siyong Huang', title: 'Content Author', blurb: '', diff --git a/content/authors/images/cow.png b/content/authors/images/cow.png Binary files differnew file mode 100644 index 0000000..d7abfac --- /dev/null +++ b/content/authors/images/cow.png diff --git a/content/ordering.ts b/content/ordering.ts index f62ee30..d538304 100644 --- a/content/ordering.ts +++ b/content/ordering.ts @@ -64,7 +64,6 @@ const MODULE_ORDERING: {[key in SectionID]: Chapter[]} = { "time-comp", "simulation", "rect-geo", - "intro-greedy", ] }, { @@ -83,8 +82,10 @@ const MODULE_ORDERING: {[key in SectionID]: Chapter[]} = { ] }, { - name: "Graphs", + name: "Unusual", items: [ + "ad-hoc", + "intro-greedy", "intro-graphs", ] } @@ -220,10 +221,10 @@ const MODULE_ORDERING: {[key in SectionID]: Chapter[]} = { "sp-neg", "BCC-2CC", "SCC", - "eulers-formula", "max-flow", "eulerian-tours", "offline-con", + "eulers-formula", ] }, { |