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

/*Resources below (including starred ones) are optional.*/
/*The following problems require relatively little programming experience and no algorithmic knowledge.*/
/*However, make sure to check [Code Conventions](/general/code-con) for the templates that will be used for code snippets in later modules!
*/
"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",
    li: "li",
    p: "p",
    ul: "ul",
    ...props.components
  }, {CPPSection, HeaderLink, Info, JavaSection, LanguageSection, Problems, PySection, Resource, Resources, Warning} = _components;
  if (!CPPSection) _missingMdxReference("CPPSection", true);
  if (!HeaderLink) _missingMdxReference("HeaderLink", true);
  if (!Info) _missingMdxReference("Info", true);
  if (!JavaSection) _missingMdxReference("JavaSection", true);
  if (!LanguageSection) _missingMdxReference("LanguageSection", true);
  if (!Problems) _missingMdxReference("Problems", true);
  if (!PySection) _missingMdxReference("PySection", true);
  if (!Resource) _missingMdxReference("Resource", true);
  if (!Resources) _missingMdxReference("Resources", true);
  if (!Warning) _missingMdxReference("Warning", true);
  return _jsxs(_Fragment, {
    children: [_jsxs(_components.h2, {
      id: "expected-knowledge",
      children: [_jsx(_components.a, {
        "aria-hidden": "true",
        tabIndex: "-1",
        className: "anchor before",
        href: "#expected-knowledge",
        children: _jsx(HeaderLink, {})
      }), "Expected Knowledge"]
    }), "\n", _jsx(Info, {
      title: "What if I'm not comfortable with basic coding (yet)?",
      children: _jsxs(_components.p, {
        children: ["Check ", _jsx(_components.a, {
          href: "/general/resources-learning-to-code",
          children: "our resources page"
        }), "!"]
      })
    }), "\n", _jsx(_components.p, {
      children: "This guide assumes you know the following topics in either C++, Java, or Python:"
    }), "\n", _jsxs(_components.ul, {
      children: ["\n", _jsxs(_components.li, {
        children: ["Variables\n", _jsxs(_components.ul, {
          children: ["\n", _jsx(_components.li, {
            children: "Data types"
          }), "\n"]
        }), "\n"]
      }), "\n", _jsx(_components.li, {
        children: "Reading Input"
      }), "\n", _jsx(_components.li, {
        children: "Writing Output"
      }), "\n", _jsx(_components.li, {
        children: "Loops"
      }), "\n", _jsx(_components.li, {
        children: "If / Else"
      }), "\n", _jsx(_components.li, {
        children: "Logical operators"
      }), "\n", _jsxs(_components.li, {
        children: ["Functions\n", _jsxs(_components.ul, {
          children: ["\n", _jsx(_components.li, {
            children: "Basic Recursion (a function calling itself)"
          }), "\n"]
        }), "\n"]
      }), "\n", _jsxs(_components.li, {
        children: ["Arrays\n", _jsxs(_components.ul, {
          children: ["\n", _jsx(_components.li, {
            children: "Multidimensional Arrays"
          }), "\n"]
        }), "\n"]
      }), "\n"]
    }), "\n", _jsxs(LanguageSection, {
      children: [_jsx(CPPSection, {
        children: _jsx(Info, {
          title: "Pro Tip",
          children: _jsxs(_components.p, {
            children: ["For C++, knowledge of pointers, ", _jsx(_components.code, {
              children: "struct"
            }), "s and ", _jsx(_components.code, {
              children: "class"
            }), "es is useful but not\nrequired."]
          })
        })
      }), _jsx(JavaSection, {
        children: _jsx(_components.p, {
          children: "In particular, contestants using Java should be familiar with roughly the first\nhalf of AP Computer Science A."
        })
      }), _jsx(PySection, {})]
    }), "\n", _jsxs(_components.h2, {
      id: "getting-started",
      children: [_jsx(_components.a, {
        "aria-hidden": "true",
        tabIndex: "-1",
        className: "anchor before",
        href: "#getting-started",
        children: _jsx(HeaderLink, {})
      }), "Getting Started"]
    }), "\n", _jsx(_components.p, {
      children: "It's probably best to start with shorter problems than those you typically find\nin USACO Bronze. The following resources may be helpful for familiarizing\nyourself with your language of choice."
    }), "\n", "\n", _jsxs(Resources, {
      children: [_jsx(Resource, {
        source: "CodeSignal",
        title: "Arcade, Interview Practice",
        url: "https://app.codesignal.com/",
        children: _jsx(_components.p, {
          children: "no need to handle input or output"
        })
      }), _jsx(Resource, {
        source: "VPlanet",
        title: "Learn to Code",
        url: "https://www.vplanetcoding.com/course1-usaco-basics",
        children: _jsx(_components.p, {
          children: "basic problemsets with and without nested loops"
        })
      }), _jsx(Resource, {
        source: "CSES",
        title: "Introductory Problems",
        url: "https://cses.fi/problemset/list/",
        children: _jsx(_components.p, {
          children: "up to and including \"Palindrome Reorder\""
        })
      })]
    }), "\n", _jsxs(_components.h2, {
      id: "introductory-usaco-bronze-problems",
      children: [_jsx(_components.a, {
        "aria-hidden": "true",
        tabIndex: "-1",
        className: "anchor before",
        href: "#introductory-usaco-bronze-problems",
        children: _jsx(HeaderLink, {})
      }), "Introductory USACO Bronze Problems"]
    }), "\n", "\n", _jsx(Problems, {
      problems: "general"
    }), "\n", _jsx(_components.p, {
      children: "Once you're done with these, you should continue onto the rest of Bronze."
    }), "\n", _jsx(Warning, {
      children: _jsx(_components.p, {
        children: "Some modules in the \"General\" section (ex. Fast Input & Output) are not relevant\nfor USACO Bronze. You should skip these for now and return to these later."
      })
    })]
  });
}
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.");
}


What you're expected to know before continuing onto the rest of USACO Bronze.

title

Info

CPPSection

JavaSection

PySection

LanguageSection

Resource

Resources

problems

Problems

Warning

Word Processor

"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, JavaSection, LanguageSection, MATHSPAN, PySection, Spoiler, YouTube} = _components;
 if (!CPPSection) _missingMdxReference("CPPSection", true);
 if (!HeaderLink) _missingMdxReference("HeaderLink", true);
 if (!IncompleteSection) _missingMdxReference("IncompleteSection", true);
 if (!JavaSection) _missingMdxReference("JavaSection", true);
 if (!LanguageSection) _missingMdxReference("LanguageSection", true);
 if (!MATHSPAN) _missingMdxReference("MATHSPAN", true);
 if (!PySection) _missingMdxReference("PySection", true);
 if (!Spoiler) _missingMdxReference("Spoiler", true);
 if (!YouTube) _missingMdxReference("YouTube", true);
 return _jsxs(_Fragment, {
 children: [_jsx(_components.p, {
 children: _jsx(_components.a, {
 href: "http://www.usaco.org/current/data/sol_word_bronze_jan20.html",
 rel: "nofollow",
 target: "_blank",
 children: "Official Analysis (Python)"
 })
 }), "\n", _jsxs(_components.h2, {
 id: "video-solution",
 children: [_jsx(_components.a, {
 "aria-hidden": "true",
 tabIndex: "-1",
 className: "anchor before",
 href: "#video-solution",
 children: _jsx(HeaderLink, {})
 }), "Video Solution"]
 }), "\n", _jsx(_components.p, {
 children: "By Jeffrey Meng"
 }), "\n", _jsx(YouTube, {
 id: "lE6mM6--wR0"
 }), "\n", _jsx(Spoiler, {
 title: "Video Solution Code",
 children: _jsxs(LanguageSection, {
 children: [_jsx(CPPSection, {
 children: _jsx(_components.pre, {
 children: _jsx(_components.code, {
 className: "language-cpp",
 children: "#include <cstdio>\n#include <iostream>\n#include <string>\n\nusing namespace std;\n\nint main() {\n\tfreopen(\"word.in\", \"r\", stdin);\n\tfreopen(\"word.out\", \"w\", stdout);\n\n\t// Read N & K.\n\tint N, K;\n\tcin >> N >> K;\n\n\t/*\n\t * This variable is used for storing the number of characters\n\t * on the current line but NOT including the space characters.\n\t */\n\tint word_length = 0;\n\n\tfor (int i = 0; i < N; i++) {\n\t\tstring S;\n\t\tcin >> S; // Read the next word.\n\t\tword_length += S.length();\n\n\t\t// If it still satisfies the constraint, print the word on the same\n\t\t// line.\n\t\tif (word_length <= K) {\n\t\t\t// If it isn't the first ever word, print a space character.\n\t\t\tif (i > 0) { cout << \" \"; }\n\t\t\tcout << S;\n\t\t} else {\n\t\t\t// If it's over the line limit, print a new line first.\n\t\t\tcout << '\\n' << S;\n\t\t\tword_length = S.length();\n\t\t}\n\t}\n}\n"
 })
 })
 }), _jsx(JavaSection, {
 children: _jsx(_components.pre, {
 children: _jsx(_components.code, {
 className: "language-java",
 children: "import java.io.*;\nimport java.util.*;\n\npublic class WordProcessor {\n\tpublic static void main(String[] args) throws IOException {\n\t\tBufferedReader in = new BufferedReader(new FileReader(\"word.in\"));\n\n\t\tStringTokenizer st = new StringTokenizer(in.readLine());\n\t\tint N = Integer.parseInt(st.nextToken());\n\t\tint K = Integer.parseInt(st.nextToken());\n\n\t\tst = new StringTokenizer(in.readLine());\n\t\tString[] words = new String[N];\n\t\tfor (int i = 0; i < N; i++) { words[i] = st.nextToken(); }\n\n\t\tPrintWriter out = new PrintWriter(\"word.out\");\n\n\t\tList<String> currentLine = new ArrayList<>();\n\t\tint currentLineLength = 0;\n\t\tfor (String word : words) {\n\t\t\tif (currentLineLength + word.length() <= K) {\n\t\t\t\tcurrentLine.add(word);\n\t\t\t\tcurrentLineLength += word.length();\n\t\t\t} else {\n\t\t\t\tout.println(String.join(\" \", currentLine));\n\t\t\t\tcurrentLine.clear();\n\t\t\t\tcurrentLine.add(word);\n\t\t\t\tcurrentLineLength = word.length();\n\t\t\t}\n\t\t}\n\t\tout.println(String.join(\" \", currentLine));\n\n\t\tout.close();\n\t}\n}\n"
 })
 })
 })]
 })
 }), "\n", _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", _jsxs(LanguageSection, {
 children: [_jsx(CPPSection, {
 children: _jsx(_components.pre, {
 children: _jsx(_components.code, {
 className: "language-cpp",
 children: "#include <cstdio>\n#include <iostream>\n#include <string>\n\nusing namespace std;\n\nint main() {\n\tfreopen(\"word.in\", \"r\", stdin);\n\tfreopen(\"word.out\", \"w\", stdout);\n\n\tint N, K;\n\tcin >> N >> K;\n\n\t// Number of characters on the current line (not including spaces)\n\tint word_len = 0;\n\tfor (int i = 0; i < N; i++) {\n\t\tstring word;\n\t\tcin >> word;\n\t\t// Get the new length if we were to put the word on the current line.\n\t\tword_len += word.length();\n\t\tif (word_len <= K) {\n\t\t\t// Print a space if it isn't the first word.\n\t\t\tif (i != 0) { cout << ' '; }\n\t\t\tcout << word;\n\t\t} else {\n\t\t\tcout << \"\\n\" << word;\n\t\t\tword_len = word.length();\n\t\t}\n\t}\n}\n"
 })
 })
 }), _jsx(JavaSection, {
 children: _jsx(_components.pre, {
 children: _jsx(_components.code, {
 className: "language-java",
 children: "import java.io.*;\nimport java.util.*;\n\npublic class Word {\n\tpublic static void main(String[] args) throws IOException {\n\t\tBufferedReader read = new BufferedReader(new FileReader(\"word.in\"));\n\t\tStringTokenizer initial = new StringTokenizer(read.readLine());\n\t\tinitial.nextToken(); // we won't need N\n\t\tint maxWidth = Integer.parseInt(initial.nextToken());\n\n\t\tString[] essay = read.readLine().split(\" \");\n\t\tStringBuilder formatted = new StringBuilder();\n\t\tint rnLength = 0;\n\t\tfor (String w : essay) {\n\t\t\tif (rnLength + w.length() > maxWidth) {\n\t\t\t\tformatted.deleteCharAt(formatted.length() - 1);\n\t\t\t\tformatted.append('\\n');\n\t\t\t\trnLength = 0;\n\t\t\t}\n\t\t\tformatted.append(w).append(' ');\n\t\t\trnLength += w.length();\n\t\t}\n\t\tformatted.deleteCharAt(formatted.length() - 1);\n\n\t\tPrintWriter written = new PrintWriter(\"word.out\");\n\t\twritten.println(formatted);\n\t\twritten.close();\n\t}\n}\n"
 })
 })
 }), _jsx(PySection, {
 children: _jsx(_components.pre, {
 children: _jsx(_components.code, {
 className: "language-py",
 children: "with open(\"word.in\") as read:\n\tmax_width = int(read.readline().split()[1])\n\tessay = read.readline().split()\n\nformatted = \"\"\nrn_length = 0\nfor w in essay:\n\t# ok, this word exceeds the limit, let's wrap it around\n\tif rn_length + len(w) > max_width:\n\t\tformatted = formatted[:-1] + \"\\n\"\n\t\trn_length = 0\n\tformatted += w + \" \"\n\trn_length += len(w)\nformatted = formatted[:-1]\n\nwith open(\"word.out\", \"w\") as written:\n\tfor line in formatted.split(\"\\n\"):\n\t\tprint(line, file=written)\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.");
}

YouTube

Spoiler

IncompleteSection

Table of Contents

Table of Contents

Video Solution

Explanation

This section is not complete.

Implementation

Join the USACO Forum!