Contest Python: USACO Bronze › Unit 14 — Two Pointers & Sliding Window

Exercises: Unit 14 — Two Pointers & Sliding Window

Each problem is a program that reads the whole input from stdin and prints the exact output (real contest style — no solve() wrapper): import sys; data = sys.stdin.read(), parse it, then print. Converging pointers need a sorted list; sliding windows need non-negative values. Write each program in a .py file and run it with piped input, e.g. python my_solution.py < case.txt.

Exercise 1: Exact Budget Pair

The first line contains N T, and the second line contains N integers already sorted from smallest to largest. Print YES if two values at different indices sum to target T, or NO otherwise. Use lo and hi at opposite ends and move one pointer inward after each comparison. In the sample, the pair 4 8 is found only at the last possible inward comparison; the decisive value 8 is the last value below the larger distractors.

Constraints. 2 <= N <= 200000. -1000000000 <= value, T <= 1000000000. The values are sorted in nondecreasing order. Use a converging two-pointer scan in O(N) time.

Sample Input

6 12
1 2 4 8 16 32

Sample Output

YES

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.

Use lo and hi at opposite ends and move one pointer inward after each comparison.
Use a converging two-pointer scan in O(N) time.

For parents and teachers: report a problem

Exercise 2: Pairs Below the Alarm

The first line contains N T, and the second line contains N integers sorted from smallest to largest. Print the number of index pairs (i, j) with i < j and values[i] + values[j] < T. Use converging pointers. When the current sum is below T, every index from lo + 1 through hi forms a valid pair with lo, so count those pairs at once before moving lo. The final input value 10 is a distractor that forces hi to move before any block can be counted.

Constraints. 2 <= N <= 200000. -1000000000 <= value, T <= 1000000000. The values are sorted in nondecreasing order. Use a converging two-pointer scan in O(N) time; checking every pair is too slow.

Sample Input

5 8
1 2 3 4 10

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.

Use converging pointers.
When the current sum is below T, every index from lo + 1 through hi forms a valid pair with lo, so count those pairs at once before moving lo.
Use a converging two-pointer scan in O(N) time

For parents and teachers: report a problem

Exercise 3: Closest Combined Score

The first line contains N T, and the second line contains N integers sorted from smallest to largest. Choose two values at different indices and print the smallest possible absolute difference between their sum and T. At each lo and hi position, update the best distance, then move lo right if the sum is below T; otherwise move hi left. The final input value 30 first pulls the sum too high and makes the inward comparisons necessary.

Constraints. 2 <= N <= 200000. -1000000000 <= value, T <= 1000000000. The values are sorted in nondecreasing order. Use a converging two-pointer scan in O(N) time.

Sample Input

6 20
1 4 7 12 18 30

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.

At each lo and hi position, update the best distance, then move lo right if the sum is below T; otherwise move hi left.
Use a converging two-pointer scan in O(N) time.

For parents and teachers: report a problem

Exercise 4: Teammates by Finish Time

The first line contains N T. Each of the next N lines contains a runner's distinct bib number followed by that runner's distinct finish_time. Exactly one pair of runners has finish times summing to T. Store each runner as a pair, define a named function finish_time(record) whose result is the runner's finish time, and use sorted(records, key=finish_time) before a converging two-pointer scan. Print the two bib numbers in increasing numeric order, separated by one space. In the sample, the decisive final record has time 30, so sorting by bib number or trusting input order moves the wrong endpoints.

Constraints. 2 <= N <= 200000. 1 <= bib <= 1000000000; bib numbers are distinct. 0 <= finish_time <= 1000000000; finish times are distinct. 0 <= T <= 2000000000, and exactly one valid pair exists. Sorting may take O(N log N); the converging scan must take O(N).

Sample Input

Sample Output

104 105

How this is checked: Checked by running your program on 3 test inputs (1 sample, 2 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.

Store each runner as a pair, define a named function finish_time(record) whose result is the runner's finish time, and use sorted(records, key=finish_time) before a converging two-pointer scan.
the converging scan must take O(N).

For parents and teachers: report a problem

Exercise 5: Longest Affordable Streak

The first line contains N K, and the second line contains N non-negative costs. Print the greatest length of a non-empty contiguous window whose sum is at most K; print 0 if no non-empty window is valid. Grow with right, add each new cost to a running sum, and repeatedly shrink from left while the sum is too large. In the sample, keeping the first values and only growing gives the wrong answer. The window must shrink, and the unique longest window is the three final 1 values at the right boundary.

Constraints. 1 <= N <= 200000 and 0 <= K <= 1000000000000000000. 0 <= value <= 1000000000 for every cost. Use a sliding window with an incrementally updated running sum in O(N) time.

Sample Input

5 3
4 3 1 1 1

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.

Grow with right, add each new cost to a running sum, and repeatedly shrink from left while the sum is too large.
Use a sliding window with an incrementally updated running sum in O(N) time.

For parents and teachers: report a problem

Exercise 6: Shortest Training Burst

The first line contains N K, and the second line contains N non-negative training-point values. Print the smallest length of a non-empty contiguous window whose sum is at least K; print 0 if no such window exists. Grow with right. Whenever the running sum reaches K, record the length and keep shrinking from left while the window remains valid. In the sample, no window is valid until the decisive final value 7; shrinking then reveals the shortest window of length 3 at the right boundary.

Constraints. 1 <= N <= 200000 and 1 <= K <= 1000000000000000000. 0 <= value <= 1000000000 for every training-point value. Use a sliding window with an incrementally updated running sum in O(N) time.

Sample Input

5 9
5 1 1 1 7

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.

Whenever the running sum reaches K, record the length and keep shrinking from left while the window remains valid.
Use a sliding window with an incrementally updated running sum in O(N) time.

For parents and teachers: report a problem

Exercise 7: Badge Variety Limit

The first line contains N K, and the second line contains N integer badge types. Print the greatest length of a contiguous window containing at most K distinct badge types. Keep a dictionary of counts, update one count when right grows, and decrease one count when left shrinks. Track the number of types whose count is positive; zero counts may stay in the dictionary. In the sample, the window must shrink after type 3 arrives, and the unique longest valid window ends at the decisive final badge.

Constraints. 1 <= N <= 200000 and 1 <= K <= N. 1 <= badge type <= 1000000000. Use a sliding window with incrementally updated counts in O(N) time.

Sample Input

7 2
1 2 1 3 4 3 3

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.

Keep a dictionary of counts, update one count when right grows, and decrease one count when left shrinks.
Use a sliding window with incrementally updated counts in O(N) time.

For parents and teachers: report a problem

Exercise 8: Count Affordable Windows

Challenge

The first line contains N K, and the second line contains N non-negative costs. Print the number of non-empty contiguous windows whose sum is at most K. After growing right and shrinking until the current window is valid, every window ending at right and starting from left through right is valid, so add right - left + 1 to the answer. In the sample, K is zero and the decisive final positive value also forces a shrink to an empty window, so the boundary answer is 0.

Constraints. 1 <= N <= 200000 and 0 <= K <= 1000000000000000000. 0 <= value <= 1000000000 for every cost. Use a sliding window with an incrementally updated running sum in O(N) time.

Sample Input

5 0
3 1 4 1 5

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.

add right - left + 1 to the answer
Use a sliding window with an incrementally updated running sum in O(N) time.

For parents and teachers: report a problem

Exercise 9: Minimum Rescue Boats

Challenge

The first line contains N L, and the second line contains N student weights. Each boat holds at most two students and at most total weight L. Print the minimum number of boats needed. Sort the weights, place lo at the lightest remaining student and hi at the heaviest, and make one converging-pointer decision for each boat: pair them when their total fits, or send the heaviest alone when it does not. The decisive final weight 7 changes which middle students can share.

Constraints. 1 <= N <= 200000 and 1 <= L <= 1000000000. 1 <= weight <= L. Sorting may take O(N log N); the converging scan must take O(N).

Sample Input

6 10
3 5 3 4 8 7

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 weights, place lo at the lightest remaining student and hi at the heaviest, and make one converging-pointer decision for each boat
the converging scan must take O(N).

For parents and teachers: report a problem

Back to Unit 14 — Two Pointers & Sliding Window