diff options
author | Benjamin Qi | 2020-07-20 18:11:12 -0400 |
---|---|---|
committer | Benjamin Qi | 2020-07-20 18:11:12 -0400 |
commit | fc318b35436d1b6a3fccb12bcde8f3e438c33925 (patch) | |
tree | 3cffaddde03d267ae992cea75fc1c9b52065f52c | |
parent | 28da1b468bd9db191c8f542bdbc0a0740dc10873 (diff) |
intro
-rw-r--r-- | content/1_Intro/Choosing_Lang.mdx | 2 | ||||
-rw-r--r-- | content/1_Intro/Data_Types.mdx | 15 | ||||
-rw-r--r-- | content/1_Intro/Expected.mdx | 2 | ||||
-rw-r--r-- | content/1_Intro/Fast_IO.mdx | 2 | ||||
-rw-r--r-- | content/1_Intro/Intro.mdx | 6 | ||||
-rw-r--r-- | content/1_Intro/Resources.mdx | 13 | ||||
-rw-r--r-- | content/1_Intro/Running_Code.mdx | 29 | ||||
-rw-r--r-- | content/4_Gold/Queues.mdx | 2 |
8 files changed, 39 insertions, 32 deletions
diff --git a/content/1_Intro/Choosing_Lang.mdx b/content/1_Intro/Choosing_Lang.mdx index dde8044..8014ff4 100644 --- a/content/1_Intro/Choosing_Lang.mdx +++ b/content/1_Intro/Choosing_Lang.mdx @@ -39,6 +39,8 @@ If you aren't comfortable with basic coding yet, you can use the resources below <CPPSection> +### C++ + Use one of the resources above or below (or find your own) to learn C++. If you use Sololearn, you don't have to complete the full course; we recommend you finish everything up to (but not including) "More on Classes." <Resources title="C++"> diff --git a/content/1_Intro/Data_Types.mdx b/content/1_Intro/Data_Types.mdx index 7e092b8..54e4a78 100644 --- a/content/1_Intro/Data_Types.mdx +++ b/content/1_Intro/Data_Types.mdx @@ -19,8 +19,7 @@ prerequisites: There are several main **data types** that are used in contests: integers, floating point numbers, booleans, characters, and strings. Assuming that you are familiar with the language you are using, this should be mostly review. -The normal **32-bit integer** data type (`int` in C++ and Java) supports values between $−2\,147\,483\,648 and 2\,147\,483\,647, which is -roughly equal to $\pm 2 \cdot 10^9$. +The normal **32-bit integer** data type (`int` in C++ and Java) supports values between $−2\,147\,483\,648$ and $2\,147\,483\,647$, which is roughly equal to $\pm 2 \cdot 10^9$. Some problems require you to use **64-bit integers** (`long long` in C++ and `long` in Java) instead of 32-bit integers (`int`). 64-bit integers are less likely to have overflow issues, since they can store any number between $-9\,223\,372\,036\,854\,775\,808$ and $9\,223\,372\,036\,854\,775\,807$ which is roughly equal to $\pm 9 \times 10^{18}$. @@ -30,16 +29,14 @@ Sometimes (but not always) a USACO problem statement (ex. [Haircut](http://www.u Contest problems are usually set such that the 64-bit integer is sufficient, so it might be a good idea to use 64-bit integers in place of 32-bit integers everywhere. Of course, you shouldn't do this when time and/or memory limits are tight, which may be the case in higher divisions of USACO. Also note that in Java, you will need to cast `long` back to `int` when accessing array indices. -**Floating point numbers** are used to store decimal values. It is important to know that floating point numbers are not exact, because the binary architecture of computers can only store decimals to a certain precision. Hence, we should always expect that floating point numbers are slightly off. It's generally a bad idea to compare two floating-point numbers for exact equality (`==`); instead, check if their absolute difference is less than some small constant like $10^{-9}$. +**Floating point numbers** are used to store decimal values. It is important to know that floating point numbers are not exact, because the binary architecture of computers can only store decimals to a certain precision. Hence, we should always expect that floating point numbers are slightly off, so it's generally a bad idea to compare two floating-point numbers for exact equality (`==`). -Contest problems will accommodate the inaccuracy of floating point numbers in two different ways. +Contest problems will usually accommodate the inaccuracy of floating point numbers by checking if the **absolute** or **relative** difference between your output and the answer is less than some small constant like $\epsilon=10^{-9}$. -USACO problems generally have a unique answer, so when floating point is necessary, the output format will be something along the lines of "Print $10^6$ times the maximum probability of receiving exactly one accepted invitation, rounded down to the nearest integer." See [USACO Cow Dating](http://www.usaco.org/index.php?page=viewproblem2&cpid=924). +- If your output is $x$ and the answer is $y$, the absolute difference is $|x-y|$. +- If your output is $x$ and the answer is $y$, the relative difference is $\frac{|x-y|}{|y|}$. -In CodeForces or other contests, your output will be marked as correct if its absolute or relative difference from the actual answer is less than a given $\epsilon$. - -- If your output is x and the answer is y, the absolute difference is $|x-y|$. -- If your output is x and the answer is y, the relative difference is $\frac{|x-y|}{y}$. +This is not the case for USACO, where problems generally have a unique correct output. So when floating point is necessary, the output format will be something along the lines of "Print $10^6$ times the maximum probability of receiving exactly one accepted invitation, rounded down to the nearest integer." (ex. [Cow Dating](http://www.usaco.org/index.php?page=viewproblem2&cpid=924)). **Boolean** variables have two possible states: `true` and `false`. We'll usually use booleans to mark whether a certain process is done, and arrays of booleans to mark which components of an algorithm have finished. diff --git a/content/1_Intro/Expected.mdx b/content/1_Intro/Expected.mdx index 8f9e00a..28c77b3 100644 --- a/content/1_Intro/Expected.mdx +++ b/content/1_Intro/Expected.mdx @@ -53,7 +53,7 @@ The following require relatively little programming experience and no algorithmi <Problems problems={problems.general} /> -Also check the [CSES Introductory Problems](https://cses.fi/problemset/list/) up to and including "Palindrome Reorder." Once you're done with these, you should continue onto Bronze. +Also check the [CSES Introductory Problems](https://cses.fi/problemset/list/) up to and including "Palindrome Reorder." Once you're done with these, you should continue onto the rest of Bronze. <Warning> diff --git a/content/1_Intro/Fast_IO.mdx b/content/1_Intro/Fast_IO.mdx index f16189e..3b5f351 100644 --- a/content/1_Intro/Fast_IO.mdx +++ b/content/1_Intro/Fast_IO.mdx @@ -9,7 +9,7 @@ Generally, input and output speed isn't an issue. However, some platinum tasks h ## Fast Input -The largest USACO input file I know of is test case 11 of [USACO Platinum - Robotic Cow Herd](http://www.usaco.org/index.php?page=viewproblem2&cpid=674), which is 10.3 megabytes! The answer to this test case is $10^{18}$ (with $N=K=10^5$ and all microcontrollers costing $10^8$). +The largest USACO input file we know of is test case 11 of [USACO Platinum - Robotic Cow Herd](http://www.usaco.org/index.php?page=viewproblem2&cpid=674) (10.3 megabytes). The answer to this test case is $10^{18}$ (with $N=K=10^5$ and all microcontrollers costing $10^8$). <LanguageSection> diff --git a/content/1_Intro/Intro.mdx b/content/1_Intro/Intro.mdx index 173e8a1..4c7e9b5 100644 --- a/content/1_Intro/Intro.mdx +++ b/content/1_Intro/Intro.mdx @@ -5,6 +5,8 @@ author: Nathan Wang, Benjamin Qi, Darren Yao description: What is competitive programming? Let's take a look! --- +## Programming Competitions + A [programming competition](https://en.wikipedia.org/wiki/Competitive_programming) generally lasts for several hours and consists of a set of problems. These problems are not open problems; they have already been solved by the problem writers and testers and are designed to be solved in the short timeframe of a contest. In general, each problem in competitive programming is solved with a two-step process: 1. coming up with the algorithm, which involves problem solving skills and intuition @@ -30,10 +32,10 @@ For those of you with experience in software development, note that competitive <!-- </Optional> --> -## USACO Contest Format +## USACO <Resources> - <Resource source="USACO" title="Contests" url="http://www.usaco.org/index.php?page=contests" starred> </Resource> + <Resource source="USACO" title="Contests" url="http://www.usaco.org/index.php?page=contests" starred>more abount contest format</Resource> </Resources> The **USA Computing Olympiad** is a national programming competition that occurs four times a year, with December, January, February, and US Open (March) contests. The regular contests are four hours long, and the US Open is five hours long. Each contest contains three problems. Solutions are evaluated and scored against a set of predetermined test cases that are not visible to the student. Scoring is out of 1000 points, with each problem being weighted equally (\~333 points). There are four divisions of contests: Bronze, Silver, Gold, and Platinum. After each contest, students who meet the contest-dependent cutoff for promotion will compete in the next division for future contests. diff --git a/content/1_Intro/Resources.mdx b/content/1_Intro/Resources.mdx index 351842b..06216b5 100644 --- a/content/1_Intro/Resources.mdx +++ b/content/1_Intro/Resources.mdx @@ -18,22 +18,23 @@ description: A bunch of helpful links. - *Will be mentioned extensively in later modules.* - [Guide to Competitive Programming](https://www.amazon.com/Guide-Competitive-Programming-Algorithms-Undergraduate/dp/3319725467) is a paid book based off CPH - Can currently download PDF for [free](https://link.springer.com/book/10.1007/978-3-319-72547-5)! + - [Principles of Algorithmic Problem Solving](http://www.csc.kth.se/~jsannemo/slask/main.pdf) - Johan Sannemo + - practice problems from Kattis - Intro to USACO - Darren Yao - *Some modules are based off chapters from this book.* - covers most of Bronze, Silver - [Java](http://darrenyao.com/usacobook/java.pdf), [C++](http://darrenyao.com/usacobook/cpp.pdf) versions - Competitive Programming Book - Steven Halim, Felix Halim - - [Competitive Programming Book 2](https://www.comp.nus.edu.sg/~stevenha/myteaching/competitive_programming/cp2.pdf) is freely available but old + - [Competitive Programming 2](https://www.comp.nus.edu.sg/~stevenha/myteaching/competitive_programming/cp2.pdf) is freely available but old - [Competitive Programming 4](https://cpbook.net/) is the latest edition of the book (with significant additions) but costs money. - [CS Guide](https://github.com/alwayswimmin/cs_guide) - Samuel Hsiang, Alexander Wei, Yang Liu - - some more from TJHSST: - - [TJ Senior Computer Team](https://activities.tjhsst.edu/sct/) - - [TJIOI](https://github.com/tjsct/tjioi-study-guide) (just basics) - - [Principles of Algorithmic Problem Solving](http://www.csc.kth.se/~jsannemo/slask/main.pdf) - Johan Sannemo - - practice problems from Kattis + - The [TJ Senior Computer Team](https://activities.tjhsst.edu/sct/) website might also be of interest. - [Cracking the Coding Interview](http://www.crackingthecodinginterview.com/) - good book specifically for programming interviews + <!-- - some more from TJHSST: --> + <!-- - [TJIOI](https://github.com/tjsct/tjioi-study-guide) (just basics) --> + ## Courses - [Competitive Programming Course](https://github.com/SuprDewd/T-414-AFLV) - Bjarki Ágúst Guðmundsson diff --git a/content/1_Intro/Running_Code.mdx b/content/1_Intro/Running_Code.mdx index 8e7a54f..0f9c6be 100644 --- a/content/1_Intro/Running_Code.mdx +++ b/content/1_Intro/Running_Code.mdx @@ -48,7 +48,7 @@ You can run your C++ programs from the command line and use a text editor of you <Resources> <Resource title="Sublime Text 3" url="https://www.sublimetext.com/" starred> - Fast, lightweight. Keeps asking you to purchase a license ... + Fast, lightweight. Unlimited free evaluation period, though it will repeatedly ask you to purchase a license. </Resource> <Resource title="Atom" url="https://atom.io/"> From the makers of Github. @@ -179,7 +179,7 @@ If you want to code in (neo)vim, you can install WSL and code through WSL bash. ``` cd /usr/local/bin - ln -s g++-9 g++ + ln -fs g++-9 g++ ``` `g++ --version` should now output the same thing as `g++-9 --version`. @@ -228,15 +228,17 @@ See [Input & Output](./io) for how to do file input and output within the progra ### [Compiler Options (aka Flags)](https://gcc.gnu.org/onlinedocs/gcc/Option-Summary.html) -Use [compiler flags](https://developers.redhat.com/blog/2018/03/21/compiler-and-linker-flags-gcc/) to change the way GCC compiles your code. Usually, we use the following in place of `g++ name.cpp -o name`: +Use [compiler flags](https://developers.redhat.com/blog/2018/03/21/compiler-and-linker-flags-gcc/) to change the way GCC compiles your code. Usually, we use something like the following in place of `g++ name.cpp -o name`: -`g++ -std=c++17 -O2 name.cpp -o name -Wall -Wextra -Wshadow` +``` +g++ -std=c++17 -O2 name.cpp -o name -Wall +``` Explanation: - `-O2` tells `g++` to compile your code to run more quickly (see [here](https://www.rapidtables.com/code/linux/gcc/gcc-o.html)) - `-std=c++17` allows you to use features that were added to C++ in 2017. USACO currently uses `-std=c++11`. -- `-Wall -Wextra -Wshadow` checks your program for common errors. See [Debugging](./debugging) for more information. +- `-Wall` checks your program for common errors. See [Debugging](./debugging) for more information. You should always compile with these flags. @@ -349,7 +351,7 @@ python3 --version # prints Python 3.8.1 # Using an IDE <Resources> - <Resource source="IOI" title="2019 Contest Environment" url="https://ioi2019.az/en-content-26.html"> </Resource> + <Resource source="IOI" title="2019 Contest Environment" url="https://ioi2019.az/en-content-26.html">software you can use at IOI</Resource> </Resources> <LanguageSection> @@ -363,18 +365,15 @@ These often have C++ support already built-in. url="https://code.visualstudio.com/" starred > - Lightweight, fast IDE, but requires some configuration. See{' '} + More lightweight than Visual Studio, requires some configuration. See{' '} <a href="http://www.csc.kth.se/~jsannemo/slask/main.pdf">PAPC 2.1</a> for setup instructions. </Resource> - <Resource source=" " title="Geany" url="https://www.geany.org/" starred> + <Resource source="Geany" title="Geany" url="https://www.geany.org/" starred> Lightweight, frequently used at IOI. </Resource> - <Resource source="Microsoft" title="Visual Studio" url="https://visualstudio.microsoft.com/vs/"> - Heavier cousin of VS Code. VS Code is better for competitive programming. - </Resource> - <Resource source=" " title="Codeblocks" url="http://www.codeblocks.org/"> - Bad on Mac. + <Resource source="Code::Blocks" title="Code::Blocks" url="http://www.codeblocks.org/"> + Bad on Mac, <a href="https://codeforces.com/blog/entry/61780">apparently</a> unstable at IOI. </Resource> <Resource source="Apple" title="XCode" url="https://developer.apple.com/xcode/"> Mac only. @@ -388,6 +387,10 @@ These often have C++ support already built-in. </Resource> </Resources> +<!-- <Resource source="Microsoft" title="Visual Studio" url="https://visualstudio.microsoft.com/vs/"> + Heavier cousin of VS Code. VS Code is better for competitive programming. + </Resource> --> + </CPPSection> <JavaSection> diff --git a/content/4_Gold/Queues.mdx b/content/4_Gold/Queues.mdx index 20a4a0f..66fe38a 100644 --- a/content/4_Gold/Queues.mdx +++ b/content/4_Gold/Queues.mdx @@ -95,7 +95,9 @@ d.push_front(1); // [1, 3, 7] d.pop_back(); // [1, 3] ``` +<IncompleteSection> (important: you can also access like array ...) +</IncompleteSection> </CPPSection> |