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",
 code: "code",
 h2: "h2",
 h3: "h3",
 li: "li",
 ol: "ol",
 p: "p",
 pre: "pre",
 strong: "strong",
 ...props.components
 }, {CPPSection, FocusProblem, HeaderLink, JavaSection, LanguageSection, MATHSPAN, Problems, PySection, Spoiler} = _components;
 if (!CPPSection) _missingMdxReference("CPPSection", true);
 if (!FocusProblem) _missingMdxReference("FocusProblem", true);
 if (!HeaderLink) _missingMdxReference("HeaderLink", true);
 if (!JavaSection) _missingMdxReference("JavaSection", true);
 if (!LanguageSection) _missingMdxReference("LanguageSection", true);
 if (!MATHSPAN) _missingMdxReference("MATHSPAN", true);
 if (!Problems) _missingMdxReference("Problems", true);
 if (!PySection) _missingMdxReference("PySection", true);
 if (!Spoiler) _missingMdxReference("Spoiler", true);
 return _jsxs(_Fragment, {
 children: [_jsx(_components.p, {
 children: "A casework problem is one that can be broken down into different cases that can each be solved for separately."
 }), "\n", _jsx(_components.p, {
 children: "These usually require drawing out a lot of cases and making observations about each."
 }), "\n", _jsx(_components.p, {
 children: "We can try to spot similarities between different cases in order to solve\nmultiple of them with the same method."
 }), "\n", _jsx(FocusProblem, {
 problem: "case-tutorial"
 }), "\n", _jsxs(_components.h2, {
 id: "solution---sleepy-cow-herding",
 children: [_jsx(_components.a, {
 "aria-hidden": "true",
 tabIndex: "-1",
 className: "anchor before",
 href: "#solution---sleepy-cow-herding",
 children: _jsx(HeaderLink, {})
 }), "Solution - Sleepy Cow Herding"]
 }), "\n", _jsxs(Spoiler, {
 title: "Solution",
 children: [_jsx(_components.p, {
 children: "Let's solve for the minimum and maximum numbers of moves independently. We refer to the cow positions as \"elements,\" and say that two elements are adjacent if there\nare no elements in between them."
 }), _jsxs(_components.h3, {
 id: "minimum",
 children: [_jsx(_components.a, {
 "aria-hidden": "true",
 tabIndex: "-1",
 className: "anchor before",
 href: "#minimum",
 children: _jsx(HeaderLink, {})
 }), "Minimum"]
 }), _jsx(_components.p, {
 children: "There are 3 cases for the minimum amount of moves:"
 }), _jsxs(_components.ol, {
 children: ["\n", _jsx(_components.li, {
 children: "The 3 elements are already consecutive."
 }), "\n", _jsx(_components.li, {
 children: "There are two adjacent elements with exactly one empty position in between them."
 }), "\n", _jsx(_components.li, {
 children: "Any other case that did not satisfy the two above."
 }), "\n"]
 }), _jsxs(_components.p, {
 children: ["For the first case, the answer would be ", _jsx(MATHSPAN, {
 className: "language-math math-inline",
 latex: "0",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mn>0</mn></mrow><annotation encoding=\"application/x-tex\">0</annotation></semantics></math>0"
 }), " because the elements are already consecutive."]
 }), _jsxs(_components.p, {
 children: ["For the second case, the answer would be ", _jsx(MATHSPAN, {
 className: "language-math math-inline",
 latex: "1",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mn>1</mn></mrow><annotation encoding=\"application/x-tex\">1</annotation></semantics></math>1"
 }), " because the only move required is the one that would insert the isolated element into the gap between the two other elements."]
 }), _jsxs(_components.p, {
 children: ["The third case would output ", _jsx(MATHSPAN, {
 className: "language-math math-inline",
 latex: "2",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mn>2</mn></mrow><annotation encoding=\"application/x-tex\">2</annotation></semantics></math>2"
 }), " because for any other test case, the optimal solution would be to either take the minimum element to ", _jsx(MATHSPAN, {
 className: "language-math math-inline",
 latex: "\\max-2",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mi>max</mi><mo>⁡</mo><mo>−</mo><mn>2</mn></mrow><annotation encoding=\"application/x-tex\">\\max-2</annotation></semantics></math>max−2"
 }), " or the maximum element to ", _jsx(MATHSPAN, {
 className: "language-math math-inline",
 latex: "\\min+2",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mi>min</mi><mo>⁡</mo><mo>+</mo><mn>2</mn></mrow><annotation encoding=\"application/x-tex\">\\min+2</annotation></semantics></math>min+2"
 }), ", and then we have reduced to the second case."]
 }), _jsxs(_components.h3, {
 id: "maximum",
 children: [_jsx(_components.a, {
 "aria-hidden": "true",
 tabIndex: "-1",
 className: "anchor before",
 href: "#maximum",
 children: _jsx(HeaderLink, {})
 }), "Maximum"]
 }), _jsx(_components.p, {
 children: "The maximum will always be finite because every operation strictly decreases\nthe distance between the endpoints (let's refer to this as the \"span\") by at least one.\nThe best approach to maximize the amount of moves is to place each element as close to an endpoint as possible (while not remaining an endpoint). After one move,\nthe span will equal the largest distance between two adjacent elements, and every\nsubsequent move after that will decrease the span by one until it reaches two.\nTherefore, the maximum is the largest distance between two adjacent elements minus 1."
 }), _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}(1)",
 children: "<math xmlns=\"http://www.w3.org/1998/Math/MathML\"><semantics><mrow><mi mathvariant=\"script\">O</mi><mo stretchy=\"false\">(</mo><mn>1</mn><mo stretchy=\"false\">)</mo></mrow><annotation encoding=\"application/x-tex\">\\mathcal{O}(1)</annotation></semantics></math>O(1)"
 })]
 }), _jsxs(LanguageSection, {
 children: [_jsx(CPPSection, {
 children: _jsx(_components.pre, {
 children: _jsx(_components.code, {
 className: "language-cpp",
 children: "#include <algorithm>\n#include <iostream>\n#include <vector>\n\nusing namespace std;\n\nint main() {\n\tfreopen(\"herding.in\", \"r\", stdin);\n\tfreopen(\"herding.out\", \"w\", stdout);\n\n\tvector<int> a(3);\n\tfor (int &b : a) { cin >> b; }\n\tsort(a.begin(), a.end());\n\n\t/*\n\t * The minimum number of moves can only be 0, 1, or 2.\n\t * 0 is if they're already consecutive,\n\t * 1 is if there's a difference of 2 between any 2 numbers,\n\t * and 2 is for all other cases.\n\t */\n\tif (a[0] == a[2] - 2) {\n\t\tcout << 0 << endl;\n\t} else if ((a[1] == a[2] - 2) || (a[0] == a[1] - 2)) {\n\t\tcout << 1 << endl;\n\t} else {\n\t\tcout << 2 << endl;\n\t}\n\n\t// max is equal to largest difference between end and middle, minus one.\n\tcout << max(a[2] - a[1], a[1] - a[0]) - 1;\n}\n"
 })
 })
 }), _jsx(JavaSection, {
 children: _jsx(_components.pre, {
 children: _jsx(_components.code, {
 className: "language-java",
 children: "import java.io.*;\nimport java.util.*;\nclass Main {\n\tpublic static void main(String[] args) throws IOException {\n\t\tScanner sc = new Scanner(new File(\"herding.in\"));\n\t\tPrintWriter pw = new PrintWriter(new File(\"herding.out\"));\n\t\tint[] cows = new int[3];\n\t\tcows[0] = sc.nextInt();\n\t\tcows[1] = sc.nextInt();\n\t\tcows[2] = sc.nextInt();\n\t\tArrays.sort(cows);\n\n\t\t/*\n\t\t * The minimum number of moves can only be 0, 1, or 2.\n\t\t * 0 is if they're already consecutive,\n\t\t * 1 is if there's a difference of 2 between any 2 numbers,\n\t\t * and 2 is for all other cases.\n\t\t */\n\t\tif (cows[2] == cows[0] + 2) {\n\t\t\tpw.println(0);\n\t\t} else if (cows[1] == cows[0] + 2 || cows[2] == cows[1] + 2) {\n\t\t\tpw.println(1);\n\t\t} else {\n\t\t\tpw.println(2);\n\t\t}\n\n\t\t// max is equal to largest difference between end and middle, minus one.\n\t\tpw.println(Math.max(cows[1] - cows[0], cows[2] - cows[1]) - 1);\n\t\tpw.close();\n\t}\n}\n"
 })
 })
 }), _jsx(PySection, {
 children: _jsx(_components.pre, {
 children: _jsx(_components.code, {
 className: "language-py",
 children: "with open(\"herding.in\", \"r\") as file_in:\n\ta, b, c = map(int, file_in.readline().split())\n\n\"\"\"\nThe minimum number of moves can only be 0, 1, or 2.\n0 is if they're already consecutive,\n1 is if there's a difference of 2 between any 2 numbers,\nand 2 is for all other cases.\n\"\"\"\nif c == a + 2:\n\tminimum = 0\nelif b == a + 2 or c == b + 2:\n\tminimum = 1\nelse:\n\tminimum = 2\n\n# max is equal to largest difference between end and middle, minus one.\nmaximum = max(b - a, c - b) - 1\n\nprint(f\"{minimum}\\n{maximum}\", file=open(\"herding.out\", \"w\"))\n"
 })
 })
 })]
 })]
 }), "\n", _jsxs(_components.h2, {
 id: "problems",
 children: [_jsx(_components.a, {
 "aria-hidden": "true",
 tabIndex: "-1",
 className: "anchor before",
 href: "#problems",
 children: _jsx(HeaderLink, {})
 }), "Problems"]
 }), "\n", _jsx(Problems, {
 problems: "casework"
 })]
 });
}
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.");
}

Source	Problem Name	Difficulty	Tags
CF	Three Logos	Easy	Show Tags Casework
Bronze	Fence Painting	Medium	Show Tags Casework
Bronze	Social Distancing I	Medium	Show Tags Casework
Bronze	Hoof Paper Scissors Minus One	Medium	Show Tags Casework
Bronze	Leaders	Hard	Show Tags Casework
Silver	Spaced Out	Very Hard	Show Tags Casework

Table of Contents

Table of Contents

Solution - Sleepy Cow Herding

Problems

Module Progress: