cpinitiative / usaco-guide

A free collection of curated, high-quality resources to take you from Bronze to Platinum and beyond.

Competitive Programming Initiative

We promote competitive programming among students through resources, outreach, classes, and contests.

Thanks to Vercel for providing free hosting & continuous deployment!

Development Environment Setup

Instructions (for volunteer hours -- not necessarily needed for other stuff)

1. If not done already, clone the repository cpinitiative/cpinitiative and open up the folder.

2. At the root directory, add a file .env, which will contain the environment configuration for the volunteer-hours. An example .env file will look like

   GOOGLE_CLIENT_ID="....apps.googleusercontent.com"
   GOOGLE_CLIENT_SECRET="asdkjflasdjfklas"
   NEXTAUTH_URL="http://localhost:3000"
   SHEETS_PRIVATE_KEY="-----BEGIN PRIVATE KEY-----..."
   SHEETS_PRIVATE_KEY_ID="1298301asfa98sf09ac0291023"
   FIREBASE_PRIVATE_KEY="-----BEGIN PRIVATE KEY-----..."
   ENCRYPTION_KEY="asdjkflajsdflkjas;ldjfa"
   MJ_APIKEY_PUBLIC="mailjet api key public"
   MJ_APIKEY_PRIVATE=""
   PAYPAL_API_SECRET="ddd"
   MAILGUN_API_KEY=""

   Here's how to get the following keys:

   • Google Sheets: https://developers.google.com/sheets/api/guides/authorizing#APIKey
   • NEXT_AUTH_URL: choose the address of deployment
   • FIREBASE_PRIVATE_KEY -- I don't think this is even needed??
   • ENCRYPTION_KEY -- ask Nathan (or modify cryptography file), used to decrypt firebase key on vercel
   • MJ_APIKEY_PUBLIC/PRIVATE -- ask Nathan, only needed for newsletter
   • MAILCHIMP_API_KEY -- ask Nathan, only needed for class registration system
   • PAYPAL_API_SECRET -- ask Nathan, only needed for class registration system

3. Using the correct configuration file, go into SHEETS_API_CREDS inconfig.ts and make sure the credential object matches your Google Sheet configuration that you retrieved in the previous step.

4. Acquire firebase credentials (or setup emulator), and make sure to replace the configuration in the firebaseAdmin.initializeApp in firebase.ts with the correct configuration.

5. To navigate to the volunteer hours page after running yarn dev, you can go to localhost:3000/view-hours. Then, it should be able to test.

6. Make sure to add access to the sheet in mind through Google Sheets itself (add the service account email as an editor in the sheet)

Here is a sample entry in the table, for reference, which can be called with the google-spreadsheet node package, :

Timestamp	What is your name?	What is your email address?	List any PR's that you reviewed or submitted this week.	How many hours did you spend on the USACO Guide this week? Enter only a number. (Optional, only if you want volunteer hours)	Anything else you want to tell us? (Optional)
2021-10-23T23:18:42.653Z	Someone	[email protected]	I worked on pull requests and reviewed things.	4	Yes, I made some stuff.

usaco-guide's Issues

Plat

• Plat Trees: HLD, Small to Large problems
• Strings: just a stub (TJ guide covers it tho?)

Add more topics (not a priority)

• Min Deque
• Meet in Middle
• Ternary Search
• Boruvka

Links

https://codeforces.com/blog/entry/80438?#comment-666657

Clicking any link outside the website should open to new tab.

Code style guide?

Should we enforce a consistent coding style across all our snippets in the guide? If so, which coding style / what are the rules?

(examples: in bronze time complexity, the for loops don't have spaces. In some modules there are a lot of macros used.)

Text Alignment?

Bronze

• Determine which parts of containers go to bronze/silver
• merge existing articles about containers
• clean up Darren's links

Modules

• Add status to modules
• Move order out of modules
  • Generally get rid of numbering issues :)

Silver

• clean up silver containers, sorting
• review binsearch, two pointers, prefix sums, DFS

Use gatsby-image for logo

Searching

Guide should have a search bar. https://github.com/nextapps-de/flexsearch should do :)

For UI design, add search to the header: https://tailwindui.com/components/application-ui/application-shells/sidebar#component-ba754bf465a594eb075045eb9e940b60

Prerequisites

Should link to corresponding modules.

More problem tutorial modules?

Tutorials on challenging problems with bad editorials could be useful, like the one Ben did for springboards here, though springboards had a pretty good editorial.

Intro

• add contest format to getting started
• Java I/O, more details about I/O for others

Hyperlinks within info-block

can't distinguish hyperlink from bold text

ex. Plat -> More DP

Tabs for Switching Languages

ex. in https://usaco-guide.netlify.app/bronze/complete-search, switch between C++ and Java sols

Full-width code blocks

We should allow for code blocks to span the full width.

Can be integrated with table of contents nicely. Example: https://joshwcomeau.com/react/rainbow-button/

Contributions

https://codeforces.com/blog/entry/80438?#comment-666657

• make subdirectory a different repo? (will history be transferred to new repo?)
• are all contributors going to be added to the Discord?

Review Sorting (Silver)

Cleaned up sorting, added coordinate compression. Needs some more problems though. Can someone review it?

Full-Page Problem Editorials

Current todos

• Add support for official editorials, auto-populate field for USACO problems

Rename "How to Practice" or add more

Rename this module or add more to it.

Right now it's more "how / when to read editorial" rather than "how to practice" except for a few responses (I think it's because originally it was "how to read editorial").

General list of tips for each topic?

For major topics, maybe just a compiled list of tips from competitors regarding that topic just based on experience? Could set this guide apart from other resources, especially since we have so many op competitors ...

"Focus Problem" styling

modules usually start with a "focus problem" that's just a standard implementation of a concept. There should be custom styling for this

General

• Module descriptions!
• Module status
• Incomplete articles
  • clean up silver sorting?
  • plat
  • all of advanced
  • general
    • debugging
    • input & output
    • macros
• Resources
  • comments about what resource is about
  • starring (if two links cover roughly the same material then at most one should be starred)
  • do we have enough links (is there some source that we've been overlooking?)
  • videos (coordinate with Dr. Dean)
  • on the other hand, are some of the links not useful? (seems like topcoder tutorials are rarely starred and code format seems to be broken, maybe just remove some of them?)
• Adding implementations (maybe from my GitHub?)
  • consistent code formatting?
  • more languages
• Diagrams
  • ex. for slope trick
• Problems
  • tagging
  • sketches/editorials if they don't already exist
  • ordering them in order of difficulty (especially for bronze, what's the best way to do this?)
• Analytics

General

• how to practice
• contest strategy
• debugging
  • compilation flags
  • using a debugger

List of Excluded Problems

List CSES, recent USACO problems that are not currently included in the guide (with a bit of web scraping)?

(can we generate list of IDs for all unique problems included within the guide?)

Dark Mode

(from darren)

Update Content Documentation

Content docs haven't been updated in a really long time... are still missing some parts

"Contact Us" Form Validation

Require name, valid email, module, topic, minimum length for message

Gold

• convert "elementary number theory"
• add binary exponentiation?

Embedding Colored Tables from USACO Book

ex. Ch 11 - Prefix Sums

orz feature

Will be especially useful for people like benq and tmw :)

Restyle resources/problem lists for mobile

They aren't very mobile friendly; design can be improved.

Progress Tracking

Checkmarks for modules, progress bars like OIChecklist

TOC Modifications

• Mark module if it contains <IncompleteSection>

Change options?

can't solve falls under skipped, so replace it with "ignore"

QoL Improvement: Make USACO Guide a button

make the USACO Guide text and logo a button that sends you to the homepage

Chapter descriptions

We should add chapter descriptions (see content/ordering.ts) for chapters that need it

Adding Problems

• Add comments below each problem / link.
• Add problems from spreadsheet to corresponding topics
• Are we going to release spreadsheet?
• Clean up syllabus

Tabs at Top of Home Page

https://codeforces.com/blog/entry/80438?#comment-666701

Table of Contents Sidebar

We should get a Table of Contents sidebar, similar to this site: https://joshwcomeau.com/gatsby/using-netlify-functions-with-gatsby/

Code Blocks

• Wrap text in code blocks (ex. promotion counting solution in "Plat -> Merging")
• Within the first explanation for "Plat -> Slope" I had to put
  between the code blocks to make them render properly (otherwise the text within the blocks overlapped with text outside the blocks)

Left Nav Sidebar Improvements

• Styling should be fixed
• It should auto-scroll to the active link
• It should allow collapsing of groups of modules

Report an Issue / Get Help Buttons

Functionality incomplete

Login System

https://codeforces.com/blog/entry/80438?#comment-666686

sync progress over multiple devices/browsers, I think GAuth is more than enough

Modules ready for review? (done content-wise)

Content

Intro

1. About This Guide

• 1.1. Using This Guide
• 1.2. Modules
• 1.3. Code Conventions

2. Getting Started

• 2.1. Introduction to Competitive Programming
• 2.2. Choosing a Language
• 2.3. Running Code
• 2.4. Data Types
• 2.5. Input & Output
• 2.6. Expected Knowledge

3. General

• 3.1. Additional Resources
• 3.2. How to Practice
• 3.3. Contest Strategy
• 3.4. Contests
• 3.5. Olympiads

4. Language-Specific

• 4.1. Factors to Consider When Choosing a Language
• 4.2. Fast Input & Output
• 4.3. Debugging
• 4.4. C++ Tips & Tricks

5. Move to usaco.org?

• 5.1. Proposing Problems for USACO Monthlies
• 5.2. Making USACO Camp

Bronze

1. Basics

• 1.1. Time Complexity
• 1.2. Simulation
• 1.3. Rectangle Geometry
• 1.4. Introduction to Greedy Algorithms

2. Data Structures

• 2.1. Introduction to Data Structures
• 2.2. Pairs & Tuples
• 2.3. Unordered Maps & Sets

3. Complete Search

• 3.1. Complete Search
• 3.2. Generating Permutations

4. Graphs

• 4.1. Introduction to Graphs

Silver

1. Prefix Sums

• 1.1. Prefix Sums

2. Binary Search

• 2.1. Binary Search on a Sorted Array
• 2.2. Binary Search on the Answer

3. Sorting

• 3.1. Sorting Methods
• 3.2. Sorting with Custom Comparators
• 3.3. Greedy Algorithms

4. Ordered Sets & Maps

• 4.1. Introduction to Ordered Sets
• 4.2. C++ Sets with Custom Comparators
• 4.3. Harder Problems with Ordered Sets

5. Stacks & Queues

• 5.1. Introduction to Stacks & Queues
• 5.2. Sliding Window

6. Graphs

• 6.1. Depth First Search (DFS)
• 6.2. Flood Fill
• 6.3. Functional Graphs

Gold

1. Dynamic Programming

• 1.1. Introduction to Dynamic Programming

2. Number Theory

• 2.1. Introductory Number Theory

3. Graphs

• 3.1. Breadth First Search (BFS)
• 3.2. Topological Sort
• 3.3. Cycle Detection
• 3.4. Shortest Paths with Non-Negative Edge Weights

4. Range Queries

• 4.1. Static Range Queries
• 4.2. Max Suffix Query with Insertions Only
• 4.3. Point Update Range Sum
• 4.4. Point Update Range Query

5. Trees

• 5.1. Disjoint Set Union
• 5.2. Minimum Spanning Trees
• 5.3. Dynamic Programming on Trees
• 5.4. Euler Tour Technique

6. Hashing

• 6.1. A Faster Hash Table in C++
• 6.2. String Hashing

Plat

1. Range Queries

• 1.1. More Applications of Segment Tree
• 1.2. Range Update Range Query
• 1.3. 2D Range Queries
• 1.4. Square Root Decomposition

2. Trees

• 2.1. Binary Jumping
• 2.2. Small-To-Large Merging
• 2.3. Heavy-Light Decomposition
• 2.4. Centroid Decomposition

3. Dynamic Programming

• 3.1. Dynamic Programming on Bitmasks
• 3.2. Dynamic Programming on Ranges
• 3.3. More DP (come up with better name?)

4. Graphs

• 4.1. Shortest Paths with Negative Edge Weights
• 4.2. BCCs and 2CCs
• 4.3. Strongly Connected Components
• 4.4. Euler's Formula
• 4.5. Maximum Flow
• 4.6. Eulerian Tours

5. Strings

• 5.1. String Searching
• 5.2. Suffix Array

6. Geometry

• 6.1. Geometry Primitives
• 6.2. Sweep Line
• 6.3. Convex Hull
• 6.4. LineContainer
• 6.5. Lagrangian Relaxation
• 6.6. Slope Trick

7. Misc. Topics

• 7.1. Bitsets
• 7.2. Fracturing Search
• 7.3. oops what to call this

Problems

Intro

1. About This Guide

• 1.1. Using This Guide
• 1.2. Modules
• 1.3. Code Conventions

2. Getting Started

• 2.1. Introduction to Competitive Programming
• 2.2. Choosing a Language
• 2.3. Running Code
• 2.4. Data Types
• 2.5. Input & Output
• 2.6. Expected Knowledge

3. General

• 3.1. Additional Resources
• 3.2. How to Practice
• 3.3. Contest Strategy
• 3.4. Contests
• 3.5. Olympiads

4. Language-Specific

• 4.1. Factors to Consider When Choosing a Language
• 4.2. Fast Input & Output
• 4.3. Debugging
• 4.4. C++ Tips & Tricks

5. Move to usaco.org?

• 5.1. Proposing Problems for USACO Monthlies
• 5.2. Making USACO Camp

Bronze

1. Basics

• 1.1. Time Complexity
• 1.2. Simulation
• 1.3. Rectangle Geometry
• 1.4. Introduction to Greedy Algorithms

2. Data Structures

• 2.1. Introduction to Data Structures
• 2.2. Pairs & Tuples
• 2.3. Unordered Maps & Sets

3. Complete Search

• 3.1. Complete Search
• 3.2. Generating Permutations

4. Graphs

• 4.1. Introduction to Graphs

Silver

1. Prefix Sums

• 1.1. Prefix Sums

2. Binary Search

• 2.1. Binary Search on a Sorted Array
• 2.2. Binary Search on the Answer

3. Sorting

• 3.1. Sorting Methods
• 3.2. Sorting with Custom Comparators
• 3.3. Greedy Algorithms

4. Ordered Sets & Maps

• 4.1. Introduction to Ordered Sets
• 4.2. C++ Sets with Custom Comparators
• 4.3. Harder Problems with Ordered Sets

5. Stacks & Queues

• 5.1. Introduction to Stacks & Queues
• 5.2. Sliding Window

6. Graphs

• 6.1. Depth First Search (DFS)
• 6.2. Flood Fill
• 6.3. Functional Graphs

Gold

1. Dynamic Programming

• 1.1. Introduction to Dynamic Programming

2. Number Theory

• 2.1. Introductory Number Theory

3. Graphs

• 3.1. Breadth First Search (BFS)
• 3.2. Topological Sort
• 3.3. Cycle Detection
• 3.4. Shortest Paths with Non-Negative Edge Weights

4. Range Queries

• 4.1. Static Range Queries
• 4.2. Max Suffix Query with Insertions Only
• 4.3. Point Update Range Sum
• 4.4. Point Update Range Query

5. Trees

• 5.1. Disjoint Set Union
• 5.2. Minimum Spanning Trees
• 5.3. Dynamic Programming on Trees
• 5.4. Euler Tour Technique

6. Hashing

• 6.1. A Faster Hash Table in C++
• 6.2. String Hashing

Plat

1. Range Queries

• 1.1. More Applications of Segment Tree
• 1.2. Range Update Range Query
• 1.3. 2D Range Queries
• 1.4. Square Root Decomposition

2. Trees

• 2.1. Binary Jumping
• 2.2. Small-To-Large Merging
• 2.3. Heavy-Light Decomposition
• 2.4. Centroid Decomposition

3. Dynamic Programming

• 3.1. Dynamic Programming on Bitmasks
• 3.2. Dynamic Programming on Ranges
• 3.3. More DP (come up with better name?)

4. Graphs

• 4.1. Shortest Paths with Negative Edge Weights
• 4.2. BCCs and 2CCs
• 4.3. Strongly Connected Components
• 4.4. Euler's Formula
• 4.5. Maximum Flow
• 4.6. Eulerian Tours

5. Strings

• 5.1. String Searching
• 5.2. Suffix Array

6. Geometry

• 6.1. Geometry Primitives
• 6.2. Sweep Line
• 6.3. Convex Hull
• 6.4. LineContainer
• 6.5. Lagrangian Relaxation
• 6.6. Slope Trick

7. Misc. Topics

• 7.1. Bitsets
• 7.2. Fracturing Search
• 7.3. oops what to call this

Merge help and complain button?

Should we do this? If so, how do we ensure users will know to click the "complain" button when seeking help?

Perhaps we should rename everything to "Contact?"

Persist Language Preference

When the user selects a certain language (C++, Java, Python), it should:

1. Update all code snippets that have that supported language, and
2. Save that language preference locally for next time

Interactivity!

One of the primary benefits of our super-complex mdx/gatsby setup is we have the ability to customize basically everything, and to create very interactive modules (think quizzes, animations, live code editors, feedback forms, etc). Almost anything is possible!

Is interactivity worth adding to the guide (at a later time, of course)? If so, where/how? If someone has a specific example of where a custom interactive element for a guide would be helpful, I can code it up fairly quickly.

AC on problems?

allow users to mark problems as AC?

Authors page?

Somehow give credit to creators & authors of site, either on homepage, in the guide itself, or somewhere?

Is this wanted, and if so, what's the best way to do this?