Closest Cow Wins

Solución en video

Por David Zhou

Nota: la solución en video puede no ser la misma que las demás soluciones. Código en C++, Python y Java.

Solución

Explicación

Podemos tratar cada intervalo entre las vacas de Nhoj como un problema independiente. Después de calcular la respuesta de cada intervalo, podemos elegir las $N$ colocaciones de vacas más óptimas para nuestra respuesta.

Hay dos tipos de intervalos que debemos considerar:

Intervalos más a la izquierda/derecha

Podemos usar una sola vaca para cortar las vacas de Nhoj en cualquiera de los extremos. Estas vacas obtienen toda la sabrosura a la izquierda de la vaca más a la izquierda de Nhoj y a la derecha de la vaca más a la derecha de Nhoj.

Intervalos del medio

Tenemos una respuesta de una vaca y una de dos vacas para cada intervalo del medio.

Para la respuesta de una vaca, vemos que, independientemente de dónde se coloque la vaca, cubre el mismo rango en el que gana a las vacas de Nhoj. Así, podemos usar una ventana deslizante para calcular la ganancia máxima de una sola vaca.

Para la respuesta de dos vacas, podemos colocar vacas justo antes de ambas vacas de Nhoj, obteniendo así toda la sabrosura del intervalo. Luego calculamos la ganancia de añadir la segunda vaca como la sabrosura de dos vacas menos la de una vaca.

La respuesta de una vaca muestra la selección más óptima de sabrosura en el intervalo. La de dos vacas es, en la práctica, lo que queda. Así, la ganancia de una vaca es siempre al menos tan buena como la ganancia de la respuesta de dos vacas. Por tanto, podemos ordenar todas las ganancias potenciales de sabrosura y elegir las $N$ más grandes para hallar la respuesta.

Implementación

Complejidad temporal: $\mathcal{O}((K+M)\log(K+M))$

C++JavaPython


#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
 
using namespace std;
 
int main() {
	int k, m, n;
	cin >> k >> m >> n;
 
	// guardar tanto los parches como las vacas de Nhoj en un solo arreglo
	vector<pair<int, long long>> entries(k + m);
	for (int i = 0; i < k; i++) {
		int pos, tasty;
		cin >> pos >> tasty;
		entries[i] = {pos, tasty};
	}
	for (int i = 0; i < m; i++) {
		int pos;
		cin >> pos;
		entries[k + i] = {pos, -1};  // marcar la vaca de Nhoj con sabrosura = -1
	}
	sort(entries.begin(), entries.end());
 
	vector<long long> contributions;
	long long sum_range = 0;
	int last_cow = -1;
 
	for (int i = 0; i < entries.size(); i++) {
		if (entries[i].second == -1) {  // encontramos una vaca de Nhoj
			if (last_cow == -1) {
				// intervalo más a la izquierda: John puede tomar toda la sabrosura con 1 vaca
				contributions.push_back(sum_range);
			} else {
				// intervalo del medio: calcular respuestas de 1 vaca y de 2 vacas
				long long interval_len = entries[i].first - entries[last_cow].first;
 
				long long cur_sum = 0, best_one = 0;
				int r = last_cow;
				for (int j = last_cow + 1; j < i; j++) {
					while (r + 1 < i && (entries[r + 1].first - entries[j].first) * 2 <
					                        interval_len) {
						cur_sum += entries[++r].second;
					}
					best_one = max(best_one, cur_sum);
					cur_sum -= entries[j].second;
				}
 
				// contribución de una vaca
				contributions.push_back(best_one);
				// ganancia adicional si colocamos una segunda vaca
				contributions.push_back(sum_range - best_one);
			}
			last_cow = i;
			sum_range = 0;
		} else {
			sum_range += entries[i].second;
		}
	}
 
	// intervalo más a la derecha: también se puede reclamar por completo con 1 vaca
	contributions.push_back(sum_range);
 
	// ordenar todas las contribuciones de forma decreciente
	sort(contributions.rbegin(), contributions.rend());
 
	// tomar las N mejores
	long long ans = 0;
	for (int i = 0; i < min(n, (int)contributions.size()); i++) {
		ans += contributions[i];
	}
 
	cout << ans << endl;
}


import java.io.*;
import java.util.*;
 
public class ClosestCowWins {
	static class Entry {
		int pos;
		long tastiness;
 
		Entry(int pos, long tastiness) {
			this.pos = pos;
			this.tastiness = tastiness;
		}
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		PrintWriter pw = new PrintWriter(System.out);
 
		String[] line = br.readLine().split(" ");
		int k = Integer.parseInt(line[0]);
		int m = Integer.parseInt(line[1]);
		int n = Integer.parseInt(line[2]);
 
		// guardar tanto los parches como las vacas de Nhoj en un solo arreglo
		List<Entry> entries = new ArrayList<>(k + m);
		for (int i = 0; i < k; i++) {
			line = br.readLine().split(" ");
			int pos = Integer.parseInt(line[0]);
			long tasty = Long.parseLong(line[1]);
			entries.add(new Entry(pos, tasty));
		}
		for (int i = 0; i < m; i++) {
			int pos = Integer.parseInt(br.readLine());
			entries.add(new Entry(pos, -1));  // marcar la vaca de Nhoj con sabrosura = -1
		}
		entries.sort(Comparator.comparingInt(e -> e.pos));
 
		List<Long> contributions = new ArrayList<>();
		long sum_range = 0;
		int last_cow = -1;
 
		for (int i = 0; i < entries.size(); i++) {
			if (entries.get(i).tastiness == -1) {  // encontramos una vaca de Nhoj
				if (last_cow == -1) {
					// intervalo más a la izquierda: John puede tomar toda la sabrosura con 1 vaca
					contributions.add(sum_range);
				} else {
					// intervalo del medio: calcular respuestas de 1 vaca y de 2 vacas
					long interval_len = entries.get(i).pos - entries.get(last_cow).pos;
 
					long cur_sum = 0, best_one = 0;
					int r = last_cow;
					for (int j = last_cow + 1; j < i; j++) {
						while (r + 1 < i &&
						       (entries.get(r + 1).pos - entries.get(j).pos) * 2 <
						           interval_len) {
							cur_sum += entries.get(++r).tastiness;
						}
						best_one = Math.max(best_one, cur_sum);
						cur_sum -= entries.get(j).tastiness;
					}
 
					// contribución de una vaca
					contributions.add(best_one);
					// ganancia adicional si colocamos una segunda vaca
					contributions.add(sum_range - best_one);
				}
				last_cow = i;
				sum_range = 0;
			} else {
				sum_range += entries.get(i).tastiness;
			}
		}
 
		// intervalo más a la derecha: también se puede reclamar por completo con 1 vaca
		contributions.add(sum_range);
 
		// ordenar todas las contribuciones de forma decreciente
		contributions.sort(Collections.reverseOrder());
 
		// tomar las N mejores
		long ans = 0;
		for (int i = 0; i < Math.min(n, contributions.size()); i++) {
			ans += contributions.get(i);
		}
 
		pw.println(ans);
		pw.close();
		br.close();
	}
}


k, m, n = map(int, input().split())
 
# guardar tanto los parches como las vacas de Nhoj en un solo arreglo
entries = []
 
for _ in range(k):
	pos, tasty = map(int, input().split())
	entries.append((pos, tasty))
 
for _ in range(m):
	pos = int(input())
	entries.append((pos, -1))  # marcar la vaca de Nhoj con sabrosura = -1
 
# ordenar por posición
entries.sort()
 
contributions = []
sum_range = 0
last_cow = -1
 
for i in range(len(entries)):
	if entries[i][1] == -1:  # encontramos una vaca de Nhoj
		if last_cow == -1:
			# intervalo más a la izquierda: John puede tomar toda la sabrosura con 1 vaca
			contributions.append(sum_range)
		else:
			# intervalo del medio: calcular respuestas de 1 vaca y de 2 vacas
			interval_len = entries[i][0] - entries[last_cow][0]
 
			cur_sum = 0
			best_one = 0
			r = last_cow
 
			for j in range(last_cow + 1, i):
				while (
					r + 1 < i and (entries[r + 1][0] - entries[j][0]) * 2 < interval_len
				):
					r += 1
					cur_sum += entries[r][1]
				best_one = max(best_one, cur_sum)
				cur_sum -= entries[j][1]
 
			# contribución de una vaca
			contributions.append(best_one)
			# ganancia adicional si colocamos una segunda vaca
			contributions.append(sum_range - best_one)
 
		last_cow = i
		sum_range = 0
	else:
		sum_range += entries[i][1]
 
# intervalo más a la derecha: también se puede reclamar por completo con 1 vaca
contributions.append(sum_range)
 
# ordenar todas las contribuciones de forma decreciente
contributions.sort(reverse=True)
 
# tomar las N mejores
ans = 0
for i in range(min(n, len(contributions))):
	ans += contributions[i]
 
print(ans)