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

Binary searching on arbitrary monotonic functions.

Angry Cows

"use strict";
const {Fragment: _Fragment, jsx: _jsx, jsxs: _jsxs} = arguments[0];
const frontmatter = undefined;
function _createMdxContent(props) {
 const _components = {
 a: "a",
 code: "code",
 h1: "h1",
 h2: "h2",
 li: "li",
 p: "p",
 pre: "pre",
 strong: "strong",
 ul: "ul",
 ...props.components
 }, {CPPSection, HeaderLink, JavaSection, LanguageSection, MATHSPAN, PySection, Spoiler, Warning, YouTube} = _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);
 if (!Spoiler) _missingMdxReference("Spoiler", true);
 if (!Warning) _missingMdxReference("Warning", true);
 if (!YouTube) _missingMdxReference("YouTube", true);
 return _jsxs(_Fragment, {
 children: [_jsxs(_components.h1, {
 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 David Zhou"
 }), "\n", _jsx(_components.p, {
 children: "Note: The video solution might not be the same as other solutions. Code in C++, Python, and Java."
 }), "\n", _jsx(Spoiler, {
 title: "Video Solution",
 children: _jsx(YouTube, {
 id: "Xdj-OybMSYM"
 })
 }), "\n", _jsxs(Spoiler, {
 title: "Hint 1",
 children: [_jsx(_components.p, {
 children: "For problems where we're asked to minimize/maximize some value, we can ask ourselves these questions:"
 }), _jsxs(_components.ul, {
 children: ["\n", _jsx(_components.li, {
 children: "How does the \"validity\" of the answer change as we increase/decrease it?"
 }), "\n", _jsx(_components.li, {
 children: "What conditions must be true of an optimal solution?"
 }), "\n"]
 })]
 }), "\n", _jsxs(Spoiler, {
 title: "Answer to Hint 1",
 children: [_jsxs(_components.p, {
 children: ["Note that for the minimum power that we launch a cow with is monotonic, since there is a set point where smaller values of ", _jsx(MATHSPAN, {
 className: "language-math math-inline",
 latex: "R",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mi>R</mi></mrow><annotation encoding=\"application/x-tex\">R</annotation></semantics></math>R"
 }), " will stop working."]
 }), _jsxs(_components.p, {
 children: ["This implies a binary search on the power ", _jsx(MATHSPAN, {
 className: "language-math math-inline",
 latex: "R",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mi>R</mi></mrow><annotation encoding=\"application/x-tex\">R</annotation></semantics></math>R"
 }), "."]
 })]
 }), "\n", _jsxs(_components.h1, {
 id: "solution",
 children: [_jsx(_components.a, {
 "aria-hidden": "true",
 tabIndex: "-1",
 className: "anchor before",
 href: "#solution",
 children: _jsx(HeaderLink, {})
 }), "Solution"]
 }), "\n", _jsxs(Spoiler, {
 title: "Solution",
 children: [_jsx(_components.p, {
 children: _jsx(_components.a, {
 href: "http://www.usaco.org/current/data/sol_angry_gold_jan16.html",
 rel: "nofollow",
 target: "_blank",
 children: "Official Analysis (C++ and Java)"
 })
 }), _jsxs(Warning, {
 children: [_jsx(_components.p, {
 children: "The second and third solutions in the analysis fail on the following test case:"
 }), _jsx(_components.pre, {
 children: _jsx(_components.code, {
 children: "2\n0\n1\n"
 })
 }), _jsx(_components.p, {
 children: "The second one gives the wrong answer, and the third errors."
 })]
 }), _jsxs(_components.h2, {
 id: "explanation",
 children: [_jsx(_components.a, {
 "aria-hidden": "true",
 tabIndex: "-1",
 className: "anchor before",
 href: "#explanation",
 children: _jsx(HeaderLink, {})
 }), "Explanation"]
 }), _jsxs(_components.p, {
 children: ["From the hints, we'll start binary searching on the initial power ", _jsx(MATHSPAN, {
 className: "language-math math-inline",
 latex: "R",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mi>R</mi></mrow><annotation encoding=\"application/x-tex\">R</annotation></semantics></math>R"
 }), ". Now, we've reduced the problem into checking if a fixed power ", _jsx(MATHSPAN, {
 className: "language-math math-inline",
 latex: "R",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mi>R</mi></mrow><annotation encoding=\"application/x-tex\">R</annotation></semantics></math>R"
 }), " works for our set of haybales."]
 }), _jsxs(_components.p, {
 children: ["There are many ways to approach this (see the ", _jsx(_components.a, {
 href: "http://www.usaco.org/current/data/sol_angry_gold_jan16.html",
 rel: "nofollow",
 target: "_blank",
 children: "Official Analysis"
 }), " for more information!), but perhaps the most straightforward way is running a second binary search on the maximum point we can place our cow."]
 }), _jsxs(_components.p, {
 children: ["This works because just like our power, there exists a set point where a cow being launched at a coordinate will not knock out all the haybales to the left/right. Since ", _jsx(MATHSPAN, {
 className: "language-math math-inline",
 latex: "N \\leq 5 \\cdot 10^4",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mi>N</mi><mo>≤</mo><mn>5</mn><mo>⋅</mo><msup><mn>10</mn><mn>4</mn></msup></mrow><annotation encoding=\"application/x-tex\">N \\leq 5 \\cdot 10^4</annotation></semantics></math>N≤5⋅104"
 }), ", we can simulate these explosions naively."]
 }), _jsxs(_components.h2, {
 id: "implementation",
 children: [_jsx(_components.a, {
 "aria-hidden": "true",
 tabIndex: "-1",
 className: "anchor before",
 href: "#implementation",
 children: _jsx(HeaderLink, {})
 }), "Implementation"]
 }), _jsxs(_components.p, {
 children: [_jsx(_components.strong, {
 children: "Time Complexity"
 }), ": ", _jsx(MATHSPAN, {
 className: "language-math math-inline",
 latex: "\\mathcal{O}(N \\log^2 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><msup><mrow><mi>log</mi><mo>⁡</mo></mrow><mn>2</mn></msup><mi>N</mi><mo stretchy=\"false\">)</mo></mrow><annotation encoding=\"application/x-tex\">\\mathcal{O}(N \\log^2 N)</annotation></semantics></math>O(Nlog2N)"
 })]
 }), _jsxs(LanguageSection, {
 children: [_jsx(CPPSection, {
 children: _jsx(_components.pre, {
 children: _jsx(_components.code, {
 className: "language-cpp",
 children: "#include <algorithm>\n#include <climits>\n#include <iomanip>\n#include <iostream>\n#include <vector>\nusing namespace std;\n\nint n;\nvector<int> haybales;\n\nbool valid(int pos, int idx, int power, int dir) {\n\t// exploded leftmost haybale\n\tif (idx <= 0 && dir == 0) { return (idx < 0 || pos - power <= haybales[idx]); }\n\n\t// exploded rightmost haybale\n\tif (idx >= n - 1 && dir == 1) { return idx >= n || pos + power >= haybales[idx]; }\n\n\tif (dir == 0) { // left\n\t\tif (pos - power <= haybales[0]) { return true; }\n\n\t\t// go as left as possible\n\t\tint next_idx = idx;\n\t\twhile (next_idx >= 0 && pos - power <= haybales[next_idx]) { next_idx--; }\n\n\t\t// more movement is not possible\n\t\tif (next_idx == idx) { return false; }\n\n\t\treturn valid(haybales[next_idx + 1], next_idx, power - 2, dir);\n\t} else { // right\n\t\tif (pos + power >= haybales[n - 1]) { return true; }\n\n\t\t// go as right as possible\n\t\tint next_idx = idx;\n\t\twhile (next_idx < n && haybales[next_idx] <= pos + power) { next_idx++; }\n\n\t\t// more movement is not possible\n\t\tif (next_idx == idx) { return false; }\n\n\t\treturn valid(haybales[next_idx - 1], next_idx, power - 2, dir);\n\t}\n\n\treturn false;\n}\n\nint main() {\n\tfreopen(\"angry.in\", \"r\", stdin);\n\tfreopen(\"angry.out\", \"w\", stdout);\n\n\tcin >> n;\n\thaybales.resize(n);\n\tfor (int i = 0; i < n; i++) {\n\t\tcin >> haybales[i];\n\t\thaybales[i] *= 2; // double each position to eliminate decimals\n\t}\n\tsort(haybales.begin(), haybales.end());\n\n\tint l = 0, r = INT_MAX;\n\twhile (l <= r) {\n\t\tint power = (r - l) / 2 + l;\n\n\t\t// find the rightmost haybale that can still reach the left\n\t\tint pos_l = 0, pos_r = INT_MAX;\n\t\twhile (pos_l <= pos_r) {\n\t\t\tint pos = (pos_r - pos_l) / 2 + pos_l;\n\n\t\t\t// index of candidate haybale\n\t\t\tint idx =\n\t\t\t lower_bound(haybales.begin(), haybales.end(), pos) - haybales.begin();\n\n\t\t\t// can we explode all haybales on left?\n\t\t\tif (idx < n && valid(pos, idx, power, 0)) {\n\t\t\t\tpos_l = pos + 1;\n\t\t\t} else {\n\t\t\t\tpos_r = pos - 1;\n\t\t\t}\n\t\t}\n\n\t\tint idx =\n\t\t upper_bound(haybales.begin(), haybales.end(), pos_l) - haybales.begin();\n\n\t\t// can we explode all haybales on the right?\n\t\tif (valid(pos_l, idx, power, 1)) {\n\t\t\tr = power - 1;\n\t\t} else {\n\t\t\tl = power + 1;\n\t\t}\n\t}\n\tcout << fixed << setprecision(1) << (double)l / 2.0 << 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 Main {\n\tstatic int n;\n\tstatic int[] haybales;\n\n\tstatic boolean valid(int pos, int idx, int power, int dir) {\n\t\t// exploded leftmost haybale\n\t\tif (idx <= 0 && dir == 0) { return (idx < 0 || pos - power <= haybales[idx]); }\n\n\t\t// exploded rightmost haybale\n\t\tif (idx >= n - 1 && dir == 1) {\n\t\t\treturn idx >= n || pos + power >= haybales[idx];\n\t\t}\n\n\t\tif (dir == 0) { // left\n\t\t\tif (pos - power <= haybales[0]) { return true; }\n\n\t\t\t// go as left as possible\n\t\t\tint next_idx = idx;\n\t\t\twhile (next_idx >= 0 && pos - power <= haybales[next_idx]) { next_idx--; }\n\n\t\t\t// more movement is not possible\n\t\t\tif (next_idx == idx) { return false; }\n\n\t\t\treturn valid(haybales[next_idx + 1], next_idx, power - 2, dir);\n\t\t} else { // right\n\t\t\tif (pos + power >= haybales[n - 1]) { return true; }\n\n\t\t\t// go as right as possible\n\t\t\tint next_idx = idx;\n\t\t\twhile (next_idx < n && haybales[next_idx] <= pos + power) { next_idx++; }\n\n\t\t\t// more movement is not possible\n\t\t\tif (next_idx == idx) { return false; }\n\n\t\t\treturn valid(haybales[next_idx - 1], next_idx, power - 2, dir);\n\t\t}\n\t}\n\n\tpublic static void main(String[] args) throws IOException {\n\t\tBufferedReader br = new BufferedReader(new FileReader(\"angry.in\"));\n\t\tPrintWriter pw = new PrintWriter(new FileWriter(\"angry.out\"));\n\n\t\tn = Integer.parseInt(br.readLine());\n\t\thaybales = new int[n];\n\t\tfor (int i = 0; i < n; i++) {\n\t\t\t// double each position to eliminate decimals\n\t\t\thaybales[i] = Integer.parseInt(br.readLine()) * 2;\n\t\t}\n\t\tArrays.sort(haybales);\n\t\tint l = 0, r = Integer.MAX_VALUE;\n\t\twhile (l <= r) {\n\t\t\tint power = (r - l) / 2 + l;\n\n\t\t\t// find the rightmost haybale that can still reach the left\n\t\t\tint pos_l = 0, pos_r = Integer.MAX_VALUE;\n\t\t\twhile (pos_l <= pos_r) {\n\t\t\t\tint pos = (pos_r - pos_l) / 2 + pos_l;\n\n\t\t\t\t// index of candidate haybale\n\t\t\t\tint idx = Arrays.binarySearch(haybales, pos);\n\t\t\t\tif (idx < 0) { idx = -idx - 1; }\n\n\t\t\t\t// can we explode all haybales on left?\n\t\t\t\tif (idx < n && valid(pos, idx, power, 0)) {\n\t\t\t\t\tpos_l = pos + 1;\n\t\t\t\t} else {\n\t\t\t\t\tpos_r = pos - 1;\n\t\t\t\t}\n\t\t\t}\n\n\t\t\tint idx = Arrays.binarySearch(haybales, pos_l);\n\t\t\tif (idx < 0) {\n\t\t\t\tidx = -idx - 1;\n\t\t\t} else {\n\t\t\t\twhile (idx < n && haybales[idx] == pos_l) { idx++; }\n\t\t\t}\n\n\t\t\t// can we explode all haybales on the right?\n\t\t\tif (valid(pos_l, idx, power, 1)) {\n\t\t\t\tr = power - 1;\n\t\t\t} else {\n\t\t\t\tl = power + 1;\n\t\t\t}\n\t\t}\n\t\tpw.printf(\"%.1f\\n\", (double)l / 2.0);\n\t\tpw.close();\n\t\tbr.close();\n\t}\n}\n"
 })
 })
 }), _jsx(PySection, {
 children: _jsx(_components.pre, {
 children: _jsx(_components.code, {
 className: "language-py",
 children: "import sys\n\n\ndef valid(mid: int) -> bool:\n\t# L to R\n\t# i marks the current haybale we are exploding\n\t# j marks the furthest haybale we can reach\n\ti, j = 0, 0\n\n\t# maxpos finds the rightmost index that can reach the left\n\tmaxpos = hay[0] + mid\n\tr = mid % 2\n\twhile j < n and r <= mid:\n\t\tif hay[i] + r >= hay[j]:\n\t\t\tj += 1\n\t\telse:\n\t\t\tif j - i == 1:\n\t\t\t\t# consecutive haybales are a special case\n\t\t\t\t# anchor is the haybale right before it, so we cannot start a new chain\n\t\t\t\tr = (hay[j] - hay[i]) + (hay[j] - hay[i]) % 2\n\t\t\t\tif r >= mid:\n\t\t\t\t\t# update max possible position if radius is insufficient\n\t\t\t\t\tmaxpos = min(maxpos, hay[i] + mid)\n\t\t\t\t\tbreak\n\t\t\telse:\n\t\t\t\t# otherwise, we can explode haybale j-1 and start again with decreased power\n\t\t\t\tr += 2\n\t\t\t\ti = j - 1\n\t\tif r <= mid:\n\t\t\tmaxpos = max(maxpos, hay[i] + mid)\n\n\t# R to L\n\ti, j = n - 1, n - 1\n\n\t# minpos finds the leftmost index that can reach the right\n\tminpos = hay[-1] - mid\n\tr = mid % 2\n\twhile j >= 0 and r <= mid:\n\t\tif hay[i] - r <= hay[j]:\n\t\t\tj -= 1\n\t\telse:\n\t\t\tif i - j == 1:\n\t\t\t\tr = (hay[i] - hay[j]) + (hay[i] - hay[j]) % 2\n\t\t\t\tif r >= mid:\n\t\t\t\t\tminpos = min(minpos, hay[i] - mid)\n\t\t\t\t\tbreak\n\t\t\telse:\n\t\t\t\tr += 2\n\t\t\t\ti = j + 1\n\t\tif r <= mid:\n\t\t\tminpos = min(minpos, hay[i] - mid)\n\n\t# explosion possible if ranges overlap\n\treturn minpos <= maxpos\n\n\nwith open(\"angry.in\", \"r\") as f:\n\tn = int(f.readline().strip())\n\thay = [\n\t\tint(f.readline().strip()) * 2 for _ in range(n)\n\t] # double positions to avoid decimals\nhay.sort()\n\n# binary search for lowest initial power\nl, r = 0, hay[-1]\nwhile l < r:\n\tmid = (l + r) // 2\n\tif valid(mid):\n\t\tr = mid\n\telse:\n\t\tl = mid + 1\n\nprint(f\"{l / 2:.1f}\", file=open(\"angry.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

Video Solution

Solution

Join the USACO Forum!