Skip to content

Latest commit

 

History

History
497 lines (397 loc) · 13.3 KB

Ad_Hoc.mdx

File metadata and controls

497 lines (397 loc) · 13.3 KB
id title author contributors description frequency
ad-hoc
Ad Hoc Problems
Michael Cao, Aarav Sharma
Ryan Chou
Problems that do not fall into standard categories with well-studied solutions.
4

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!

Let's try placing cow $1$ at a specific position.

How might we go about checking to see if we'll end up with a valid ordering?

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))$.

#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) {
	vector<int> cow_to_pos(n, -1);

	for (int i = 0; i < n; i++) {
		if (order[i] != -1) { cow_to_pos[order[i]] = i; }
	}

	int h_idx = 0;
	for (int i = 0; i < n && h_idx < m; i++) {
		if (cow_to_pos[hierarchy[h_idx]] != -1) {
			// we know the next cow has to be in front of it

			if (i > cow_to_pos[hierarchy[h_idx]]) { return false; }

			i = cow_to_pos[hierarchy[h_idx]];
			h_idx++;
		} else {
			while (i < n && order[i] != -1) { i++; }

			// run out of places
			if (i == n) { return false; }

			order[i] = hierarchy[h_idx];
			cow_to_pos[hierarchy[h_idx]] = i;
			h_idx++;
		}
	}

	return true;
}

int main() {
	freopen("milkorder.in", "r", stdin);
	freopen("milkorder.out", "w", stdout);
	cin >> n >> m >> k;

	vector<int> hierarchy(m);
	for (int i = 0; i < m; i++) {
		cin >> hierarchy[i];
		hierarchy[i]--;
	}

	vector<int> order(n, -1);

	for (int i = 0; i < k; i++) {
		int cow, pos;
		cin >> cow >> pos;

		order[--pos] = --cow;

		if (cow == 0) {  // already fixed, nothing we can do
			cout << pos + 1 << endl;
			return 0;
		}
	}

	for (int i = 0; i < n; i++) {
		// if already fixed, skip
		if (order[i] == -1) {
			// try placing cow 1 @ position i
			order[i] = 0;
			if (check(order, hierarchy)) {
				cout << i + 1 << endl;
				break;
			}
			order[i] = -1;
		}
	}
}
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());
		int m = Integer.parseInt(st.nextToken());
		int k = Integer.parseInt(st.nextToken());

		int[] hierarchy = new int[m];
		st = new StringTokenizer(br.readLine());
		for (int i = 0; i < m; i++) {
			hierarchy[i] = Integer.parseInt(st.nextToken()) - 1;
		}

		int[] order = new int[n];
		Arrays.fill(order, -1);
		for (int i = 0; i < k; i++) {
			st = new StringTokenizer(br.readLine());
			int cow = Integer.parseInt(st.nextToken()) - 1;
			int pos = Integer.parseInt(st.nextToken()) - 1;
			order[pos] = cow;

			// already fixed, nothing we can do
			if (cow == 0) {
				pw.println(pos + 1);
				pw.close();
				System.exit(0);
			}
		}
		br.close();

		for (int i = 0; i < n; i++) {
			if (order[i] == -1) {
				// try placing cow 1 @ position i
				order[i] = 0;
				if (check(order, hierarchy)) {
					pw.println(i + 1);
					break;
				}
				order[i] = -1;
			}
		}
		pw.close();
	}

	/**
	 * @return whether it's possible to construct a
	 * valid ordering with given fixed elements
	 */
	static boolean check(int[] order, int[] hierarchy) {
		order = order.clone();

		int[] cowToPos = new int[order.length];
		Arrays.fill(cowToPos, -1);

		for (int i = 0; i < order.length; i++) {
			if (order[i] != -1) { cowToPos[order[i]] = i; }
		}

		int hIdx = 0;
		for (int i = 0; i < order.length && hIdx < hierarchy.length; i++) {
			if (cowToPos[hierarchy[hIdx]] != -1) {
				// we know the next cow has to be in front of it
				if (i > cowToPos[hierarchy[hIdx]]) { return false; }
				i = cowToPos[hierarchy[hIdx]];
				hIdx++;
			} else {
				while (i < order.length && order[i] != -1) { i++; }
				// run out of places
				if (i == order.length) { return false; }
				order[i] = hierarchy[hIdx];
				cowToPos[hierarchy[hIdx]] = i;
				hIdx++;
			}
		}

		return true;
	}
}
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

for i in range(k):
	cow, pos = map(int, input().split())

	order[pos - 1] = cow - 1

	if cow == 1:  # already fixed, nothing we can do
		print(pos)
		exit()


def check():
	"""
	:return: whether it's possible to construct a
	valid ordering with given fixed elements
	"""
	new_order = order.copy()

	cow_to_pos = [-1] * n
	for i in range(n):
		if order[i] != -1:
			cow_to_pos[order[i]] = i

	h_idx = 0
	i = 0
	while i < n and h_idx < m:
		# we know the next cow has to be in front of it
		if cow_to_pos[hierarchy[h_idx]] != -1:
			if i > cow_to_pos[hierarchy[h_idx]]:
				return False

			i = cow_to_pos[hierarchy[h_idx]]
			h_idx += 1
		else:
			while i < n and new_order[i] != -1:
				i += 1

			# run out of places
			if i == n:
				return False

			new_order[i] = hierarchy[h_idx]
			cow_to_pos[hierarchy[h_idx]] = i
			h_idx += 1

		i += 1

	return True


for i in range(n):
	# if already fixed, skip
	if order[i] == -1:
		# try placing cow 1 @ position i
		order[i] = 0

		if check():
			print(i + 1)
			break

		order[i] = -1

Casework

When you draw a lot of cases and notice that certain cases fit similar trends in their solutions, chances are that the problem requires casework. A casework problem is a type of ad hoc problem that needs to be broken down into different cases that each need to be accounted for.

Casework problems also require drawing out a lot of cases and making observations about these cases. Try to spot similarities and differences between cases and their solutions.

Example - Sleepy Cow Herding

The solution for the minimum involves casework, while the maximum does not necessarily. There are 3 cases for the minimum, each having their own $\mathcal{O}(1)$ solution. Can you find out what those solutions are? There are 3 cases for the minimum amount of moves: - The 3 positions are already consecutive. - Two elements are already in-position consecutively (including gaps), but the other is not. - Any other case that did not satisfy the two above. For the first case, the answer would be $0$ because the elements are already consecutive.

For the second case, the answer would be $1$ because the only swap required is the one that would insert the isolated element into the gap between the two other elements.

The third case would output $2$ because for any other test case, the optimal solution would be to take the minimum element to $max-2$, and then the new minimum to fit right in between the gap.

The maximum will always be finite because these operations group the cows closer together over time, as mentioned in the problem statement. The best approach to maximize the amount of moves is to place each element as close to a gap as possible (while not remaining an endpoint). Therefore, the maximum is just the largest gap between two adjacent elements minus 1. This can be observed by drawing a lot of cases.

This code was borrowed from here. 

#include <algorithm>
#include <iostream>
#include <vector>

using namespace std;

int main() {
	freopen("herding.in", "r", stdin);
	freopen("herding.out", "w", stdout);

	// all cow locations
	vector<int> a;
	for (int i = 0; i < 3; i++) {
		int b;
		cin >> b;
		a.push_back(b);
	}
	sort(a.begin(), a.end());

	/*
	 * The minimum number of moves can only be 0, 1, or 2.
	 * 0 is if they're already consecutive,
	 * 1 is if there's a difference of 2 between any 2 numbers,
	 * and 2 is for all other cases.
	 */
	if (a[0] == a[2] - 2) {
		cout << 0 << endl;
	} else if ((a[1] == a[2] - 2) || (a[0] == a[1] - 2)) {
		cout << 1 << endl;
	} else {
		cout << 2 << endl;
	}
	// max is equal to largest difference between end and middle, minus one.
	cout << max(a[2] - a[1], a[1] - a[0]) - 1;
}
import java.io.*;
import java.util.*;
class Main {
	public static void main(String[] args) throws IOException {
		Scanner sc = new Scanner(new File("herding.in"));
		PrintWriter pw = new PrintWriter(new File("herding.out"));
		int[] cows = new int[3];
		cows[0] = sc.nextInt();
		cows[1] = sc.nextInt();
		cows[2] = sc.nextInt();
		Arrays.sort(cows);

		// Printing the minimum number of moves
		if (cows[2] == cows[0] + 2) {
			pw.println(0);
		} else if (cows[1] == cows[0] + 2 || cows[2] == cows[1] + 2) {
			pw.println(1);
		} else {
			pw.println(2);
		}

		// Max number of moves
		pw.println(Math.max(cows[1] - cows[0], cows[2] - cows[1]) - 1);
		pw.close();
	}
}
with open("herding.in", "r") as file_in:
	a, b, c = map(int, file_in.readline().split())

	# Best scenario: the three elements are already in order.
	if c == a + 2:
		minimum = 0
		"""
        If there is a difference by 2, it can be solved in one move.
        3 5 9 -> 5 7 9
        """
	elif b == a + 2 or c == b + 2:
		minimum = 1
		"""
        It can always be solved in two moves by moving a -> c - 2 and b -> c - 1.
        If there is less than one integer between the two elements, it'll be taken care
        of in the if statement above.
        """
	else:
		minimum = 2
		"""
        The worst case is incrementing by 1 in the largest gap.
        3 5 9 -> 5 6 9 -> 6 7 9 -> 7 8 9
        """

maximum = max(b - a, c - b) - 1
with open("herding.out", "w") as file_out:
	file_out.write(f"{minimum}\n{maximum}\n")

Ad Hoc Problems

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

Casework Problems

Quiz

What is most useful when solving ad hoc problems? Being able to quickly recall complex algorithms and data structures. Incorrect. Ad hoc solutions may use specific algorithms and data structures, but a majority of the solution relies on observations and understanding the problem. Exploring lots of cases and making observations. Correct. Trying small cases allows you to better understand the problem and helps you make more observations. Certain observations may be a crucial part of the solution. Relying on previous knowledge on well-studied topics. Incorrect. Ad hoc problems have solutions that are not well-studied and do not fall into any standard categories.