Ad Hoc Problems

According to USACO Training section 1.2:

Ad hoc problems are those whose algorithms do not fall into standard categories with well-studied solutions. Each ad hoc problem is different; no specific or general techniques exist to solve them.

In this module, we'll go over some general tips that may be useful in approaching problems that appear to be ad hoc.

• Draw lots of small cases to gain a better understanding of the problem. If you're having trouble debugging, draw more cases. If you don't know how to start with a problem, draw more cases. Whenever you don't know how to further approach a problem, you're probably missing an important observation, so draw more cases and make observations about properties of the problem.
• Whenever you find an observation that seems useful, write it down! Writing down ideas lets you easily come back to them later, and makes sure you don't forget about ideas that could potentially be the solution.
• Don't get stuck on any specific idea, unless you see an entire solution.
• Try to approach the problem from a lot of different perspectives. Try to mess around with formulas or draw a visual depiction of the problem. One of the most helpful things you can do when solving ad hoc problems is to keep trying ideas until you make progress. This is something you get better at as you do more problems.

In the end, the best way to get better at ad hoc problems (or any type of problem) is to do a lot of them.

Example - Milking Order

Don't be afraid to give up on some approach if you aren't making progress!

Solution

Official Analysis (C++)

What if we tried placing cow $1$ at every possible position?

Then, we'll have some hierarchy we have to fit in and some free cows which can go anywhere. Let's just handle the hierarchy, since we can fit in the free cows at the end.

As we sweep through the hierarchy, we'll also store a pointer that indicates our current position. Greedily, we should try to place these cows as early as possible to make sure that we have room to fit in all of them. As we go through the list, we have to make sure that this pointer never outruns some previous cow in our hierarchy.

This check takes $\mathcal{O}(N + M + K)$, which brings our total time complexity to $\mathcal{O}(N(N + M + K))$.

Copy
#include <bits/stdc++.h>
using namespace std;

int n, m, k;

/**
 * @return whether it's possible to construct a
 * valid ordering with given fixed elements
 */
bool check(vector<int> order, vector<int> &hierarchy) {

Copy
import java.io.*;
import java.util.*;

public class MilkOrder {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new FileReader("milkorder.in"));
		PrintWriter pw = new PrintWriter("milkorder.out");

		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());

Copy
import sys

sys.stdin = open("milkorder.in", "r")
sys.stdout = open("milkorder.out", "w")

n, m, k = map(int, input().split())

hierarchy = [i - 1 for i in list(map(int, input().split()))]
order = [-1] * n

Problems

Of course, ad hoc problems can be quite easy, but the ones presented below are generally on the harder side.

Quiz