Skip to Content
CTRL K

Milking Order

Pista

Pista 1

Intentemos colocar a la vaca 11 en una posición específica.

¿Cómo podríamos comprobar si terminaremos con un orden válido?

Solución

Análisis oficial (C++) 

Spoiler

¿Y si intentamos colocar a la vaca 11 en cada posición posible?

Entonces tendremos una jerarquía que hay que encajar y algunas vacas libres que pueden ir a cualquier lado. Solo nos ocupamos de la jerarquía, ya que las vacas libres las podemos encajar al final.

Al barrer la jerarquía, también guardamos un puntero que indica nuestra posición actual. De forma voraz (greedy), deberíamos intentar colocar estas vacas lo más temprano posible para asegurarnos de tener lugar para todas. A medida que recorremos la lista, hay que asegurarse de que este puntero nunca se adelante a alguna vaca anterior de nuestra jerarquía.

Esta comprobación toma O(N)\mathcal{O}(N) de tiempo, lo que lleva la complejidad temporal total a O(N2)\mathcal{O}(N^2).

#include <bits/stdc++.h>
using namespace std;
 
int n, m, k;
 
 
/**
 * @return si es posible construir un
 * orden válido con los elementos fijos dados
 */
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) {
			// sabemos que la siguiente vaca tiene que estar delante de ella
 
			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++; }
 
			// nos quedamos sin lugares
			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) {  // ya está fija, no podemos hacer nada
			cout << pos + 1 << endl;
			return 0;
		}
	}
 
	for (int i = 0; i < n; i++) {
		// si ya está fija, saltamos
		if (order[i] == -1) {
			// intentamos colocar a la vaca 1 en la posición 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;
 
			// ya está fija, no podemos hacer nada
			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) {
				// intentamos colocar a la vaca 1 en la posición i
				order[i] = 0;
				if (check(order, hierarchy)) {
					pw.println(i + 1);
					break;
				}
				order[i] = -1;
			}
		}
		pw.close();
	}
 
	/**
	 * @return si es posible construir un
	 * orden válido con los elementos fijos dados
	 */
	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) {
				// sabemos que la siguiente vaca tiene que estar delante de ella
				if (i > cowToPos[hierarchy[hIdx]]) { return false; }
				i = cowToPos[hierarchy[hIdx]];
				hIdx++;
			} else {
				while (i < order.length && order[i] != -1) { i++; }
				// nos quedamos sin lugares
				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:  # ya está fija, no podemos hacer nada
		print(pos)
		exit()
 
 
def check():
	"""
	:return: si es posible construir un
	orden válido con los elementos fijos dados
	"""
	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:
		# sabemos que la siguiente vaca tiene que estar delante de ella
		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
 
			# nos quedamos sin lugares
			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):
	# si ya está fija, saltamos
	if order[i] == -1:
		# intentamos colocar a la vaca 1 en la posición i
		order[i] = 0
 
		if check():
			print(i + 1)
			break
 
		order[i] = -1

Extra

Resolver el problema en tiempo O(N)O(N).

Fundamentos