Adding Solutions

Basic Debugging

Choosing a Language

Contest Strategy

Contests

Contributing

C++ With the Command Line

Data Types

How to Debug

Debugging C++

Expected Knowledge

Fast Input & Output

(Optional) C++ - Writing Generic Code

Input & Output

Introduction to Competitive Programming

(Optional) C++ - Lambda Expressions

Resources: Learning to Code

Introducing Modules

Olympiads

How to Practice

Resources: Competitive Programming

Resources: USA-Specific

Running Code Locally

Running Code Online

USACO Camp

USACO FAQs

USACO Monthlies

Using This Guide

Working With MDX

Ad Hoc Problems

Casework

Complete Search with Recursion

Additional Practice for USACO Bronze

Basic Complete Search

Introduction to Data Structures

Introduction to Graphs

Introduction to Greedy Algorithms

Introduction to Sets & Maps

Introduction to Sorting

Rectangle Geometry

Simulation

Time Complexity

Binary Search

Binary Search on a Sorted Array

Additional Practice for USACO Silver

Flood Fill

Introduction to Functional Graphs

Graph Traversal

Greedy Algorithms with Sorting

Intro to Bitwise Operators

Introduction to Tree Algorithms

More on Prefix Sums

Introduction to Prefix Sums

Priority Queues

Custom Comparators and Coordinate Compression

Two Pointers

DP on Trees - Solving For All Roots

Combinatorics

Additional Practice for USACO Gold

(Optional) Sorted Sets with Custom Comparators

Bitmask DP

Range DP

DP on Trees - Introduction

Disjoint Set Union

Digit DP

Divisibility

Hashing

(Optional) Hashmaps

Introduction to DP

More Operations on Sorted Sets

Knapsack DP

(Optional) LCA with Euler Tour

Longest Increasing Subsequence

Minimum Spanning Trees

(Optional) Meet In The Middle

Modular Arithmetic

Point Update Range Sum

Paths on Grids

Shortest Paths with Non-Negative Edge Weights

Sliding Window

Stacks

Optimizing Unimodal Functions

Topological Sort

(Optional) Euler Tour Technique

Shortest Paths with Unweighted Edges

2D Range Queries

Binary Jumping

(Optional) Bitsets

Centroid Decomposition

Additional Practice for USACO Platinum

Convex Hull

Convex Hull Trick

Divide & Conquer - DP

Divide & Conquer - SRQ

Sum over Subsets DP

Geometry Primitives

Heavy-Light Decomposition

Matrix Exponentiation

Small-To-Large Merging

Inclusion-Exclusion Principle

"use strict";
const {Fragment: _Fragment, jsx: _jsx, jsxs: _jsxs} = arguments[0];
const frontmatter = undefined;
function _createMdxContent(props) {
  const _components = {
    a: "a",
    h2: "h2",
    p: "p",
    strong: "strong",
    ...props.components
  }, {Asterisk, HeaderLink, Problems} = _components;
  if (!Asterisk) _missingMdxReference("Asterisk", true);
  if (!HeaderLink) _missingMdxReference("HeaderLink", true);
  if (!Problems) _missingMdxReference("Problems", true);
  return _jsxs(_Fragment, {
    children: [_jsxs(_components.h2, {
      id: "what-now",
      children: [_jsx(_components.a, {
        "aria-hidden": "true",
        tabIndex: "-1",
        className: "anchor before",
        href: "#what-now",
        children: _jsx(HeaderLink, {})
      }), "What Now?"]
    }), "\n", _jsxs(_components.p, {
      children: ["After completing this section on the USACO Guide, you should be comfortable with\nthe topics that have historically appeared in the USACO Silver\ndivision.", _jsx(Asterisk, {
        children: "Of course, there's always a chance that another topic,\npotentially from a higher division, will show up in future Silver\ncontests."
      }), " In order to maximize your chance at promoting, you should\naim to ", _jsx(_components.strong, {
        children: "practice"
      }), " by doing more problems."]
    }), "\n", _jsxs(_components.h2, {
      id: "uncategorized-problems",
      children: [_jsx(_components.a, {
        "aria-hidden": "true",
        tabIndex: "-1",
        className: "anchor before",
        href: "#uncategorized-problems",
        children: _jsx(HeaderLink, {})
      }), "Uncategorized Problems"]
    }), "\n", _jsxs(_components.p, {
      children: ["Below we list some problems that we think are roughly Silver level but don't\nreally fit in previous modules.", _jsx(Asterisk, {
        children: "either because there were too many\nproblems already, or because the problem requires more than one\nconcept"
      }), " The difficulties listed here are relative to the Silver\ndivision (difficulty is subjective and isn't always accurate though). Some of\nthese problems appeared in a higher division, but can still be solved using only\nSilver-level topics. We'll be expanding this list as we get more problem\nsuggestions."]
    }), "\n", _jsx(Problems, {
      problems: "problems",
      pageSize: 12
    }), "\n", _jsxs(_components.h2, {
      id: "final-thoughts",
      children: [_jsx(_components.a, {
        "aria-hidden": "true",
        tabIndex: "-1",
        className: "anchor before",
        href: "#final-thoughts",
        children: _jsx(HeaderLink, {})
      }), "Final Thoughts"]
    }), "\n", _jsxs(_components.p, {
      children: ["Refer to our FAQ to\n", _jsx(_components.a, {
        href: "/general/usaco-faq#q-where-can-i-find-more-practice-problems",
        children: "find more problems to practice"
      }), ".\nYou may also find the ", _jsx(_components.a, {
        href: "/general/practicing",
        children: "How to Practice"
      }), "\nmodule worth reading. Best of luck on future contests!"]
    })]
  });
}
function MDXContent(props = {}) {
  const {wrapper: MDXLayout} = props.components || ({});
  return MDXLayout ? _jsx(MDXLayout, {
    ...props,
    children: _jsx(_createMdxContent, {
      ...props
    })
  }) : _createMdxContent(props);
}
return {
  frontmatter,
  default: MDXContent
};
function _missingMdxReference(id, component) {
  throw new Error("Expected " + (component ? "component" : "object") + " `" + id + "` to be defined: you likely forgot to import, pass, or provide it.");
}


Final tips for Silver and additional practice problems.

Asterisk

problems

pageSize

Problems

2017 - Sabotage

"use strict";
const {Fragment: _Fragment, jsx: _jsx, jsxs: _jsxs} = arguments[0];
const frontmatter = undefined;
function _createMdxContent(props) {
 const _components = {
 a: "a",
 code: "code",
 h2: "h2",
 p: "p",
 pre: "pre",
 strong: "strong",
 ...props.components
 }, {CPPSection, HeaderLink, IncompleteSection, LanguageSection, MATHSPAN} = _components;
 if (!CPPSection) _missingMdxReference("CPPSection", true);
 if (!HeaderLink) _missingMdxReference("HeaderLink", true);
 if (!IncompleteSection) _missingMdxReference("IncompleteSection", true);
 if (!LanguageSection) _missingMdxReference("LanguageSection", true);
 if (!MATHSPAN) _missingMdxReference("MATHSPAN", true);
 return _jsxs(_Fragment, {
 children: [_jsxs(_components.h2, {
 id: "explanation",
 children: [_jsx(_components.a, {
 "aria-hidden": "true",
 tabIndex: "-1",
 className: "anchor before",
 href: "#explanation",
 children: _jsx(HeaderLink, {})
 }), "Explanation"]
 }), "\n", _jsx(IncompleteSection, {
 children: _jsx(_components.p, {
 children: "Editorial"
 })
 }), "\n", _jsxs(_components.h2, {
 id: "implementation",
 children: [_jsx(_components.a, {
 "aria-hidden": "true",
 tabIndex: "-1",
 className: "anchor before",
 href: "#implementation",
 children: _jsx(HeaderLink, {})
 }), "Implementation"]
 }), "\n", _jsxs(_components.p, {
 children: [_jsx(_components.strong, {
 children: "Time Complexity:"
 }), " ", _jsx(MATHSPAN, {
 className: "language-math math-inline",
 latex: "\\mathcal{O}(N)",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mi mathvariant=\"script\">O</mi><mo stretchy=\"false\">(</mo><mi>N</mi><mo stretchy=\"false\">)</mo></mrow><annotation encoding=\"application/x-tex\">\\mathcal{O}(N)</annotation></semantics></math>O(N)"
 })]
 }), "\n", _jsx(LanguageSection, {
 children: _jsx(CPPSection, {
 children: _jsx(_components.pre, {
 children: _jsx(_components.code, {
 className: "language-cpp",
 children: "#include <bits/stdc++.h>\nusing namespace std;\n\nusing ll = long long;\nusing ld = long double;\nusing db = double;\nusing str = string; // yay python!\n\nusing pi = pair<int, int>;\nusing pl = pair<ll, ll>;\nusing pd = pair<db, db>;\n\nusing vi = vector<int>;\nusing vb = vector<bool>;\nusing vl = vector<ll>;\nusing vd = vector<db>;\nusing vs = vector<str>;\nusing vpi = vector<pi>;\nusing vpl = vector<pl>;\nusing vpd = vector<pd>;\n\n#define tcT template <class T\n#define tcTU tcT, class U\n// ^ lol this makes everything look weird but I'll try it\ntcT > using V = vector<T>;\ntcT, size_t SZ > using AR = array<T, SZ>;\ntcT > using PR = pair<T, T>;\n\n// pairs\n#define mp make_pair\n#define f first\n#define s second\n\n// vectors\n// oops size(x), rbegin(x), rend(x) need C++17\n#define sz(x) int((x).size())\n#define bg(x) begin(x)\n#define all(x) bg(x), end(x)\n#define rall(x) x.rbegin(), x.rend()\n#define sor(x) sort(all(x))\n#define rsz resize\n#define ins insert\n#define ft front()\n#define bk back()\n#define pb push_back\n#define eb emplace_back\n#define pf push_front\n\n#define lb lower_bound\n#define ub upper_bound\ntcT > int lwb(V<T> &a, const T &b) { return int(lb(all(a), b) - bg(a)); }\n\n// loops\n#define FOR(i, a, b) for (int i = (a); i < (b); ++i)\n#define F0R(i, a) FOR(i, 0, a)\n#define ROF(i, a, b) for (int i = (b) - 1; i >= (a); --i)\n#define R0F(i, a) ROF(i, 0, a)\n#define trav(a, x) for (auto &a : x)\n\nconst int MOD = 1e9 + 7; // 998244353;\nconst int MX = 5e5 + 5;\nconst ll INF = 1e18; // not too close to LLONG_MAX\nconst ld PI = acos((ld)-1);\nconst int dx[4] = {1, 0, -1, 0}, dy[4] = {0, 1, 0, -1}; // for every grid problem!!\nmt19937 rng((uint32_t)chrono::steady_clock::now().time_since_epoch().count());\ntemplate <class T> using pqg = priority_queue<T, vector<T>, greater<T>>;\n\n// bitwise ops\n// also see https://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html\nconstexpr int pct(int x) { return __builtin_popcount(x); } // # of bits set\nconstexpr int bits(int x) { // assert(x >= 0); // make C++11 compatible until\n\t // USACO updates ...\n\treturn x == 0 ? 0 : 31 - __builtin_clz(x);\n} // floor(log2(x))\nconstexpr int p2(int x) { return 1 << x; }\nconstexpr int msk2(int x) { return p2(x) - 1; }\n\nll cdiv(ll a, ll b) {\n\treturn a / b + ((a ^ b) > 0 && a % b);\n} // divide a by b rounded up\nll fdiv(ll a, ll b) {\n\treturn a / b - ((a ^ b) < 0 && a % b);\n} // divide a by b rounded down\n\ntcT > bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; } // set a = min(a,b)\ntcT > bool ckmax(T &a, const T &b) { return a T fstTrue(T lo, T hi, U f) {\n\thi++;\n\tassert(lo <= hi); // assuming f is increasing\n\twhile (lo < hi) { // find first index such that f is true\n\t\tT mid = lo + (hi - lo) / 2;\n\t\tf(mid) ? hi = mid : lo = mid + 1;\n\t}\n\treturn lo;\n}\ntcTU > T lstTrue(T lo, T hi, U f) {\n\tlo--;\n\tassert(lo <= hi); // assuming f is decreasing\n\twhile (lo < hi) { // find first index such that f is true\n\t\tT mid = lo + (hi - lo + 1) / 2;\n\t\tf(mid) ? lo = mid : hi = mid - 1;\n\t}\n\treturn lo;\n}\ntcT > void remDup(vector<T> &v) { // sort and remove duplicates\n\tsort(all(v));\n\tv.erase(unique(all(v)), end(v));\n}\ntcTU > void erase(T &t, const U &u) { // don't erase\n\tauto it = t.find(u);\n\tassert(it != end(t));\n\tt.erase(it);\n} // element that doesn't exist from (multi)set\n\n// INPUT\n#define tcTUU tcT, class... U\ntcT > void re(complex<T> &c);\ntcTU > void re(pair<T, U> &p);\ntcT > void re(V<T> &v);\ntcT, size_t SZ > void re(AR<T, SZ> &a);\n\ntcT > void re(T &x) { cin >> x; }\nvoid re(db &d) {\n\tstr t;\n\tre(t);\n\td = stod(t);\n}\nvoid re(ld &d) {\n\tstr t;\n\tre(t);\n\td = stold(t);\n}\ntcTUU > void re(T &t, U &...u) {\n\tre(t);\n\tre(u...);\n}\n\ntcT > void re(complex<T> &c) {\n\tT a, b;\n\tre(a, b);\n\tc = {a, b};\n}\ntcTU > void re(pair<T, U> &p) { re(p.f, p.s); }\ntcT > void re(V<T> &x) { trav(a, x) re(a); }\ntcT, size_t SZ > void re(AR<T, SZ> &x) { trav(a, x) re(a); }\ntcT > void rv(int n, V<T> &x) {\n\tx.rsz(n);\n\tre(x);\n}\n\n// TO_STRING\n#define ts to_string\nstr ts(char c) { return str(1, c); }\nstr ts(const char *s) { return (str)s; }\nstr ts(str s) { return s; }\nstr ts(bool b) {\n#ifdef LOCAL\n\treturn b ? \"true\" : \"false\";\n#else\n\treturn ts((int)b);\n#endif\n}\ntcT > str ts(complex<T> c) {\n\tstringstream ss;\n\tss << c;\n\treturn ss.str();\n}\nstr ts(V<bool> v) {\n\tstr res = \"{\";\n\tF0R(i, sz(v)) res += char('0' + v[i]);\n\tres += \"}\";\n\treturn res;\n}\ntemplate <size_t SZ> str ts(bitset<SZ> b) {\n\tstr res = \"\";\n\tF0R(i, SZ) res += char('0' + b[i]);\n\treturn res;\n}\ntcTU > str ts(pair<T, U> p);\ntcT > str ts(T v) { // containers with begin(), end()\n#ifdef LOCAL\n\tbool fst = 1;\n\tstr res = \"{\";\n\tfor (const auto &x : v) {\n\t\tif (!fst) res += \", \";\n\t\tfst = 0;\n\t\tres += ts(x);\n\t}\n\tres += \"}\";\n\treturn res;\n#else\n\tbool fst = 1;\n\tstr res = \"\";\n\tfor (const auto &x : v) {\n\t\tif (!fst) res += \" \";\n\t\tfst = 0;\n\t\tres += ts(x);\n\t}\n\treturn res;\n\n#endif\n}\ntcTU > str ts(pair<T, U> p) {\n#ifdef LOCAL\n\treturn \"(\" + ts(p.f) + \", \" + ts(p.s) + \")\";\n#else\n\treturn ts(p.f) + \" \" + ts(p.s);\n#endif\n}\n\n// OUTPUT\ntcT > void pr(T x) { cout << ts(x); }\ntcTUU > void pr(const T &t, const U &...u) {\n\tpr(t);\n\tpr(u...);\n}\nvoid ps() { pr(\"\\n\"); } // print w/ spaces\ntcTUU > void ps(const T &t, const U &...u) {\n\tpr(t);\n\tif (sizeof...(u)) pr(\" \");\n\tps(u...);\n}\n\n// DEBUG\nvoid DBG() { cerr << \"]\" << endl; }\ntcTUU > void DBG(const T &t, const U &...u) {\n\tcerr << ts(t);\n\tif (sizeof...(u)) cerr << \", \";\n\tDBG(u...);\n}\n#ifdef LOCAL // compile with -DLOCAL, chk -> fake assert\n#define dbg(...) \\\n\tcerr << \"Line(\" << __LINE__ << \") -> [\" << #__VA_ARGS__ << \"]: [\", DBG(__VA_ARGS__)\n#define chk(...) \\\n\tif (!(__VA_ARGS__)) \\\n\t\tcerr << \"Line(\" << __LINE__ << \") -> function(\" << __FUNCTION__ \\\n\t\t << \") -> CHK FAILED: (\" << #__VA_ARGS__ << \")\" << \"\\n\", \\\n\t\t exit(0);\n#else\n#define dbg(...) 0\n#define chk(...) 0\n#endif\n\nvoid setPrec() { cout << fixed << setprecision(15); }\nvoid unsyncIO() { cin.tie(0)->sync_with_stdio(0); }\n// FILE I/O\nvoid setIn(str s) { freopen(s.c_str(), \"r\", stdin); }\nvoid setOut(str s) { freopen(s.c_str(), \"w\", stdout); }\nvoid setIO(str s = \"\") {\n\tunsyncIO();\n\tsetPrec();\n\t// cin.exceptions(cin.failbit);\n\t// throws exception when do smth illegal\n\t// ex. try to read letter into int\n\tif (sz(s)) setIn(s + \".in\"), setOut(s + \".out\"); // for USACO\n}\n\nint N, K, sub[MX], p[MX];\ndb need[MX];\n\nint main() {\n\tsetIO();\n\tre(N, K);\n\tFOR(i, 2, N + 1) re(p[i]);\n\tROF(i, 1, N + 1) {\n\t\tsub[i]++;\n\t\tif (i != 1) sub[p[i]] += sub[i];\n\t}\n\tdb ans = 0;\n\tROF(i, 1, N + 1) { // max x such that subtree of i mutinies\n\t\tif (sub[i] == 1) need[i] = 1;\n\t\tif (i != 1) ckmax(need[p[i]], min(need[i], db(sub[i]) / (sub[p[i]] - 1)));\n\t\tif (sub[i] > K) ckmax(ans, need[i]);\n\t}\n\tcout << fixed << setprecision(9) << ans;\n}\n"
 })
 })
 })
 })]
 });
}
function MDXContent(props = {}) {
 const {wrapper: MDXLayout} = props.components || ({});
 return MDXLayout ? _jsx(MDXLayout, {
 ...props,
 children: _jsx(_createMdxContent, {
 ...props
 })
 }) : _createMdxContent(props);
}
return {
 frontmatter,
 default: MDXContent
};
function _missingMdxReference(id, component) {
 throw new Error("Expected " + (component ? "component" : "object") + " `" + id + "` to be defined: you likely forgot to import, pass, or provide it.");
}

Sabotage

IncompleteSection

CPPSection

LanguageSection

Table of Contents

Table of Contents

Explanation

This section is not complete.

Implementation

Join the USACO Forum!