USACO 2019 December Contest, Silver Problem 2. Meetings

USACO 2019 December Contest, Silver Problem 2. Meetings

Two barns are located at positions 00 and LL (1≤L≤109)(1≤L≤109) on a one-dimensional number line. There are also NN cows (1≤N≤5⋅104)(1≤N≤5⋅104) at distinct locations on this number line (think of the barns and cows effectively as points). Each cow ii is initially located at some position xixi and moving in a positive or negative direction at a speed of one unit per second, represented by an integer didi that is either 11 or −1−1. Each cow also has a weight wiwi in the range [1,103][1,103]. All cows always move at a constant velocity until one of the following events occur:

• If cow ii reaches a barn, then cow ii stops moving.
• A meeting occurs when two cows ii and jj occupy the same point, where that point is not a barn. In this case, cow ii is assigned cow jj's previous velocity and vice versa. Note that cows could potentially meet at points that are not integers.

Let TT be the earliest point in time when the sum of the weights of the cows that have stopped moving (due to reaching one of the barns) is at least half of the sum of the weights of all cows. Please determine the total number of meetings between pairs of cows during the range of time 0…T0…T (including at time TT).

 

 

 

 

SAMPLE INPUT:

3 5
1 1 1
2 2 -1
3 3 -1

SAMPLE OUTPUT:

2

The cows in this example move as follows:

 

1. The first and second cows meet at position 1.5 at time 0.5. The first cow now has velocity −1−1 and the second has velocity 1.1.
2. The second and third cows meet at position 2 at time 1. The second cow now has velocity −1−1 and the third has velocity 1.1.
3. The first cow reaches the left barn at time 2.
4. The second cow reaches the left barn at time 3.
5. The process now terminates since the sum of the weights of the cows that have reached a barn is at least half of the sum of the weights of all cows. The third cow would have reached the right barn at time 4.

Exactly two meetings occurred.

 

Problem credits: Benjamin Qi

<h3>USACO 2019 December Contest, Silver Problem 2. Meetings 题解(翰林国际教育提供，仅供参考)</h3>
<p style="text-align: center;">题解请<a href="/register" target="_blank" rel="noopener">注册</a>或<a href="/login" target="_blank" rel="noopener">登录</a>查看</p>
[/hide]

(Analysis by Benjamin Qi)

Note: This problem is quite tricky for silver!

First, sort all the cows by xx-coordinate. For partial credit, we can simulate each collision that the cows make in O(N),O(N), for a worst-case runtime of O(N3).O(N3).

To make solving the problem in O(NlogN)O(Nlog⁡N) more manageable, let's split it into two independent parts.

Part 1: Determining T.T.

Consider the multiset of all times when the cows reach the barns. If the cows did not actually switch velocities,

 

• Cows with di=−1di=−1 contribute xixi to the multiset.
• Cows with di=1di=1 contribute L−xiL−xi to the multiset.

Nevertheless, this multiset remains the same regardless of whether cows switch velocities or not.

Let zz be the number of cows with di=−1.di=−1. Then exactly zz cows reach the left barn, so these must be precisely the zz leftmost cows. Thus, we can just take all of the xixi for the cows with initial di=−1di=−1 and set these equal to the finishing times of the zz leftmost cows. Similarly, we can just take all of the L−xiL−xi for cows with initial di=1di=1 and set these equal to the finishing times of the N−zN−z rightmost cows. After this, we can sort all the finishing times again and maintain the current total weight in order to determine T.T.

Part 2: Determining the number of meetings.

Now we can ignore the weight condition and assume that cows do not switch velocities after meeting; essentially, they will pass through each other. This will not affect the answer. Then two cows with xi<xjxi<xj will meet if di=1,dj=−1,xi+2T≥xj.di=1,dj=−1,xi+2T≥xj. The number of such pairs can be computed by iterating from left to right and maintaining a queue that consists of those cows with di=1di=1 that you are currently considering as meeting candidates.

 

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi; 
typedef vector<pair<int,int>> vpi; 
 
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)
 
#define pb push_back
#define rsz resize
#define sz(x) int(x.size())
#define all(x) begin(x), end(x)
#define f first
#define s second

void setIO(string name) {
	ios_base::sync_with_stdio(0); cin.tie(0);
	freopen((name+".in").c_str(),"r",stdin);
	freopen((name+".out").c_str(),"w",stdout);
}

int N,L;
vi w,x,d;
 
void init() {
	setIO("meetings");
	cin >> N >> L;
	w.rsz(N), x.rsz(N), d.rsz(N);
	F0R(i,N) cin >> w[i] >> x[i] >> d[i];
	vi inds(N); iota(all(inds),0);
	sort(all(inds),[](int a, int b) { return x[a] < x[b]; });
	vi W,X,D;
	trav(t,inds) {
		W.pb(w[t]);
		X.pb(x[t]);
		D.pb(d[t]);
	}
	swap(w,W), swap(x,X), swap(d,D);
}
 
int getTime() {
	vi lef, rig;
	F0R(i,N) {
		if (d[i] == -1) lef.pb(x[i]);
		else rig.pb(x[i]);
	}
	vpi v;
	F0R(i,sz(lef)) v.pb({lef[i],w[i]});
	F0R(i,sz(rig)) v.pb({L-rig[i],w[sz(lef)+i]});
	sort(all(v));
	int tot = 0; trav(t,v) tot += t.s;
	trav(t,v) {
		tot -= 2*t.s;
		if (tot <= 0) return t.f;
	}
}
 
int main() {
	init();
	int t = getTime(); 
	queue<int> rig;
	int ans = 0;
	F0R(i,N) {
		if (d[i] == -1) {
			while (sz(rig) && rig.front()+2*t < x[i]) rig.pop();
			ans += sz(rig);
		} else rig.push(x[i]);
	}
	cout << ans << "\n";
}

For some more problems in the same spirit see

• Independence #20
• Ants on a Circle (AtCoder)
• Ants on a Circle (CodeForces)

[/hide]