259 - Software Allocation

[K0stIa]

Is that valid input..?
My AC code returns "_AB_______"

Anyway, your approach look correct..
But, your code is missing '\n' after the last case.. (when the output of the last case is not '!')

So, it's still WA I'm very disappointed. Can u show me ur code ? I don't understand what wrong with it

And, if there multi answer allowed, what kind of case I should to choose for my answer ?

And, what do u think about next test?
A1 2;
C1 1;
B1 12;
B1 1234;

According to the UVA toolkit the answer must be equal to "_CABB_____";
now I'm going to research this test case more deeply.

User 1 comes to solve him one problem "A", he can to do it only on 2nd computer,
then user 2 has one problem "C" and he can solve it only on first computer,
user 3, have one problem B , and cans solve it only on first r second machine,
user 4, as user 3, also has the same "B", but he can solve it on 1,2,3,4 computers.

according to the uva toolkits answer user 3 can solves his problem on computer 3 & 4 also, it looks naturally if user 3 and 4 has problems identical "B".
Ok, lets try to look on the next two test cases:

A1 2;
C1 1;
V1 234;
B1 2345;
B1 3;

and

A1 2;
C1 1;
V1 23;
B1 2345;
B1 3;

Who can explain to me why first has answer "_CABVB____" and second has "_CAVBB____" according to the UVA toolkit?

Who has solved this damned PROBLEM ?

So, i'm interested in input data from the UVA server, how i can get it ?

[helloneo]

I PMed you..

Don't go deeper.. There are many other good problems..

[AhmadKhatar]

Hi!
Does any body know where my mistake is?
I spent a lot of time but I couldn't find it!
Thanks in advance!

Code: Select all

#define SOURCE 36
#define SINK 37
#define FIRSTCMP 26

#include <iostream>
using std::cin;
using std::cout;
using std::endl;

#include <queue>
using std::queue;

#include <string>
using std::string;

using std::min;

int f [ 38 ][ 38 ]; // 0..25 are chars, 26..35 are computers, 36 is source, 37 is sink, 
int p [ 38 ];
int totalWorks;

void process();
int bfs();

int main()
{
	char tempL [ 15 ];

	// initialize
	for ( int i = 0; i < 38; i++ )
	{
		for ( int j = 0; j < 38; j++ )
		{
		   f[ i ][ j ] = 0;
		}
	}

	totalWorks = 0;


	while ( cin.getline( tempL, 15, '\n' ) )
	{
		if ( tempL[ 0 ] == NULL )
		{
			process();

			// refresh
			for ( int i = 0; i < 38; i++ )
			{
				for ( int j = 0; j < 38; j++ )
				{
					f[ i ][ j ] = 0;
				}
			}

			totalWorks = 0;
		}
		else
		{
			totalWorks += tempL[ 1 ] - 48;
			int lastGoodInd = 3;
			for ( int i = 4; tempL[ i ] != ';'; i++ )
			{
				lastGoodInd++;
			}

			f[ SOURCE ][ ( tempL[ 0 ] - 65 ) ] = tempL[ 1 ] - 48;
			for ( int i = 3; i <= lastGoodInd; i++ )
			{
				f[ ( tempL[ 0 ] - 65 ) ][ FIRSTCMP + tempL[ i ] - 48 ] = tempL[ 1 ] - 48; // here we could assign to 1
				f[ FIRSTCMP + tempL[ i ] - 48 ][ SINK ] = 1;
			}
		}
	}

	return 0;
}

void process()
{
	string toOut = "__________";
	
	int maxFlow = 0;
	int incPath;
	while ( bfs() != 0 )
	{
		incPath = -1;
		for ( int i = SINK; i != SOURCE; i = p[ i ] )
		{
			if ( incPath == -1 )
			{
				incPath = f[ p[ i ] ][ i ];
			}
			else
			{
				incPath = min( incPath, f[ p[ i ] ][ i ] );
			}
		}

		for ( int i = SINK; i != SOURCE; i = p[ i ] )
		{
			f[ p[ i ] ][ i ] -= incPath;
			f[ i ][ p[ i ] ] += incPath;
		}

		maxFlow += incPath;
	}

	if ( maxFlow < totalWorks )
	{
		cout << "!" << endl;
	}
	else
	{
		for ( int i = 0; i <= 25; i++ )
		{
			for ( int j = 26; j <= 35; j++ )
			{
				if ( f[ j ][ i ] == 1 ) // NOTE THAT here f[ i ][ j ] == 0 doesn't work
				{
					toOut[ j - 26 ] = static_cast<char>( ( i % 26 ) + 65 );
				}
			}
		}

		cout << toOut << endl;
	}
}

int bfs() // returns sink plus the augmenting path
{
	int curNode;
	queue<int> q;
	int color[ 38 ];
	
	for ( int i = 0; i < 38; i++ )
	{
		color[ i ] = 0; // 0 is white, 1 is gray
		p[ i ] = -1;
	}

	q.push( SOURCE );
	color[ SOURCE ] = 1;

	while (!q.empty())
	{
		curNode = q.front();
		q.pop();

		for ( int i = 0; i < 38; i++ )
		{
			if ( f[ curNode ][ i ] > 0 && color[ i ] == 0 )
			{
				p[ i ] = curNode;
				color[ i ] = 1;
				if ( i == SINK )
				{
					return SINK; // a positive integer
				}
				q.push( i );
			}
		}
	}

	return 0; // because no vertex has value 0 (vertex numbers start from 1) no problem is with 0
}

[brianfry713]

Doesn't match the sample I/O.

[AhmadKhatar]

Hi!
Perhaps I'm wrong, but the sample output and my output are equal!

[brianfry713]

You're missing the !
http://ideone.com/QTMIa

[AhmadKhatar]

Thanks!
But your input needs another new line!

[brianfry713]

I don't think so. Try to make your code work either way.

[AhmadKhatar]

Thanks!
You were right! Newline should be between inputs not after each of them.

[vsha041]

Any one can get runtime error because input may be like

A1 13579;
B1 a-123;

Handle this i got accepted other wise i got runtime error.

There is no test case like this in the judge's input. Input format isn't tricky either. I use cin and cout to read/write input/output.

[moxlotus]

Getting WA on this problem.
Can someone provide me with some tricky corner case? or is there something abt the output format that i m missing here?
Totally can't figure out whats wrong with my code

AC

[brianfry713]

Next time post in the existing thread.

Input:

Code: Select all

A9 2;
B1 3;

A1 78;
B3 012345689;

A8 169;

A2 89;
B2 0127;

A2 7;

A2 012346789;

A1 2;
B1 169;

A3 125689;

A2 123456789;
B1 02456789;
C5 0124569;
D2 012345789;

A6 01345;
B2 01235689;


A7 01234678;
B3 15;
C1 3579;

A1 0123456789;

A2 029;
B1 12589;
C1 8;
D1 0149;

A3 1678;

A6 03678;

A1 038;
B1 69;

A: 02369;
B1 03456789;

A5 16789;
B1 024567;
C3 013678;

A4 0123456789;
B1 0134568;
C2 123479;

AC output:

Code: Select all

!
BBB____A__
!
BB______AA
!
AA________
_BA_______
_AA__A____
CAADCCCDBC
!
__________
!
A_________
ABA_D___C_
_A____AA__
!
A_____B___
!
!
AAAAB__C_C

[moxlotus]

Thanks Brian.
Didnt want to spawn a new thread but there is alrdy so many around i dunno which is a better one to append to. xD

[brianfry713]

I merged all of the "Help on the Problemset" threads about this problem into this one.