Official Editorial (C++)

This problem is extremely hard for Silver, so don't feel bad if you get stuck on it!

Explanation

Initial Analysis

First of all, what really happens during a meeting?

The cows do "bounce" off from each other, but that's really hard to think about and implement.

An alternative way to approach this meeting mechanic is that the cows swap weights and continue on their way. If we think about it like that, then we have all the times the cows will reach the barn because we have their positions and speeds.

Of course, now we have to account for the weights of the cows.

Let's first think about it from the leftmost left-going cow. If it's the leftmost cow overall, nothing will happen. However, if there's some cows to the left of it, it will always take on the weight of the leftmost right-going cow because that's the cow it will meet last. More precisely, it will always take on the weight of the leftmost cow overall.

Moving on the second leftmost left-going cow (if there is one), it will take on the weight of the second leftmost cow overall, because the leftmost cow's weight has been taken.

This pattern generalizes to the following two rules:

• If a cow is going left and is the $n$-th leftmost left-going cow, it will always take on the position of the $n$-th leftmost cow overall.
• If a cow is going right and is the $n$-th rightmost right-going cow, it will always take on the position of the $n$-th rightmost cow overall.

With this rule and the previous observations, we can figure out the times at which cows will reach exits and the weights they will reach it with, and thus we will know the time at which half the total cows' weight will have reached a barn.

Final Solution

Given that we have the end time, we just have to efficiently count the number of meetings that will occur before that time.

To do this, we iterate through all cows in order, for each left-going cow seeing how many right-going cows are within their range. We can do this with a queue and the observation that a left-going cow at position $l$ and a right-going cow at position $r$ can meet if $l<r$ and $r+2e \geq l$, where $e$ is the ending time.

Implementation

Time Complexity: $\mathcal{O}(N \log N)$

Copy
#include <algorithm>
#include <fstream>
#include <iostream>
#include <queue>
#include <vector>

using std::cout;
using std::endl;
using std::vector;

Copy
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;

Copy
from typing import NamedTuple
from collections import deque


class Cow(NamedTuple):
	weight: int
	pos: int
	speed: int