Skip to Content
CTRL K

Meetings

Editorial oficial (C++) 

Este problema es extremadamente difícil para Plata, ¡así que no te sientas mal si te trabas!

Explicación

Análisis inicial

Primero que nada, ¿qué ocurre realmente durante un encuentro?

Las vacas “rebotan” entre sí, pero eso es muy difícil de pensar y de implementar.

Una forma alternativa de encarar esta mecánica de encuentro es que las vacas intercambian pesos y siguen su camino. Si lo pensamos así, entonces tenemos todos los tiempos en que las vacas llegarán al granero porque tenemos sus posiciones y velocidades.

Por supuesto, ahora hay que tener en cuenta los pesos de las vacas.

Pensemos primero desde la vaca más a la izquierda que va hacia la izquierda. Si es la vaca más a la izquierda en general, no pasará nada. Sin embargo, si hay algunas vacas a su izquierda, siempre tomará el peso de la vaca más a la izquierda que va hacia la derecha porque esa es la vaca con la que se encontrará al final. Más precisamente, siempre tomará el peso de la vaca más a la izquierda en general.

Pasando a la segunda vaca más a la izquierda que va hacia la izquierda (si hay una), tomará el peso de la segunda vaca más a la izquierda en general, porque el peso de la vaca más a la izquierda ya fue tomado.

Este patrón se generaliza a las siguientes dos reglas:

  • Si una vaca va hacia la izquierda y es la nn-ésima vaca más a la izquierda que va hacia la izquierda, siempre tomará la posición de la nn-ésima vaca más a la izquierda en general.
  • Si una vaca va hacia la derecha y es la nn-ésima vaca más a la derecha que va hacia la derecha, siempre tomará la posición de la nn-ésima vaca más a la derecha en general.

Con esta regla y las observaciones anteriores, podemos hallar los tiempos en que las vacas llegarán a las salidas y los pesos con los que llegarán, y así sabremos el momento en que la mitad del peso total de las vacas habrá llegado a un granero.

Solución final

Dado que tenemos el tiempo de fin, solo hay que contar de forma eficiente el número de encuentros que ocurrirán antes de ese tiempo.

Para esto, recorremos todas las vacas en orden y, para cada vaca que va hacia la izquierda, vemos cuántas vacas que van hacia la derecha están dentro de su rango. Podemos hacer esto con una cola y la observación de que una vaca que va hacia la izquierda en la posición ll y una vaca que va hacia la derecha en la posición rr pueden encontrarse si l<rl<r y r+2e≥lr+2e \geq l, donde ee es el tiempo de fin.

Implementación

Complejidad temporal: O(Nlog⁡N)\mathcal{O}(N \log N)

#include <algorithm>
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>
 
using std::cout;
using std::endl;
using std::vector;
 
struct Cow {
	int weight;
	int pos;
	int speed;
};
 
int main() {
	std::ifstream read("meetings.in");
 
	int cow_num;
	int barn_pos;
	read >> cow_num >> barn_pos;
 
	vector<Cow> cows(cow_num);
	int total_weight = 0;
	for (Cow &c : cows) {
		read >> c.weight >> c.pos >> c.speed;
		total_weight += c.weight;
	}
 
	std::sort(cows.begin(), cows.end(),
	          [](const Cow &c1, const Cow &c2) { return c1.pos < c2.pos; });
 
	// obtenemos las vacas que empiezan yendo a la izquierda y a la derecha
	vector<Cow> left;
	vector<Cow> right;
	for (const Cow &c : cows) {
		if (c.speed == -1) {
			left.push_back(c);
		} else if (c.speed == 1) {
			right.push_back(c);
		}
	}
 
	/*
	 * calculamos cada uno de los tiempos en que las vacas llegan al final
	 * las vacas más a la izquierda reciben todas las posiciones de las vacas -1 como tiempos,
	 * y de forma similar para las más a la derecha
	 */
	vector<std::pair<int, int>> weight_times;
	for (int c = 0; c < left.size(); c++) {
		// tiempo de llegada al granero y peso, respectivamente
		weight_times.push_back({left[c].pos, cows[c].weight});
	}
	for (int c = 0; c < right.size(); c++) {
		weight_times.push_back({barn_pos - right[c].pos, cows[left.size() + c].weight});
	}
 
	// las ordenamos por su ocurrencia
	std::sort(weight_times.begin(), weight_times.end(),
	          [](const std::pair<int, int> &a, const std::pair<int, int> &b) {
		          return a.first < b.first;
	          });
 
	int endTime = -1;
	for (const auto &[time, weight] : weight_times) {
		total_weight -= 2 * weight;
		if (total_weight <= 0) {
			endTime = time;
			break;
		}
	}
 
	// contamos cuántos encuentros ocurren antes del tiempo de fin
	int meeting_num = 0;
	// las vacas con las que una vaca que va a la izquierda puede encontrarse antes del tiempo de fin
	std::queue<int> leftSide;
	for (int c = 0; c < cow_num; c++) {
		if (cows[c].speed == 1) {
			leftSide.push(cows[c].pos);
		} else if (cows[c].speed == -1) {
			// quitamos todas las vacas que no pueden encontrarse con esta vaca que va a la izquierda
			while (!leftSide.empty() && leftSide.front() + 2 * endTime < cows[c].pos) {
				leftSide.pop();
			}
			meeting_num += leftSide.size();
		}
	}
 
	std::ofstream("meetings.out") << meeting_num << endl;
}
import java.io.*;
import java.util.*;
 
public class Meetings {
	static class Cow {
		public int weight;
		public int pos;
		public int speed;
		public Cow(int weight, int pos, int speed) {
			this.weight = weight;
			this.pos = pos;
			this.speed = speed;
		}
	}
 
	public static void main(String[] args) throws IOException {
		BufferedReader read = new BufferedReader(new FileReader("meetings.in"));
		StringTokenizer initial = new StringTokenizer(read.readLine());
 
		int cowNum = Integer.parseInt(initial.nextToken());
		int barnPos = Integer.parseInt(initial.nextToken());
 
		Cow[] cows = new Cow[cowNum];
		int totalWeight = 0;
		for (int c = 0; c < cowNum; c++) {
			StringTokenizer cow = new StringTokenizer(read.readLine());
			cows[c] = new Cow(Integer.parseInt(cow.nextToken()),
			                  Integer.parseInt(cow.nextToken()),
			                  Integer.parseInt(cow.nextToken()));
			totalWeight += cows[c].weight;
		}
 
		Arrays.sort(cows, Comparator.comparingInt(c -> c.pos));
 
		// obtenemos las vacas que empiezan yendo a la izquierda y a la derecha
		List<Cow> left = new ArrayList<>();
		List<Cow> right = new ArrayList<>();
		for (Cow c : cows) {
			if (c.speed == -1) {
				left.add(c);
			} else if (c.speed == 1) {
				right.add(c);
			}
		}
 
		/*
		 * calculamos cada uno de los tiempos en que las vacas llegan al final
		 * las vacas más a la izquierda reciben todas las posiciones de las vacas -1 como tiempos,
		 * y de forma similar para las más a la derecha
		 */
		List<int[]> weightTimes = new ArrayList<>();
		for (int c = 0; c < left.size(); c++) {
			// tiempo de llegada al granero y peso, respectivamente
			weightTimes.add(new int[] {left.get(c).pos, cows[c].weight});
		}
		for (int c = 0; c < right.size(); c++) {
			weightTimes.add(
			    new int[] {barnPos - right.get(c).pos, cows[left.size() + c].weight});
		}
 
		// las ordenamos por su ocurrencia
		weightTimes.sort(Comparator.comparingInt(t -> t[0]));
 
		int endTime = -1;
		for (int[] barnMeeting : weightTimes) {
			totalWeight -= 2 * barnMeeting[1];
			if (totalWeight <= 0) {
				endTime = barnMeeting[0];
				break;
			}
		}
 
		// contamos cuántos encuentros ocurren antes del tiempo de fin
		int meetingNum = 0;
		// las vacas con las que una vaca que va a la izquierda puede encontrarse antes del tiempo de fin
		Queue<Integer> leftSide = new ArrayDeque<>();
		for (int c = 0; c < cowNum; c++) {
			if (cows[c].speed == 1) {
				leftSide.add(cows[c].pos);
			} else if (cows[c].speed == -1) {
				// quitamos todas las vacas que no pueden encontrarse con esta vaca que va a la izquierda
				while (!leftSide.isEmpty() &&
				       leftSide.peek() + 2 * endTime < cows[c].pos) {
					leftSide.poll();
				}
				meetingNum += leftSide.size();
			}
		}
 
		PrintWriter written = new PrintWriter("meetings.out");
		written.println(meetingNum);
		written.close();
	}
}
from typing import NamedTuple
from collections import deque
 
 
class Cow(NamedTuple):
	weight: int
	pos: int
	speed: int
 
 
with open("meetings.in") as read:
	cow_num, barn_pos = [int(i) for i in read.readline().split()]
	cows = [Cow(*[int(i) for i in read.readline().split()]) for _ in range(cow_num)]
	total_weight = sum(c.weight for c in cows)
 
cows.sort(key=lambda c: c.pos)
 
# obtenemos las vacas que empiezan yendo a la izquierda y a la derecha
left = []
right = []
for c in cows:
	if c.speed == -1:
		left.append(c)
	elif c.speed == 1:
		right.append(c)
 
"""
calculamos cada uno de los tiempos en que las vacas llegan al final
las vacas más a la izquierda reciben todas las posiciones de las vacas -1 como tiempos,
y de forma similar para las más a la derecha
"""
weight_times = []
for c in range(len(left)):
	# tiempo de llegada al granero y peso, respectivamente
	weight_times.append((left[c].pos, cows[c].weight))
for c in range(len(right)):
	weight_times.append((barn_pos - right[c].pos, cows[len(left) + c].weight))
 
# las ordenamos por su ocurrencia
weight_times.sort(key=lambda t: t[0])
 
end_time = -1
for time, weight in weight_times:
	total_weight -= 2 * weight
	if total_weight <= 0:
		end_time = time
		break
 
# contamos cuántos encuentros ocurren antes del tiempo de fin
meeting_num = 0
# las vacas con las que una vaca que va a la izquierda puede encontrarse antes del tiempo de fin
left_side = deque()
for c in range(cow_num):
	if cows[c].speed == 1:
		left_side.append(cows[c].pos)
	elif cows[c].speed == -1:
		# quitamos todas las vacas que no pueden encontrarse con esta vaca que va a la izquierda
		while left_side and left_side[0] + 2 * end_time < cows[c].pos:
			left_side.popleft()
		meeting_num += len(left_side)
 
print(meeting_num, file=open("meetings.out", "w"))
Fundamentos