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

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

259 - Software Allocation

Post by jagadish » Fri Jul 02, 2004 8:47 pm

i got 0.5x sec for this one using dfs..cant see how people have got close to 0 sec ... all those who are above my rank have runnning times at least 10 times lesser than mine :(
can anyone of you give me some hints to speed up my code ?
if u can think of it .. u can do it in software.

fishbao
New poster
Posts: 4
Joined: Fri Jun 18, 2004 10:05 am

problem 259-WA

Post by fishbao » Thu Jul 08, 2004 5:36 am

It seems all right.But it is judged WA.
I NEED YOUR HELP! :o :o :o
[cpp]
#include <string.h>
#include <stdio.h>

char computer[10];
int oneline(char *s)
{
char app_name;
int app_num,i,n,j;
app_name=s[0];
app_num=s[1]-'0';
for (i=3,n=0;n<app_num;i++)
{
if(s!='\0')
{
if(!computer[s-'0'])
{
computer[s-'0']=app_name;
n++;
}
}
else
break;
}
if(n==app_num)
while(s!='\0')
{
computer[s-'0']='_';
i++;
}
else
return 0;
return 1;
}
void cases()
{
int i,j;
char *s;
s=new char[100];
while(gets(s))
{
if(!strcmp(s,""))
{
if(j==0)
printf ("!\n");
else
puts(computer);
}
else
{
i=strlen(s);
s[i-1]='\0';
j=oneline(s);


}
}

if(j==0)
printf ("!\n");
else
puts(computer);
}






int main()
{
cases();

return 1;
}[/cpp]
Thanks to everyone help me! :lol:

m_thimma
New poster
Posts: 3
Joined: Wed Feb 15, 2006 10:01 am
Location: iitg,india

Post by m_thimma » Thu May 11, 2006 7:03 am

i used the following alg:
0-9 indicates different computers
10-35 indicates applications
36 is source,37 destination
1)i constructed network with above conventions and the weights of edges between source and applications is the no of users bringing that application and all the othere edges weights are 1.
2)i used maxflow with bfs strategy...
whenever i find augmentation path...i saved the matching ...
it took around 0.033sec since it is only 38*38 size matrix only
Genius is a 2% inspiration and 98% perspiration

hummty
New poster
Posts: 1
Joined: Tue Nov 14, 2006 3:50 pm

problem 259 got TLE

Post by hummty » Wed Nov 15, 2006 8:01 am

i don't want to use any other approach.i want modification in this code.can anyone help me.



#include<iostream>
#include<string>
#include<fstream>
#include <stdio.h>
using namespace std;


int main()
{
/*app_no (total appointments)
comp_alloc (Allocated computers enter by the user)*/
int user,app_no,j,k,all_length,loc;
char app,input[15];


char computer[10]={' ',' ',' ',' ',' ',' ',' ',' ',' ',' '};

while(1)
{
gets(input);
all_length=strlen(input)-1;
while(all_length>0 )
{
app=input[0];
user=(input[1]-48);



app_no=user;

for( j=3;j<all_length;j++)
{
loc=(input[j]-48);

if(app_no>0 )
{
if(computer[loc]==' ')
{
computer[loc]=app;
app_no--;

}
}


else if(app_no==0)
{
computer[loc]='_';
}


}
gets(input);
all_length=strlen(input)-1;
}

for( k=0;k<10;k++)
{if(app_no>0)
{ cout<<"!";
break;
}
else
cout<<computer[k];


}
cout<<endl;
}

return 0;
}

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Wed Nov 15, 2006 6:09 pm

Dont open a new thread if there is one already. And try to post your code into the 'code' section (Check the editor). Otherwise your code can have emotions..
Ami ekhono shopno dekhi...
HomePage

baodog
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

WA

Post by baodog » Wed Aug 01, 2007 2:53 am

I keep getting WA ... I checked with many inputs, and I get
right answer. I'm using very simply bakctracking/brute force.
Are there any extremely tricky cases? Thanks.
Really appreciate it.

Here is my code for reference:

Code: Select all

ACC...  Thank you, Rio!
Can't believe I missed that ...
None of my test cases tested it ...  
Last edited by baodog on Fri Aug 03, 2007 11:14 pm, edited 1 time in total.

User avatar
rio
A great helper
Posts: 385
Joined: Thu Sep 21, 2006 5:01 pm
Location: Kyoto, Japan

Post by rio » Fri Aug 03, 2007 10:57 am

I found where to fix, but can't create the critical test cases.
And I'm not sure even such critical cases can actually occur.

Anyway, insert

Code: Select all

computer[n] = 0;
before

Code: Select all

return Solve(n+1);
----
RIo

User avatar
Kallol
Learning poster
Posts: 100
Joined: Sun Nov 13, 2005 8:56 am

Post by Kallol » Tue Aug 14, 2007 8:51 pm

well

I tried here bipartite matching .... my code ran well for all the input I gave . But i dont know why it is gettin RUNTIME ERROR(invalid memory reference) in UVA judge :(

can anyone help me ??

here is my code ..

Code: Select all

#include<cstdio>
#include<iostream>
#include<cstring>

using namespace std;


int a[300][300];
int task[300];
bool alpha[300];
char alloc[500];
bool seen[500];

bool bpm(int i)
{
	int j;
	for(j=0;j<10;j++)
		if(a[i][j] && alloc[j]=='_')
		{
			alloc[j]=i+'A';
			return true;
		}
	
	seen[i]=true;
	for(j=0;j<10;j++)if(a[i][j] && (alloc[j]-'A')!=i && !seen[j])
	{
		if(bpm(alloc[j]-'A'))
		{
			alloc[j]=i+'A';
			return true;
		}
	}
	return false;
}


int main(void)
{
	//freopen("259in.txt","r",stdin);
	char s[1000];
	int i,j,q;
	while(gets(s))
	{

		memset(a,0,sizeof(a));
		memset(alpha,false,sizeof(alpha));
		memset(alloc,'_',sizeof(alloc));
		
		if(strcmp(s,"")==0)
		{
			for(i=0;i<10;i++)
			{
				printf("%c",alloc[i]);
			}
			printf("\n");
			continue;
		}
		int p=s[0]-'A';
		task[p]=s[1]-'0';
		alpha[p]=true;
		for(i=3;s[i]!=';';i++)
		{
			q = s[i]-'0';
			a[p][q]=1;
		}

		while(1)
		{
			if(!gets(s))
				break;
			if(strcmp(s,"")==0)
				break;
			p=s[0]-'A';
			task[p]=s[1]-'0';
			alpha[p]=true;
			for(i=3;s[i]!=';';i++)
			{
				q=s[i]-'0';
				a[p][q]=1;
			}
		}

		int cnt=0;
		int flag=1;
		for(i=0;i<26;i++)if(alpha[i])
		{
			for(j=0;j<task[i];j++)
			{
				memset(seen,false,sizeof(seen));
				if(!bpm(i))
				{
					flag=0;
					break;
				}
			}
			if(!flag)
				break;
		}

		if(!flag)
		{
			printf("!\n");
		}
		else
		{
			for(i=0;i<10;i++)
			{
				printf("%c",alloc[i]);
			}
			printf("\n");
		}
	}
	return 0;
}

Syed Ishtiaque Ahmed Kallol
CSE,BUET
Bangladesh

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Aug 14, 2007 10:34 pm

I dont know why you are getting RTE. But I can tell you that your code is not fully correct. Try the case below:

Input:

Code: Select all

A1 13579;
B1 02468;
C1 01;
D1 02;
E1 1;
F1 3;
P1 4;
Q1 5;
Z1 7;
Output:

Code: Select all

CEDFPQBZ_A
Hope it helps.
Ami ekhono shopno dekhi...
HomePage

Akter_Sust
New poster
Posts: 4
Joined: Sat Sep 16, 2006 9:55 am

Runtime Error

Post by Akter_Sust » Thu Oct 18, 2007 8:23 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.

RenatoAlmeida
New poster
Posts: 3
Joined: Sun Jul 12, 2009 6:22 am

Re: 259 - optimizing..

Post by RenatoAlmeida » Mon Nov 09, 2009 2:18 am

EDIT: I think I found the error. I Will look this, thanks!
EDIT2: Sorry for post, I solved my problem. :)


I'm getting WA on this problem, can anyone help me with more elaborated test cases or look my code?

My graph:

0 - source
1 - sink
2...11 - computers
12+ - applications

There are a edge "SOURCE -> APPLICATION", for each application described, with capacity equal to the number of users for this application.
There are a edge "APPLICATION -> COMPUTER", with capacity 1, if the application can run on this computer.
There are ten edges "COMPUTER -> SINK", with capacity 1.

Then I run maxFlow algorithm, and if I can't match all users with your applications on the ten computers, print "!",

Else, I look on the flow matrix, for each edge APPLICATION -> COMPUTER, if the flow on this edge is 1, the application on this computer "COMPUTER" will be "APPLICATION".

My code works on the tests in this thread and others, I can't find the error.

Here the code:

Code: Select all

Accepted!
I was forget the flow on v->u , fnet on COMPUTER -> APPLICATION
Thanks.
PS: for the max flow, I use the ford fulkerson algorithm of shygypsy library.


Thanks!

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

Re: Runtime Error

Post by K0stIa » Fri Sep 24, 2010 9:42 am

Akter_Sust wrote: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.

hello, guys.

I tired to submit problems on this site. I think i solved this problem and have problems with I/O. Can anybody see on my code below ? If u can give me some advises how to write I/O for the problem on this site i'll be very thankful for u, coz i like problems on this site and dislike the format input data on it.

Code: Select all

#include <iostream>
#include <sstream>
using namespace std;

const int N = 38;
int C[N][N];
int F[N][N];

void clear()
{
	memset(C,0,sizeof(C));
	memset(F,0,sizeof(F));
}

const int s = 36;
const int t = 37;
const int inf = 1<<30;

int maxFlow()
{	
	int e[N], h[N];

	memset(e,0,sizeof(e));
	memset(h,0,sizeof(h));

	h[s] = N;

	for(int i = 0; i < N; ++i)
		if(i != s)
		{
			F[s][i] = C[s][i];
			F[i][s] = -F[s][i];
			e[i] = F[s][i];
		}
		
	for(int i = 0, j = 0, sz = 0, maxh[N]; ; )
	{
		if(!sz)
		{
			for(i=0; i < N; ++i)
				if(i != s && i != t && e[i])
				{
					if(!sz || h[i] > h[maxh[0]])
					{
						sz = 0;
						maxh[sz++] = i;
					}
					else if(h[i] == h[maxh[0]])
							maxh[sz++]=i;
				}								
		}

		if(!sz) break;

		while(sz > 0)
		{
			bool pushed = false;			
			i = maxh[sz-1];
			
			for(j=0; j < N; ++j)
				if(C[i][j] - F[i][j] > 0 && h[i]==h[j]+1)
				{
					pushed = true;
					int pf = min(C[i][j] - F[i][j], e[i]);
					F[i][j] += pf; F[j][i] = -F[i][j];
					e[i] -= pf; e[j] += pf;					
					if(e[i]==0) 
					{
						sz--;
						break;
					}
				}

			if(!pushed)
			{
				h[i] = inf;
				for(j=0; j < N; ++j)
					if(C[i][j]-F[i][j] > 0 && h[j]+1 < h[i])
						h[i] = h[j]+1;

				if(h[maxh[sz-1]] < h[i])
				{
					sz=0;
					break;
				}
			}				
		}
	}
	return e[t];
}

int main(int argv, char* arg[])
{
	#ifndef ONLINE_JUDGE
		freopen("in","r",stdin);		
	#endif	

	char buff[256];
	char comps[256];	
	int expected_flow = 0;

	clear();	
			
	while( 1 )
	{
		cin.getline( buff,256 );

		if(buff[0]=='\0')
		{
			bool cant = false;
			int flow = 0;
			
			if(expected_flow <= 10)
			{
				for(int i=0; i < 10; ++i)					
						C[26+i][t] = 1;

				flow = maxFlow();
			}
			else
				cant = true;

			if(expected_flow != flow || cant)
			{
				cout << '!' << endl;
			}
			else
			{
				for(int i = 26; i < s; ++i)
				{
					char c = '_';
					if(F[i][t] > 0)
					{
						for(int k = 0; k < 26; ++k)
						{
							if(F[k][i] > 0)
							{
								c = 'A' + k;
								break;
							}
						}
					}
					cout << c;
				}						
			}

			cout << endl;
			if(cin.eof()) return 0;						
			
			clear();
			expected_flow = 0;
			continue;
		}
		
		istringstream iss(buff);
		string ss;

		iss >> ss;

		if(ss[0] < 'A' || ss[0] > 'Z') continue;		

		int job =  ss[0] - 'A';				
		int sz=0;
		char ch = ' ';
		while(1)
		{
			iss >> ch;

			if(ch >= '0' && ch <= '9')
			{	
				comps[sz++] = ch-'0'+26;
			}
			else 
			{
				if(ch == ';')
				{
					for(int i=0;i<sz;++i) 						
							C[job][comps[i]] = 1;	
					
					C[s][job] += ss[1] - '0';
					expected_flow += ss[1] - '0';
				}
				
				break;
			}
		}		
	}			

	return 0;
}
I'm new one in this.
Last edited by K0stIa on Sat Sep 25, 2010 8:11 am, edited 4 times in total.

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: Runtime Error

Post by helloneo » Fri Sep 24, 2010 4:11 pm

K0stIa wrote: hello, guys.

I tired to submit problems on this site. I think i solved this problem and have problems with I/O. Can anybody see on my code below ? If u can give me some advises how to write I/O for the problem on this site i'll be very thankful for u, coz i like problems on this site and dislike the format input data on it.

I'm new one in this.

My code takes input like this..

Code: Select all

while (gets(buf)) {
    ...
    ...
    sscanf(buf, "%s%s", str1, str2);
    ...
    ...
    while (gets(buf)) {
        if (strlen(buf) <= 0)
            break;
        sscanf(buf, "%s%s", str1, str2);
        ...
        ...
    }
    ...
    ...
}
I don't know C++, so I can't tell you how to do this with C++ iostream

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

Re: Runtime Error

Post by K0stIa » Fri Sep 24, 2010 4:42 pm

What u can say about my approach ?
It's one of the usual approaches in such kind problems. We add source & sink nodes, first we connect with jobs, second with computers. Edges capacity from source to jobs nodes are equal to amount of jobs, capacities from computer node to sink are equal one. So, in such graph max flow goes throw the matching edges for jobs & computers as we want. If it's no hard for u, please see my code. there is simple implementation of preflow-push algorithm for max-flow problem.
I don't understand what's wrong with my code...

p.s. IO part looks like ur...

and I have one request more, can u give me some advices about IO data in this site, it seems to me there are many problems which are not difficult but have such kind of Input data which have the most general form which are not contradict with condition.

And what can u say about next test ?

A1 13579;
B1 a-123;

UVA toolkit returns "_A________"

does ur code provide this test ?

helloneo
Guru
Posts: 516
Joined: Mon Jul 04, 2005 6:30 am
Location: Seoul, Korea

Re: Runtime Error

Post by helloneo » Fri Sep 24, 2010 5:30 pm

K0stIa wrote:What u can say about my approach ?
It's one of the usual approaches in such kind problems. We add source & sink nodes, first we connect with jobs, second with computers. Edges capacity from source to jobs nodes are equal to amount of jobs, capacities from computer node to sink are equal one. So, in such graph max flow goes throw the matching edges for jobs & computers as we want. If it's no hard for u, please see my code. there is simple implementation of preflow-push algorithm for max-flow problem.
I don't understand what's wrong with my code...

p.s. IO part looks like ur...

and I have one request more, can u give me some advices about IO data in this site, it seems to me there are many problems which are not difficult but have such kind of Input data which have the most general form which are not contradict with condition.

And what can u say about next test ?


UVA toolkit returns "_A________"

does ur code provide this test ?


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 '!')

Post Reply

Return to “Volume 2 (200-299)”