Skip to content
Tutorials Center
My learning

Topics

Lesson 53 of 63 ยท Practice and Review

Practice: Hard Problems with Solutions

Eight harder contest problems with graded hints, then full runnable Python solutions: sliding windows, stacks, bitmask and digit DP, graph states, trees and games.

Hard problems rarely need a new algorithm. They need a known technique used in an unfamiliar disguise, often combined with a second idea. The eight problems here are chosen so that each one hides a standard tool behind a small twist: a counting trick, a monotonic stack, a state added to a graph, a contribution argument on a tree. They are harder than the intermediate problems, and you should expect to be stuck on some of them.

Being stuck is the point, but being stuck for too long teaches little. So every problem comes with graded hints. Read the statement, think for ten minutes, then reveal one hint at a time. Only after you have a plan should you read the solution and run the code. Each solution is verified against a brute force on small random inputs, because a hard problem is exactly where a subtle off-by-one hides.

flowchart TD
  S["Statement"] --> T["Think 10 min<br/>with small cases"]
  T --> H1{"Idea?"}
  H1 -- "no" --> HA["Read hint 1"]
  HA --> H2{"Idea?"}
  H2 -- "no" --> HB["Read hint 2"]
  HB --> SOL["Read the solution"]
  H1 -- "yes" --> C["Code it and test<br/>against a brute force"]
  H2 -- "yes" --> C
  SOL --> R["Close it and re-solve<br/>from a blank file tomorrow"]
  C --> R

A hint ladder: use the smallest hint that unblocks you, and always re-solve later.

Problems 1 to 3: windows, stacks and sorting

Problem 1: Exactly k distinct. Given an array and k, count the subarrays that contain exactly k different values. Length up to 200,000. Hint 1: counting "exactly k" directly is awkward; counting "at most k" is easy with a sliding window. Hint 2: "exactly k" equals "at most k" minus "at most k - 1".

Problem 2: Largest rectangle. A histogram has bars of width 1 and given heights. Find the area of the largest rectangle that fits inside it. Up to 200,000 bars. Hint 1: for a fixed bar, the best rectangle that uses it as the shortest bar extends left and right until it meets a lower bar. Hint 2: a monotonic stack that stores bars in increasing order of height finds those boundaries for all bars in one pass.

Problem 3: Inversions. Count the pairs i < j with a[i] > a[j]. Length up to 200,000, so O(n^2) is far too slow. Hint 1: merge sort already compares elements across its two halves. Hint 2: when you take an element from the right half before the remaining left elements, it forms an inversion with every one of those left elements.

Python Problems 1 to 3 with brute-force checks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Solutions. For problem 1, at_most_k_distinct moves the right end one step at a time and shrinks the left end while the window has too many values; the number of valid windows ending at right is the window length. For [1, 2, 1, 2, 3] and k = 2 the answer is 7. Both calls are O(n), so the whole solution is O(n). This is the "at most" trick from two pointers and sliding windows in practice.

For problem 2 the stack holds bars of increasing height, each remembering how far left it can extend. When a lower bar arrives, the taller bars on the stack end there, so their areas are final. Each bar is pushed and popped once: O(n). The answer for the classic histogram [2, 1, 5, 6, 2, 3] is 10 (the bars 5 and 6 with height 5). More stack patterns are in monotonic stacks, heaps and deques.

For problem 3 the merge step adds len(left) - i each time a right element wins, which is exactly the number of larger left elements still waiting. O(n log n). The reversed list of 1000 numbers has 1000 x 999 / 2 = 499,500 inversions, which the output confirms. A Fenwick tree gives the same complexity (see Fenwick and segment trees).

Problems 4 and 5: bitmask and digit DP

Problem 4: Shortest tour. There are n <= 16 cities with a symmetric distance table. Find the length of the shortest route that starts at city 0, visits every city exactly once and returns to city 0. Hint 1: trying all orders is (n-1)! routes, which is too many for n = 16. But the future of a partial route depends only on which cities are visited and where you stand now. Hint 2: use a state (set of visited cities, current city), with the set stored as a bitmask. There are 2^n x n states and n transitions each.

Problem 5: Digit sum count. Count the integers from 0 to N (with N up to 10^18) whose digits sum to exactly S. Hint 1: you cannot loop over 10^18 numbers, but you can build a number digit by digit. Hint 2: the state is (position, remaining sum, tight), where tight says that the digits chosen so far equal the prefix of N, so the next digit is capped by N's digit. Memoize it.

Python Problems 4 and 5 with brute-force checks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Solutions. The tour on four cities has length 80 (for example 0, 1, 3, 2, 0: 10 + 25 + 30 + 15). The table has 2^n x n entries and each needs a loop over n next cities, so the cost is O(2^n n^2); for n = 16 that is about 16.7 million basic steps, which is heavy for Python and a good example of a problem where you would consider a faster language or NumPy. The structure is explained in bitmask and digit DP.

For digit DP the number of states is at most (digits) x (sums up to S) x 2, which is a few thousand for 10^18, and each tries at most ten digits, so it finishes instantly. The answer for N = 100 and S = 10 is 9 (the numbers 19, 28, ..., 91). Counting from 0 is harmless here because 0 has digit sum 0, but if S = 0 your answer would include it, so subtract it when the statement starts at 1.

Problems 6 to 8: graph states, trees and games

Problem 6: Free roads. In a road network with positive travel costs you can use at most k roads for free. What is the cheapest cost from a start to a destination? Hint 1: plain Dijkstra does not know how many coupons you have left. Hint 2: make the coupon count part of the vertex: run Dijkstra on pairs (city, coupons used), with two kinds of edges, paying or using a coupon.

Problem 7: All pairs on a tree. A tree has n vertices (up to 200,000). Find the sum of distances over all unordered pairs of vertices. Hint 1: do not compute distances. Count, for each edge, how many pairs have a path through it. Hint 2: removing an edge splits the tree into two parts of sizes s and n - s, and every pair across the split uses that edge exactly once.

Problem 8: Stone game. Several piles of stones; a move removes 1, 3 or 4 stones from one pile; the player who cannot move loses. Does the first player win? Hint 1: each pile is an independent game, and independent games combine through XOR. Hint 2: compute the Grundy value of a pile as the smallest non-negative integer not among the Grundy values of the positions reachable in one move. The first player wins exactly when the XOR of all pile values is not zero.

Python Problems 6 to 8 with brute-force checks

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Solutions. In the square network the plain shortest route costs 8 (through cities 0, 2, 3), and with one coupon it drops to 4 (use the free pass on the 4-cost road). The state graph has n x (k + 1) vertices, so Dijkstra costs O(k(V + E) log(kV)). This idea of state-expanded graphs is covered in shortest paths in practice.

For the tree the total for the example is 18: the four edges separate 1 x 4, 1 x 4, 2 x 3 and 1 x 4 pairs. The code finds subtree sizes by processing vertices in reverse discovery order, so it needs no recursion and handles a path of 200,000 vertices. The brute force compares it against a BFS from every vertex.

For the game, the Grundy values for piles 0 to 10 are 0 1 0 1 2 3 2 0 1 0 1. A pile of 7 has value 0, which is a lost position for the player to move. Piles (5, 7) have values 3 and 0, so the first player wins; piles (2, 2) have values 0 and 0, so the second player wins by mirroring. The brute force searches all game states for small piles to confirm. See game theory.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. How does the solution count subarrays with exactly k distinct values?

    The sliding window easily counts subarrays with at most k distinct values. The difference between k and k - 1 is exactly k.
  2. 2. In digit DP, what does the 'tight' flag mean?

    While tight, the next digit is capped by the limit's digit. Once a smaller digit is chosen, the rest of the digits are free (up to 9).
  3. 3. Why is the sum of all pairwise distances in a tree computed by looking at edges?

    Removing an edge splits the tree into two parts, and every pair with one vertex on each side uses the edge once.
  4. 4. Why does the free-roads problem use Dijkstra over (city, coupons used) states?

    Two visits to the same city with different numbers of coupons left are different situations. Adding the count to the state makes the problem an ordinary shortest path.
  5. 5. A pile in the stone game has Grundy value 0. What does that mean for the player to move in a game with only that pile?

    A Grundy value of 0 marks a position where every move leads to a position with a nonzero value, so the player to move loses against correct play.

Summary

  • Hard problems combine a known tool with a twist: "exactly k" becomes a difference of "at most", a histogram becomes a monotonic stack, a counting problem becomes a digit DP.
  • Adding information to the state (visited set, tight flag, coupons used) turns a hard problem into a standard one.
  • On trees and in counting problems, think about the contribution of each edge or element instead of computing every answer.
  • Independent games combine with XOR of Grundy values.
  • Always verify clever solutions against a brute force on small inputs, and re-solve each problem from scratch a day later.

Next: CSES Introductory Problems Walkthrough