Contest Python: USACO Bronze › Grand Mock Contest — Contest Python: USACO Bronze Capstone

Problems: Grand Mock Contest — Contest Python: USACO Bronze Capstone

A full timed mock contest spanning the book: eight problems in five milestones. Each problem reads the whole contest input from standard input and prints the exact output. Read the input in your program with:

import sys
data = sys.stdin.read()

Write each answer as a complete program in your notebook, and run it with piped input, for example python my_solution.py < case.txt. Do not call input(). The five milestones group the problems by the technique they reward; solve them in any order.

Milestone 1 — Warmups

Problem 1: Fair Cut

Line 1: N. Line 2: N integers (they may be negative), the values of a row of prize boxes. Cut the row once between two neighbouring boxes, so that both parts keep at least one box. Output the smallest possible difference |left total - right total|.

Build one prefix-sum array, so each cut's left total is one lookup and its right total is the whole total minus the left total. In the sample, the best cut comes after the third box: 4 - 1 + 7 = 10 on the left against 3 - 2 + 5 = 6 on the right.

Constraints. 2 <= N <= 100000, -10^9 <= a_i <= 10^9. Re-adding both parts for every cut will not finish in time.

Sample Input

6
4 -1 7 3 -2 5

Sample Output

How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

Build one prefix-sum array, so each cut's left total is one lookup and its right total is the whole total minus the left total.

For parents and teachers: report a problem

Problem 2: Laser Maze

Line 1: R C r. Then R rows of the maze, made of . (empty), /, and \ (two-sided mirrors). A laser beam enters cell (r, 0) from the left edge, moving right. An empty cell lets the beam pass straight through. A / mirror turns a beam moving right to up, up to right, left to down, and down to left; a \ mirror turns right to down, down to right, left to up, and up to left. The beam always leaves the maze eventually. Output two values: how many times the beam enters a cell (a cell entered twice counts twice), and the side where it leaves: N (top), S (bottom), E (right), or W (left).

In the sample, the beam turns up, left, and then down, re-enters its starting cell (1, 0) moving down, and leaves through the bottom after 8 cell entries.

Constraints. 1 <= R, C <= 500, 0 <= r < R, and every row has exactly C characters.

Sample Input

3 3 1
/.\
../
...

Sample Output

8 S

How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.

Your code

For parents and teachers: report a problem

Milestone 2 — Search & Pointers

Problem 3: Spread the Beacons

Line 1: N K. Line 2: N distinct positions along a coast where a beacon may be built. Build exactly K beacons at K different positions so that the smallest distance between two beacons is as large as possible. Output that largest possible smallest distance.

Binary-search the distance: a distance d works when a greedy left-to-right sweep over the sorted positions, placing a beacon at the first position and then at every position at least d beyond the last beacon, places at least K beacons. In the sample, the beacons 1 7 15 keep every gap at least 6, and no choice of three positions keeps every gap at 7 or more.

Constraints. 2 <= K <= N <= 100000, 0 <= position <= 10^9. Trying every distance one at a time will not finish in time.

Sample Input

6 3
1 12 3 7 10 15

Sample Output

How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

Binary-search the distance: a distance d works when a greedy left-to-right sweep over the sorted positions, placing a beacon at the first position and then at every position at least d beyond the last beacon, places at least K beacons.

For parents and teachers: report a problem

Problem 4: Gap Pairs

Line 1: N D. Line 2: N distinct integers. Output how many pairs of these values differ by exactly D.

Sort the values and move two pointers in the same direction: for each lo, advance hi while values[hi] - values[lo] is less than D, then check for an exact match; neither pointer ever moves backward. In the sample, the pairs are 1 4, 4 7, 7 10, and 10 13, and the final value 13 completes the last pair.

Constraints. 2 <= N <= 100000, 0 <= value <= 10^9, 1 <= D <= 10^9. Checking every pair will not finish in time.

Sample Input

6 3
1 7 4 10 5 13

Sample Output

How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

Sort the values and move two pointers in the same direction
neither pointer ever moves backward.

For parents and teachers: report a problem

Milestone 3 — Graphs & Grids

Problem 5: Fastest Routes

Line 1: N M S T (nodes 1..N, M roads, source S, target T). Then M lines each u v, an undirected road. Output two values: the fewest roads on a route from S to T, and the number of different routes that use exactly that many roads, modulo 1000000007. Output -1 0 if T cannot be reached, and 0 1 when S equals T.

Run BFS from S with a deque. Record each node's distance when it is first reached and give it the route count of the node it was reached from; whenever another node one road closer to S also has a road to it, add that node's route count as well. In the sample, three different routes of 3 roads reach node 6, and the final road 5 6 adds the third one.

Constraints. 1 <= N <= 50000, 0 <= M <= 100000, 1 <= S, T <= N; no road joins a node to itself, and no road is listed twice. Listing every route will not finish in time.

Sample Input

Sample Output

3 3

How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

Run BFS from S with a deque.

For parents and teachers: report a problem

Problem 6: Enclosed Ponds

Line 1: R C. Then R rows of # (land) and . (water). A pond is a 4-connected region of water, and it is enclosed when none of its cells lies in the first or last row or in the first or last column. Output the number of enclosed ponds and their total number of cells.

Flood-fill each pond once with a recursive walk, collecting its cells so you can check whether any of them touches the edge. In the sample, the three-cell pond in the upper left is enclosed, while the pond on the right reaches the right edge and the single water cell in the bottom row touches the bottom edge.

Constraints. 1 <= R, C, R*C <= 400.

Sample Input

5 6
######
#..#.#
#.##.#
####..
#.####

Sample Output

1 3

How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

Flood-fill each pond once with a recursive walk, collecting its cells so you can check whether any of them touches the edge.

For parents and teachers: report a problem

Milestone 4 — Recursion & Backtracking

Problem 7: Seating Plan

A single line N. Count the arrangements of people 1..N into seats 1..N such that person p never sits in seat p. Output the count. (Build it by backtracking: for each seat, try every unused person that is allowed, mark them used, recurse, then unmark.)

Constraints. 1 <= N <= 9.

Sample Input

Sample Output

How this is checked: Checked by running your program on 4 test inputs (1 sample, 3 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

Build it by backtracking: for each seat, try every unused person that is allowed, mark them used, recurse, then unmark.

For parents and teachers: report a problem

Milestone 5 — Trees

Problem 8: Widest Generation

Line 1: N (nodes 1..N, node 1 is the root). Then N lines each label left right, where left/right are the child node ids (in 1..N) or -1 for none. The root is at depth 1, its children are at depth 2, and so on. The widest depth is the one holding the most nodes; if several depths tie, it is the smallest of them. Output the widest depth and the sum of the labels of the nodes at that depth.

Use a recursive traversal that passes each node's depth down to its children and adds the node to per-depth counts and label sums. In the sample, depth 3 holds three nodes with labels 1, 2, and 6, so the output is 3 9.

Constraints. 1 <= N <= 100000, 0 <= label <= 10^9, and the tree height is at most 500; the input describes one valid binary tree rooted at node 1.

Sample Input

Sample Output

3 9

How this is checked: Checked by running your program on 5 test inputs (1 sample, 4 hidden) and comparing its output word by word.

Your code

Also check yourself

The automatic check cannot see these, so tick each one when your work does it.

Use a recursive traversal that passes each node's depth down to its children and adds the node to per-depth counts and label sums.

For parents and teachers: report a problem

Make it yours

Finished early, or want a bigger challenge? Pick one:

Add a problem in the book's style and write its reference solver + a couple of crafted test cases.
Tighten a bound: re-solve Problem 3 or Problem 5 imagining N ten times larger — does your solution still finish in time? State its Big-O.
Optimize: rewrite Problem 7 to prune impossible branches earlier, and count how many fewer recursive calls it makes.

Requirements

To complete the contest:

[ ] Each of the eight programs reads the whole input from sys.stdin and prints the exact output string (no input()).
[ ] Every solver reproduces its sample output.
[ ] Each solver finishes within the time budget at the stated constraints (state each one's Big-O).
[ ] Problems 5 (BFS) and 8 (tree) use the taught idioms — a deque FIFO queue and a recursive traversal with the -1 child sentinel.

Back to Grand Mock Contest — Contest Python: USACO Bronze Capstone