USACO 2020 US Open Contest, Silver Problem 2. Cereal

USACO 2020 US Open Contest, Silver Problem 2. Cereal

Farmer John's cows like nothing more than cereal for breakfast! In fact, the cows have such large appetites that they will each eat an entire box of cereal for a single meal.

The farm has recently received a shipment with MM different types of cereal (1≤M≤105)(1≤M≤105) . Unfortunately, there is only one box of each cereal! Each of the NN cows (1≤N≤105)(1≤N≤105) has a favorite cereal and a second favorite cereal. When given a selection of cereals to choose from, a cow performs the following process:

 

1. If the box of her favorite cereal is still available, take it and leave.
2. Otherwise, if the box of her second-favorite cereal is still available, take it and leave.
3. Otherwise, she will moo with disappointment and leave without taking any cereal.

The cows have lined up to get cereal. For each 0≤i≤N−10≤i≤N−1, determine how many cows would take a box of cereal if Farmer John removed the first ii cows from the line.

 

 

 

SAMPLE INPUT:

4 2
1 2
1 2
1 2
1 2

SAMPLE OUTPUT:

2
2
2
1

If at least two cows remain, then exactly two of them get a box of cereal.

Problem credits: Dhruv Rohatgi

 USACO 2020 US Open Contest, Silver Problem 2. Cereal 题解(翰林国际教育提供，仅供参考)

题解请注册或登录查看

[/hide]

(Analysis by Dhruv Rohatgi )

Suppose that Farmer John doesn't remove any cows from the line. Then we can simply simulate the actions of the cows in order, keeping track of which boxes of cereal are left. This yields an O(N2)O(N2) solution to the original problem: for each ii, simulate the last N−iN−i cows.

There are several ways to speed up this solution. One way is to start with i=Ni=N and add cows one by one. Suppose we have solved the problem for the last N−iN−i cows: that is, if the last N−iN−i cows line up in order, we know which box each cow takes. We want to efficiently update this outcome to the outcome if instead the last N+1−iN+1−i cows were to line up. Thus, we need to handle the operation "add cow to front of line".

Suppose the new cow has preferences (f,s)(f,s). Then the new cow will certainly get cereal ff. If the last N−iN−i cows didn't take cereal ff, then nothing will change: all of those cows have the same outcomes after adding the new cow. But if some cow jj had taken cereal ff, then after adding the new cow, jj no longer gets ff. If ff is jj's second choice, then now jj gets nothing---and all other cows have the same outcomes. If ff is jj's first choice, and her second choice was taken by some cow earlier in line, then again jj gets nothing, and all other cows have the same outcome. But if jj's second choice was not taken by some cow earlier in line, then jj will take it. Unfortunately, this case may cause a cascade: we need to recurse on jj and figure out whether jj stole her second-choice cereal from someone later in line, and so forth.

At each step of the recursion, a cow jj can only "steal" from one later cow: the cow who originally took the cereal which jj is now taking. So the above algorithm doesn't blow up exponentially or anything. But each addition of a new cow seems like it could cause a recursion of depth O(N)O(N), which would imply an overall time complexity of O(N2)O(N2)!

Fortunately, this is not the case: we can show that the sum of the recursion depths is actually O(N)O(N). The reason is that every time we recurse, a cow is either kicked from first-preference to second-preference or from second-preference to nothing. Moreover, as we add cows, the reverse can never happen: a cow who was getting nothing cannot suddenly get something when we add a cow to the front of the line. It follows that the total depth of all the recursion is at most 2N2N.

To implement the algorithm efficiently (with a constant-time update at each recursion step) we just need to keep track of which cow currently gets each box of cereal (occ[pos]occ[pos] stores the index of the cow that gets cereal pospos). The final algorithm runs in time O(N)O(N). See my code below:

 

#include <iostream>
#include <algorithm>
using namespace std;
#define MAXN 100001

int N,M;
int f[MAXN];
int s[MAXN];
int occ[MAXN];

int ans[MAXN];

int main()
{
	cin >> N >> M;
	for(int i=0;i<N;i++)
		cin >> f[i] >> s[i];
	int cnt = 0;
	for(int i=N-1;i>=0;i--)
	{
		int j = i;
		int pos = f[i];
		while(1)
		{
			if(occ[pos] == 0)
			{
				occ[pos] = j;
				cnt++;
				break;
			}
			else if(occ[pos] < j)
				break;
			else
			{
				int k = occ[pos];
				occ[pos] = j;
				if(pos == s[k])
					break;
				j = k;
				pos = s[k];
			}
		}
		ans[i] = cnt;
	}
	for(int i=0;i<N;i++)
		cout << ans[i] << '\n';
}

[/hide]