11119 - Chemical Attraction

All about problems in Volume 111. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden

Post by Per » Mon Oct 23, 2006 10:46 pm

Abednego wrote: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. :)

User avatar
Abednego
A great helper
Posts: 281
Joined: Tue Sep 10, 2002 5:14 am
Location: Mountain View, CA, USA
Contact:

Post by Abednego » Mon Oct 23, 2006 10:57 pm

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.
If only I had as much free time as I did in college...

shahriar_manzoor
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

Post by shahriar_manzoor » Tue Oct 24, 2006 12:08 am

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
System administrator & Problemsetter
Posts: 399
Joined: Sat Jan 12, 2002 2:00 am

hmm

Post by shahriar_manzoor » Tue Oct 24, 2006 7:53 am

Per wrote:
Abednego wrote: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
New poster
Posts: 17
Joined: Fri Oct 21, 2016 12:58 pm
Location: NS, Canada

Re: 11119 - Chemical Attraction

Post by dull_jester » Sun Nov 13, 2016 1:41 pm

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;
}



Post Reply

Return to “Volume 111 (11100-11199)”

Who is online

Users browsing this forum: No registered users and 1 guest