[Logo] Форум DL
  [DL]  На главную страницу 
Индекс форума ->Олимпиадное программирование ->USACO Analyses
Автор Сообщение
Михаил Долинский

Темы: 1440
Сообщений: 34071

Мой профиль
(Analysis by Dhruv Rohatgi )
Suppose we had a function which could tell us if a given set of constraints is satisfiable. Then we could easily determine the earliest possible location of cow $1$: just loop over all possible positions. For each location $i$, add a constraint requiring that cow $1$ is at position $i$, and check if the resulting set of constraints is valid.

Now let's figure out how to check if a set of constraints is satisfiable. For each constraint of the form "cow $i$ must be at position $j$", we can place cow $i$ in position $j$, and mark cow $i$ and position $j$ as "used". If a position is used multiple times, or a cow is used multiple times at different locations, then the constraints are invalid.

Otherwise, we have a set of "free" cows, a set of "free" positions, and a list of cows who must satisfy a given order. Let's loop over the cows in the given order. For each cow, we want to place it in the earliest free position such that the cow is positioned after the previous cow in the order. To compute these earliest-possible-positions, as we scan through the list we can also scan through all positions, incrementing a pointer while the position being looked at is either used or too early. Slight care must be taken to process cows in the list whose locations are already fixed.

The satisfiability check therefore takes $O(N+M+K)$ time. In the worst case, we must perform $N$ checks to determine the earliest possible position of cow $1$, for an overall runtime of $O(N(N+M+K))$.

#include <iostream>
#include <algorithm>
using namespace std;
 
bool usedCow[100];
bool usedPos[100];
int pos[100];
 
 
int nCows, M, nFixed;
 
int ord[100];
 
int cFixed[101];
int pFixed[101];
 
bool works()
{
	for(int i=0;i<nCows;i++)
		usedCow[i] = usedPos[i] = 0;
	for(int i=0;i<nFixed;i++)
	{
		if(usedCow[cFixed[i]] && pos[cFixed[i]] == pFixed[i]) continue;
		if(usedCow[cFixed[i]]) return 0;
		if(usedPos[pFixed[i]]) return 0;
		usedCow[cFixed[i]] = 1;
		usedPos[pFixed[i]] = 1;
		pos[cFixed[i]] = pFixed[i];
	}
	int j = 0;
	for(int i=0;i<M;i++)
	{
		int cow = ord[i];
		if(usedCow[cow])
		{
			if(j > pos[cow]) return 0;
			j = pos[cow];
			continue;
		}
		while(usedPos[j])
		{
			j++;
			if(j == nCows)
				return 0;
		}
		usedPos[j] = 1;
		pos[cow] = j;
	}
	return 1;
}
 
int main()
{
	cin >> nCows >> M >> nFixed;
	for(int i=0;i<M;i++)
	{
		cin >> ord[i];
		ord[i]--;
	}
	for(int i=0;i<nFixed;i++)
	{
		cin >> cFixed[i] >> pFixed[i];
		cFixed[i]--, pFixed[i]--;
	}
	nFixed++;
	for(int i=0;i<nCows;i++)
	{
		cFixed[nFixed-1] = 0;
		pFixed[nFixed-1] = i;
		if(works())
		{
			cout << i+1 << '\n';
			return 0;
		}
	}
}

 
Индекс форума ->Олимпиадное программирование ->USACO Analyses
Time:0,031