Ad hoc math and geometry optimisation casework

Some optimisation problems do not fit standard algorithms. Instead, you reduce the problem to a small set of candidate solutions and check each one. This is casework: explicitly handle each possible case and find the best one.

The key insight is recognising when a solution has structure that limits the search space. For example, if you are placing objects on a line, the optimal placement might always occur at a boundary or at the position of another object. If so, you only check those O(N) positions instead of all O(N^2) pairs.

Reducing to a formula

Many geometry problems ask: given some constraints, what is the maximum or minimum of a quantity? Often the quantity is a simple function of a few parameters (side lengths, distances from boundaries, a budget K).

Once you identify those parameters, you can express the answer as a formula. Then optimisation becomes algebraic: find the parameters that maximise the formula within the constraints.

For example, if you are placing a rectangular object in a grid and want to maximise the sum of values in the rectangle, the answer might depend only on the rectangle's size and position. If the rectangle's size is fixed, you only need to try O(N^2) positions.

1import sys2
3
4def main() -> None:5    input_data = sys.stdin.read().split()6    n = int(input_data[0])7    k = int(input_data[1])8    grid = []9    idx = 210    for i in range(n):11        row = [int(input_data[idx + j]) for j in range(n)]12        grid.append(row)13        idx += n14
15    # Build 2D prefix sum16    prefix = [[0] * (n + 1) for _ in range(n + 1)]17    for i in range(1, n + 1):18        for j in range(1, n + 1):19            prefix[i][j] = grid[i - 1][j - 1] + prefix[i - 1][j] + prefix[i][j - 1] - prefix[i - 1][j - 1]20
21    # Find max sum of k by k rectangle. Seed with the first candidate, not 0,22    # so a grid of entirely negative values still gives the right answer.23    max_sum = None24    for i in range(k, n + 1):25        for j in range(k, n + 1):26            rect_sum = prefix[i][j] - prefix[i - k][j] - prefix[i][j - k] + prefix[i - k][j - k]27            if max_sum is None or rect_sum > max_sum:28                max_sum = rect_sum29
30    print(max_sum)31
32
33if __name__ == "__main__":34    main()

3 2
1 2 3
4 5 6
7 8 9

28

The program iterates over all possible top-left corners of the rectangle. For each corner, it computes the sum of the K by K region using 2D prefix sums, which takes O(1) time after O(N^2) preprocessing.

The casework is implicit here: every possible position is a case, and you compute the answer for each. If K is fixed and N is 100, you check at most 100 by 100 positions, which is 10,000 constant-time lookups. This is fast enough for most time limits.

A worked example: circular placement and angles

Imagine placing K evenly-spaced gates around a circular track. The track has N stations, and you want to maximise the minimum distance from any station to the nearest gate. The answer depends on the gate spacing (determined by K) and the starting position of the first gate.

Casework: the optimal first gate position likely coincides with a station or lies at a specific angle. If you assume the optimal position is at some station, you check N starting positions. For each starting position, the gates divide the track into K arcs. The minimum arc length is the distance you want to maximise. This reduces a continuous optimisation to checking N discrete positions.

Formally, if gate spacing is (360 / K) degrees, and the first gate is at station s, then the gates are at angles s, s + 360/K, s + 2*360/K, etc. The minimum gap between consecutive gates determines your answer. By checking all N starting positions and computing gaps, you find the optimal arrangement in O(N K) time.

Explicit casework by boundary

When the solution has structure, you can explicitly list the cases. For instance, the optimal rectangle might always have its top or left edge aligned with a row or column of interest. Then you iterate only over those edges rather than all O(N^2) possible positions.

Similarly, if you are choosing a parameter K between 0 and N, and the answer is a quadratic in K, you can check K = 0, K = N, and K = the vertex of the parabola (if it is an integer in range). The vertex of a quadratic a*K^2 + b*K + c is at K = -b / (2*a). This reduces the search space from O(N) to O(1).

You can also derive invariants from the problem constraints. For instance, if the problem states that the optimal solution lies on a boundary, you only check boundary positions. If it states that the solution is symmetric, you only check half the space.

A common pattern in ad hoc problems is that the optimal solution occurs at an extreme: the smallest or largest value of a parameter, or at a critical point like a vertex or an intersection. By identifying these critical points, you reduce a continuous or large discrete space to a small set of candidates.

Finding the closed form

The first step in solving an ad hoc problem is to identify the closed form. Do not immediately jump to implementation. Instead, ask: what are the independent parameters? How does the answer depend on them?

Say you are choosing where to plant a single marker along a line of N posts, and you can move up to K posts to make room for it. The answer might depend on only two numbers: the marker's position (an integer from 0 to N) and how much of the budget K you spend near it. Once you express the answer as a function of those two parameters, you can search over them efficiently instead of simulating every possible arrangement.

The key skill is problem abstraction. Read the statement carefully to identify what varies and what is fixed. Then write the answer as a formula or a function in those varying parameters. Once you have a formula, optimisation becomes calculus or discrete enumeration rather than DP or graph search.

Verification and partial solutions

Ad hoc problems often have no general algorithm. The safest approach is to implement a brute-force solution for small N, then an optimised solution for large N. Verify on small inputs that both give the same answer. This builds confidence that your optimised solution is correct.

If the full problem times out or you run out of time before finding the optimal solution, submit the partial solution for a smaller subtask and move on. Ad hoc problems sometimes have no known polynomial solution, so recognising when to stop is important. A half-working solution is better than no solution.

Common pitfalls

Many contestants jump straight into implementation without deriving the closed form. This leads to inefficient code that searches a huge space unnecessarily. Instead, spend time upfront deriving the formula and understanding the structure.

Another pitfall is numerical precision. When dealing with geometry or optimisation, floating-point errors can accumulate. Whenever possible, work with integers or use high-precision arithmetic. If you must use floats, add small epsilon values when comparing for equality.

Finally, be wary of assuming the problem has a simple solution. Some ad hoc problems are genuinely hard, and there may be no efficient algorithm at all. If you get stuck, try small examples, verify against brute force, and move on if the time cost is too high.