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

Longest Increasing Subsequence

Minimum Spanning Trees

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

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

Range Update Range Query

Directly simulating the problem statement.

Resource

Resources

Asterisk

problem

FocusProblem

CPPSection

JavaSection

PySection

LanguageSection

problems

hideSuggestProblemButton

Problems

Mowing the Field

"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, JavaSection, LanguageSection, MATHSPAN, PySection} = _components;
 if (!CPPSection) _missingMdxReference("CPPSection", true);
 if (!HeaderLink) _missingMdxReference("HeaderLink", true);
 if (!JavaSection) _missingMdxReference("JavaSection", true);
 if (!LanguageSection) _missingMdxReference("LanguageSection", true);
 if (!MATHSPAN) _missingMdxReference("MATHSPAN", true);
 if (!PySection) _missingMdxReference("PySection", true);
 return _jsxs(_Fragment, {
 children: [_jsx(_components.p, {
 children: _jsx(_components.a, {
 href: "http://www.usaco.org/current/data/sol_mowing_bronze_jan16.html",
 rel: "nofollow",
 target: "_blank",
 children: "Official Analysis (Java)"
 })
 }), "\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(_components.p, {
 children: "We can simulate Farmer John's movements across his field and update our\nanswer when he comes across the same patch of grass."
 }), "\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}(NS \\log (NS))",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mi mathvariant=\"script\">O</mi><mo stretchy=\"false\">(</mo><mi>N</mi><mi>S</mi><mi>log</mi><mo>⁡</mo><mo stretchy=\"false\">(</mo><mi>N</mi><mi>S</mi><mo stretchy=\"false\">)</mo><mo stretchy=\"false\">)</mo></mrow><annotation encoding=\"application/x-tex\">\\mathcal{O}(NS \\log (NS))</annotation></semantics></math>O(NSlog(NS))"
 })]
 }), "\n", _jsxs(LanguageSection, {
 children: [_jsx(CPPSection, {
 children: _jsx(_components.pre, {
 children: _jsx(_components.code, {
 className: "language-cpp",
 children: "#include <bits/stdc++.h>\nusing namespace std;\n\nint main() {\n\tfreopen(\"mowing.in\", \"r\", stdin);\n\tint n;\n\tcin >> n;\n\tvector<pair<char, int>> steps(n);\n\tfor (auto &[dir, num_steps] : steps) { cin >> dir >> num_steps; }\n\n\t// FJ's starting position.\n\tpair<int, int> curr{0, 0};\n\t// Make an ordered map, and mark off steps.\n\t// We'll first mark off his starting position.\n\tmap<pair<int, int>, int> visits{{curr, 0}};\n\n\tint time = 0;\n\tint max_regrow = INT32_MAX;\n\tfor (const auto &[dir, num_steps] : steps) {\n\t\t// Get the direction Farmer John is moving.\n\t\tpair<int, int> delta;\n\t\tswitch (dir) {\n\t\tcase 'N':\n\t\t\tdelta = pair<int, int>{0, 1};\n\t\t\tbreak;\n\t\tcase 'W':\n\t\t\tdelta = pair<int, int>{-1, 0};\n\t\t\tbreak;\n\t\tcase 'E':\n\t\t\tdelta = pair<int, int>{1, 0};\n\t\t\tbreak;\n\t\tcase 'S':\n\t\t\tdelta = pair<int, int>{0, -1};\n\t\t\tbreak;\n\t\t}\n\n\t\tfor (int i = 0; i < num_steps; i++) {\n\t\t\t// Update our current position.\n\t\t\tcurr = pair<int, int>{curr.first + delta.first, curr.second + delta.second};\n\t\t\ttime++;\n\n\t\t\t// Check if FJ's been to this patch of grass before.\n\t\t\tif (visits.count(curr)) {\n\t\t\t\tmax_regrow = min(max_regrow, time - visits[curr]);\n\t\t\t}\n\n\t\t\t// Update the last time FJ has come upon this patch of grass.\n\t\t\tvisits[curr] = time;\n\t\t}\n\t}\n\n\tfreopen(\"mowing.out\", \"w\", stdout);\n\t// Output -1 if FJ has never gone back to the same patch of grass.\n\tcout << (max_regrow == INT32_MAX ? -1 : max_regrow) << endl;\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 Mowing {\n\t// BeginCodeSnip{Step Class}\n\tstatic class Step {\n\t\tchar dir;\n\t\tint numSteps;\n\n\t\tpublic Step(char dir, int numSteps) {\n\t\t\tthis.dir = dir;\n\t\t\tthis.numSteps = numSteps;\n\t\t}\n\t}\n\t// EndCodeSnip\n\n\tpublic static void main(String[] args) throws IOException {\n\t\tBufferedReader read = new BufferedReader(new FileReader(\"mowing.in\"));\n\t\tint n = Integer.parseInt(read.readLine());\n\t\tStep[] steps = new Step[n];\n\t\tfor (int s = 0; s < n; s++) {\n\t\t\tStringTokenizer step = new StringTokenizer(read.readLine());\n\t\t\tsteps[s] = new Step(step.nextToken().charAt(0),\n\t\t\t Integer.parseInt(step.nextToken()));\n\t\t}\n\t\tread.close();\n\n\t\t// FJ's starting position.\n\t\tPoint curr = new Point(0, 0);\n\t\t// Make a hashmap, and mark off steps.\n\t\t// We'll first mark off his starting position.\n\t\tMap<Point, Integer> visits = new HashMap<>(Map.of(curr, 0));\n\n\t\tint time = 0;\n\t\tint maxRegrow = Integer.MAX_VALUE;\n\t\tfor (Step s : steps) {\n\t\t\tfor (int i = 0; i < s.numSteps; i++) {\n\t\t\t\t// Update our current position.\n\t\t\t\tcurr = curr.next(s.dir);\n\t\t\t\ttime++;\n\n\t\t\t\t// Check if FJ's been to this patch of grass before.\n\t\t\t\tif (visits.containsKey(curr)) {\n\t\t\t\t\tmaxRegrow = Math.min(maxRegrow, time - visits.get(curr));\n\t\t\t\t}\n\n\t\t\t\t// Update the last time FJ has come upon this patch of grass.\n\t\t\t\tvisits.put(curr, time);\n\t\t\t}\n\t\t}\n\n\t\tPrintWriter written = new PrintWriter(\"mowing.out\");\n\t\t// Output -1 if FJ has never gone back to the same patch of grass.\n\t\twritten.println(maxRegrow == Integer.MAX_VALUE ? -1 : maxRegrow);\n\t\twritten.close();\n\t}\n}\n\n// BeginCodeSnip{Point Class}\nclass Point {\n\tint x, y;\n\n\tpublic Point(int x, int y) {\n\t\tthis.x = x;\n\t\tthis.y = y;\n\t}\n\n\t/**\n\t * @return The point reached after moving in the given direction from this\n\t * point.\n\t */\n\tpublic Point next(char dir) {\n\t\tswitch (dir) {\n\t\tcase 'N':\n\t\t\treturn new Point(x, y + 1);\n\t\tcase 'W':\n\t\t\treturn new Point(x - 1, y);\n\t\tcase 'E':\n\t\t\treturn new Point(x + 1, y);\n\t\tcase 'S':\n\t\t\treturn new Point(x, y - 1);\n\t\tdefault:\n\t\t\treturn this;\n\t\t}\n\t}\n\n\t@Override\n\tpublic String toString() {\n\t\treturn String.format(\"(%d, %d)\", x, y);\n\t}\n\n\t@Override\n\tpublic int hashCode() {\n\t\treturn Objects.hash(x, y);\n\t}\n\n\t@Override\n\tpublic boolean equals(Object obj) {\n\t\treturn obj instanceof Point && x == ((Point)obj).x && y == ((Point)obj).y;\n\t}\n}\n// EndCodeSnip\n"
 })
 })
 }), _jsx(PySection, {
 children: _jsx(_components.pre, {
 children: _jsx(_components.code, {
 className: "language-py",
 children: "with open(\"mowing.in\") as read:\n\tn = int(read.readline())\n\tsteps = []\n\tfor _ in range(n):\n\t\tdir_, num_steps = map(str, read.readline().split())\n\t\tsteps.append((dir_, int(num_steps)))\n\n# FJ's starting position.\ncurr = (0, 0)\n# Make a hashmap, and mark off steps.\n# We'll first mark off his starting position.\nvisits = {curr: 0}\n\ntime = 0\nmax_regrow = float(\"inf\")\nfor dir_, num_steps in steps:\n\t# Get the direction Farmer John is moving.\n\tif dir_ == \"N\":\n\t\tdelta = 0, 1\n\telif dir_ == \"W\":\n\t\tdelta = -1, 0\n\telif dir_ == \"E\":\n\t\tdelta = 1, 0\n\telif dir_ == \"S\":\n\t\tdelta = 0, -1\n\n\tfor _ in range(int(num_steps)):\n\t\t# Update our current position.\n\t\tcurr = (curr[0] + delta[0], curr[1] + delta[1])\n\t\ttime += 1\n\n\t\t# Check if FJ's been to this patch of grass before.\n\t\tif curr in visits:\n\t\t\tmax_regrow = min(max_regrow, time - visits[curr])\n\t\t# Update the last time FJ has come upon this patch of grass.\n\t\tvisits[curr] = time\n\n# Output -1 if FJ has never gone back to the same patch of grass.\noutput = -1 if max_regrow == float(\"inf\") else max_regrow\nprint(output, file=open(\"mowing.out\", \"w\"))\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.");
}

Table of Contents

Table of Contents

Explanation

Implementation

Join the USACO Forum!