259 - Software Allocation

[jagadish]

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 ?

[fishbao]

It seems all right.But it is judged WA.
I NEED YOUR HELP!
[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!

[m_thimma]

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

[hummty]

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]

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..

[baodog]

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 ...  

[rio]

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

[Kallol]

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

[Jan]

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.

[Akter_Sust]

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]

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]

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.

[helloneo]

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]

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]

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