259 - Software Allocation

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

Moderator: Board moderators

K0stIa
New poster
Posts: 4
Joined: Thu Sep 23, 2010 10:20 pm

Re: Runtime Error

Post by K0stIa » Fri Sep 24, 2010 6:04 pm

helloneo wrote:
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
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: 259 - optimizing..

Post by helloneo » Mon Sep 27, 2010 11:31 pm

I PMed you..

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

AhmadKhatar
New poster
Posts: 28
Joined: Fri Mar 30, 2012 12:57 am

Re: 259 - optimizing..

Post by AhmadKhatar » Fri Jul 20, 2012 5:56 pm

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

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 259 - optimizing..

Post by brianfry713 » Sat Jul 21, 2012 12:54 am

Doesn't match the sample I/O.
Check input and AC output for thousands of problems on uDebug!

AhmadKhatar
New poster
Posts: 28
Joined: Fri Mar 30, 2012 12:57 am

Re: 259 - optimizing..

Post by AhmadKhatar » Sat Jul 21, 2012 5:18 am

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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 259 - optimizing..

Post by brianfry713 » Mon Jul 23, 2012 11:22 pm

You're missing the !
http://ideone.com/QTMIa
Check input and AC output for thousands of problems on uDebug!

AhmadKhatar
New poster
Posts: 28
Joined: Fri Mar 30, 2012 12:57 am

Re: 259 - optimizing..

Post by AhmadKhatar » Tue Jul 24, 2012 2:52 am

Thanks!
But your input needs another new line!

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 259 - optimizing..

Post by brianfry713 » Tue Jul 24, 2012 10:59 pm

I don't think so. Try to make your code work either way.
Check input and AC output for thousands of problems on uDebug!

AhmadKhatar
New poster
Posts: 28
Joined: Fri Mar 30, 2012 12:57 am

Re: 259 - optimizing..

Post by AhmadKhatar » Tue Jul 24, 2012 11:17 pm

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

vsha041
New poster
Posts: 35
Joined: Wed Feb 12, 2014 10:04 am

Re: 259 - optimizing..

Post by vsha041 » Mon Mar 31, 2014 9:02 am

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
New poster
Posts: 31
Joined: Sat Sep 17, 2011 6:47 am

259 WA

Post by moxlotus » Tue Aug 12, 2014 6:18 pm

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
Last edited by moxlotus on Fri Aug 15, 2014 11:34 am, edited 1 time in total.

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 259 - Software Allocation

Post by brianfry713 » Tue Aug 12, 2014 9:11 pm

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
Check input and AC output for thousands of problems on uDebug!

moxlotus
New poster
Posts: 31
Joined: Sat Sep 17, 2011 6:47 am

Re: 259 - Software Allocation

Post by moxlotus » Fri Aug 15, 2014 6:36 am

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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 259 - Software Allocation

Post by brianfry713 » Fri Aug 15, 2014 8:08 pm

I merged all of the "Help on the Problemset" threads about this problem into this one.
Check input and AC output for thousands of problems on uDebug!

Post Reply

Return to “Volume 2 (200-299)”