11119 - Chemical Attraction

[Per]

I remember that last year during the coaches' meeting at the World Finals, Bill Poucher announced that from now on, all regional contests must publish their data.

If by "must" you mean "should", and by "publish" you mean "send to Miguel so he can put the problem in the live archive", then we remember the same thing. But I might remember incorrectly.

Regarding PC^2, if that's how you feel about validators (whose only fault are their interface), I'd be afraid to hear a rant on the things which are actually complicated to do in PC^2.

[Abednego]

You mean memory limits, automatic judging, a non-graphical contest configuration tool, a web interface, a readable scoreboard, automatic stopping of a contest, a way to run clients behind a firewall?...

I really shouldn't start talking about that.

[shahriar_manzoor]

For technical reasons I won't comment in details on data release of world finals. I think they have good reasons not doing it. And since they are not making mistakes it can be forgiven. But I don't think more than 30 % regional can produce 98% correct problemset. They are taking the advantage of not publishing data. The regionals need not publish official data, rather they can publish un official data but that is also a far cry.

In general I would say "Judges decision is final" is a very wrong sentence. It should be "If decisions are to be taken on ambigious judging events then judges decision is final.". Personally I am ready to defend any judging issue (Ofcourse of local/national contests) with the coaches or with the ICPC head quarters. But sometimes many strange complains are heard which are done without asking me.

[shahriar_manzoor]

I remember that last year during the coaches' meeting at the World Finals, Bill Poucher announced that from now on, all regional contests must publish their data.

If by "must" you mean "should", and by "publish" you mean "send to Miguel so he can put the problem in the live archive", then we remember the same thing. But I might remember incorrectly.

It seems that as I miss out the coaches briefing each year I miss out many interesting things .

[dull_jester]

I am also checking the stability, as well as that all the pairs are present. However, WA. any ideas why?

Code: Select all

/*
 * 11119. chemical Attraction
 * TOPIC: bipartite matching, stable matching
 * status:
 */
#include <cassert>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <set>
#include <vector>
#define N 0x400
#define MAXC 0x800
#include <queue>
#include <algorithm>
using namespace std;
enum { S, T };

int id[2][MAXC],n[2],
	m[2][N][N],compounds,
	u[2][N],len[2],
	_rank[2][N][N],
	ptr[N],mate[2][N],
	has_proposed[N][N],yes;
char name[2][N][8];
vector<int> lst[2][N];
queue<int> q;

int conv( char *s ) {
	int x = (0[s]-'A'), y = (1[s]-'a');
	return y|(x<<5);
}

int find( char *s ) {
	int t,i,c = conv(s);
	for ( t = S; t <= T; ++t )
		if ( id[t][c] >= 0 )
			return t|(id[t][c]<<1);
	assert(0);
}

int main() {
	int i,j,k,t,cs = 0,mx,x,y,nx,ny;
	char a[0x10];
#ifndef ONLINE_JUDGE
	freopen("11119.in","r",stdin);
#endif
	for (;1==scanf("%d",&n[S])&&n[S];) {
		memset(id,-1,sizeof id);
		for ( i = 0; i < n[S]; ++i )
			scanf("%s",a), id[S][conv(a)] = i, strcpy(name[S][i],a);
		for ( scanf("%d",&n[T]), i = 0; i < n[T]; ++i )
			scanf("%s",a), id[T][conv(a)] = i, strcpy(name[T][i],a);
		for ( t = S; t <= T; ++t ) 
			for ( i = 0; i < n[t]; ++i )
				for ( j = 0; j < n[t^1]; ++j )
					scanf("%d",&m[t][i][j]), _rank[t][i][--m[t][i][j]] = j;
		for ( ++cs, mx = 0; 1 == scanf("%d",&compounds) && compounds; putchar('\n') ) {
			memset(mate,-1,sizeof mate);
			printf("Scenario %d, Mixture %d:\n",cs,++mx);
			for ( t = S; t <= T; ++t ) 
				for ( len[t] = 0, i = 0; i < n[t]; lst[t][i++].clear() );
			for ( i = 0; i < compounds; ++i ) {
				scanf("%s",a), x = find(a), y = find(a+2);
				assert( (x&1)^(y&1) );
				if ( T==(x&1) )
					k=x,x=y,y=k;
				u[S][len[S]++]=(x>>1),u[T][len[T]++]=(y>>1);
				lst[S][x>>1].push_back(len[S]-1);
				lst[T][y>>1].push_back(len[T]-1);
			}
			for ( i = 0; i < len[S]; q.push(i), ptr[i++] = n[T]-1 );
			for ( ++yes; !q.empty(); ) {
				x = q.front(), q.pop(), nx = u[S][x];
				assert( mate[S][x] < 0 );
				assert( ptr[x] >= 0 );
				for (;ptr[x]>=0;) {
					for ( ny = m[S][nx][ptr[x]--], i = 0; i < (int)lst[T][ny].size(); ++i ) {
						assert( u[T][y=lst[T][ny][i]]==ny );
						if ( has_proposed[x][y] == yes ) continue ;
						has_proposed[x][y] = yes;
						if ( mate[T][y] < 0 ) {
							mate[T][mate[S][x] = y] = x, ++ptr[x];
							goto br;
						}
						if ( _rank[T][ny][nx] > _rank[T][ny][u[S][mate[T][y]]] ) {
							q.push(mate[T][y]), mate[S][mate[T][y]] = -1;
							mate[T][mate[S][x] = y] = x, ++ptr[x];
							goto br;
						}
					}
					continue ;
					br: break ;
				}
				assert( mate[S][x] >= 0 );
			}
			for ( i = 0; i < len[T]; ++i )
				assert( mate[T][i] >= 0 );
			set<int> st;
			for ( i = 0; i < len[S]; ++i )
				st.insert(mate[S][i]);
			assert( st.size() == len[T] );
			for ( st.clear(), i = 0; i < len[T]; ++i )
				st.insert(mate[T][i]);
			assert( st.size() == len[S] );
			for ( i = 0; i < len[S]; ++i )
				for ( j = 0; j < len[S]; ++j )
					if ( i != j ) {
						int aa = u[S][i], bb = u[T][mate[S][i]],
							cc = u[S][j], dd = u[T][mate[S][j]];
						assert( !(_rank[S][aa][dd] > _rank[S][aa][bb] && _rank[T][dd][aa] > _rank[T][dd][cc]) );
					}
			for ( i = 0; i < len[S]; ++i )
				printf("%s%s%c",name[S][u[S][i]],name[T][u[T][mate[S][i]]],i==len[S]-1?'\n':' ');
		}
	}
	return 0;
}