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]