10305 - Ordering Tasks

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

Moderator: Board moderators

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

10305 - Ordering Tasks

Post by anupam » Mon Mar 17, 2003 8:45 am

first please check,,

Code: Select all

cut it off please don't mind..
it's a sol after some reply...
thanks to tomal bhai...
this is a simple code of topological sorting,,
but i get wa for several times..
i can't understand why?

then i tried a very easy algirithm..
just compute the in degree of graph nodes but again wa..
am i missing something??
please please help...
i have no way left..

the second code... is pasted here....
please don't mind, i pasted it after at least 10 trials..and getting wa....

Code: Select all

#include<stdio.h>
#define N 100
main()
{
	freopen("in.txt","r",stdin);
	int m,n,b[N],out[N],i,j,c,d,h,e[N],f[N],high,l,k,r[N],pr;
	while(1)
	{
		scanf("%d%d",&n,&m);
		pr=0;
		if(m==0 && n==0) break;
		for(i=0;i<n;i++) b[i]=out[i]=0,r[i]=i;
		for(i=0;i<m;i++)
		{
			scanf("%d%d",&c,&d);
			b[c-1]++;out[d-1]++;
		}
		for(i=0;i<n-1;i++)
		{
			h=i;
			for(j=i+1;j<n;j++)
				if(b[j]>b[h]) h=j;
			c=b[h];
			d=out[h];
			b[h]=b[i];
			out[h]=out[i];
			out[i]=d;
			b[i]=c;
			c=r[i];
			r[i]=r[h];
			r[h]=c;
		}
		high=0;
		for(i=0;i<n;i++) if(b[i]>high) high=b[i];
		for(;high>=0;high--)
		{
			l=0;
			for(j=0;j<n;j++) if(b[j]==high) e[l]=j,f[l++]=out[j];
			for(j=0;j<l-1;j++)
			{
				h=j;
				for(k=j+1;k<l;k++)
					if(out[e[k]]<out[e[h]]) h=k;
				k=e[j];
				e[j]=e[h];
				e[h]=k;
			}
			for(i=0;i<l;i++)
			{
				if(pr) printf(" ");
				else pr=1;
				printf("%d",e[i]+1);
			}
		}
		printf("\n");
	}
	return 0;
}
if any one helps me i will be greatfull.
pleases ...
thanks.....
:oops: :oops: :oops: :oops: :oops: :oops: :oops: :oops: :oops: [/b]
Last edited by anupam on Tue Mar 18, 2003 6:16 am, edited 1 time in total.
"Everything should be made simple, but not always simpler"

User avatar
kmhasan
Problemsetter
Posts: 107
Joined: Fri Oct 26, 2001 2:00 am
Location: Canada
Contact:

Post by kmhasan » Mon Mar 17, 2003 4:48 pm

The code for topological sorting should work. I did it almost the same way. The part which I get a bit confused is where you swap the elements of array a. It seems like your doing some sort of Selection Sort there. I'm not sure if that is correct.

If you had kept the nodes in a global stack when you do the DFS, then you could simply pop and print them after the DFS is done.

[cpp]
void dfs(int u)
{
int i;
time++;
c='g';
for(i=0;i<n;i++)
if(c=='w' && b==1)
dfs(i);
S[top++] = u; /* this is what I suggest */
}
[/cpp]

I hope it might help.

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Tue Mar 18, 2003 6:12 am

if i get the finishing time the sorting represent the finishing time..
as the stack represent..
is there any error(bhul) in my code without using the stack..
tomal bhai apni boss..
apnar ebarer help 100% kaj diyeche...
but i can't understand why coreman is wrong or i am wrong in this case...
ektu explain korben??
:P :P
"Everything should be made simple, but not always simpler"

jura
New poster
Posts: 4
Joined: Thu Jan 02, 2003 11:00 pm
Location: Croatia

10305 - ordering tasks

Post by jura » Fri Apr 25, 2003 5:54 pm

Do I have a wrong approach or what?
I dunno why i get WA.


program tasks;
var level:array[1..100] of byte;
nodes:array[1..6000,1..2] of byte;
m,n,i,j:integer;
gotovo,prva:boolean;

begin
while true do
begin
readln(n,m);
if (n=0) and (m=0) then halt;

for i:=1 to m do readln(nodes[i,1],nodes[i,2]);
fillchar(level,sizeof(level),1);
for i:=1 to n do
begin
gotovo:=true;
for j:=1 to m do
begin
if level[nodes[j,1]]=i then
begin
level[nodes[j,2]]:=i+1;
gotovo:=false;
end;
end;
if gotovo then break;
end;
prva:=true;
for i:=1 to n do
begin
gotovo:=true;
for j:=1 to n do
begin
if level[j]=i then
begin
if prva then
begin
write(j);
prva:=false;
end else write(' ',j);
gotovo:=false;
end;
end;
if gotovo then break;
end;
end;
end.

boatfish
New poster
Posts: 18
Joined: Thu May 08, 2003 11:46 am

10305 WA why?

Post by boatfish » Sat Jul 12, 2003 3:33 pm

I just use topological sort, but keep on WA, why??

[cpp]
#include<iostream>
#include<queue>
#include<memory.h>
#include<algorithm>
using namespace std;

struct src{
int no;
int f;
};

bool graph[101][101];
int pre[101],color[101],t;
src f_c[101];

void DFS_VISIT(int u,int n){
int j;
color=2;
for(j=1;j<=n;j++){
if(graph[j] && color[j]==1){
pre[j]=u;
DFS_VISIT(j,n);
}
}
color=3;
t++;
(f_c).f=t;
}

void DFS(int n){
int i;
memset(pre,-1,101);
memset(color,1,101);
t=0;
for(i=1;i<=n;i++)
if(color==1)
DFS_VISIT(i,n);
}

bool new_less(src a,src b){
return a.f<b.f;
}

void print_path(int n){
sort(f_c,f_c+n,new_less);
for(int i=1;i<=n;i++)
cout<<(f_c).no<<' ';
}

int main(){
int n,m,a,b,i;
for(i=1;i<=100;i++)
(f_c).no=i;

while(cin>>n>>m,n){
memset(graph,1,10201);
for(i=1;i<=m;i++){
cin>>a>>b;
graph[a]=false;
}
DFS(n);
print_path(n);
cout<<endl;
}
return 0;
}[/cpp][/cpp]

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Location: Bangladesh

Post by Noim » Tue Jul 15, 2003 5:05 pm

strange.

have you test your program for some input? your program does not work for many input.
it just prints the same output for all input.
__nOi.m....

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post by miras » Tue Sep 09, 2003 3:24 pm

don.t use BREAk
:D

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

10305

Post by miras » Tue Sep 09, 2003 3:26 pm

Elo if input is
5 4
1 2
2 3
1 3
1 5
0 0


can the noutput be
1 2 3 5 4 ?? :D

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Location: Bangladesh

Post by Noim » Sat Sep 13, 2003 7:39 pm

yes the output would be: 1 2 3 5 4
what's the reason you have menteioned that?
is there any problem??? or any disagree???
__nOi.m....

miras
Learning poster
Posts: 98
Joined: Sat Jun 14, 2003 1:45 pm

Post by miras » Wed Sep 17, 2003 12:20 pm

ello ther is no problem but i still got WA i don.y know what is wrong hear;



BTW theanks;

end;
end.
MIRAS :lol:

Noim
Learning poster
Posts: 88
Joined: Sun Oct 13, 2002 6:11 am
Location: Bangladesh

Post by Noim » Wed Sep 17, 2003 7:23 pm

Mr. Miras,

i have not helped you yet. so why did you thank me , sir??? :wink:

ok you can try for the input below ( this is made by one of my freinds who got AC though his program output wrong for this input .....hahaha...)

input:
5 2
3 2
5 3
output can be one of many :lol:

ok , i can ensure you it is very easy problem and there is no meaningless critical input for this problem. you have to just implement a TOPOLOGICAL sort algorithm which can be found from any of the books of algorithm. may be thissss time, you can solve it . please inform here if you manage to solve this problem.
bye
__nOi.m....

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

Post by mido » Sun Sep 28, 2003 6:33 pm

Why does this go capoot(WA) :
[cpp]
#include <iostream.h>

long i,e,v,dep[105],x,y,j;
bool used[105],mat[105][105],first,vis[105];

void check(int x)
{
vis[x]=true;
int i;
if (dep[x]>0)
for (i=1;i<=v;i++)
{
if (mat[x] && !used && !vis[x]) check(i);
}

cout<<x<<" ";
used[x]=true;
vis[x]=false;
}

void main()
{
while (cin>>v>>e && (v||e))
{
for (i=1;i<=v;i++)
{
dep=0;
for (j=1;j<=v;j++)
mat[j]=false;
}
while (e--)
{
cin>>x>>y;
dep[y]++;

mat[y][x]=true;
}

for (i=1;i<=v;i++)
{
used=vis=false;
}

for (i=1;i<=v;i++)
{
if (dep==0) {cout<<i<<" ";used=true;}
}

cout.flush();

for (i=1;i<=v;i++)
{
if (dep>0 && !used) {check(i);}
}

cout<<char(8);

cout.flush();
cout<<endl;
}
}
[/cpp]
Thanks...

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

Post by mido » Thu Oct 02, 2003 7:21 pm

Stupid error that I found...duh

Algoritmo
New poster
Posts: 32
Joined: Wed Oct 15, 2003 12:10 pm
Contact:

Post by Algoritmo » Tue Nov 25, 2003 8:23 am

mido wrote:Stupid error that I found...duh
Can I make sujestions ?

-=> You probably have noted that you should repeatedly print and check, not just print all then check all and quit. dep[] array is not beeing never decremented and I think you don't need so many arrays.
-=> In c++ we normally count from 0 to N-1 instead than from 1 to N. If you have an array of 105, they are numbered from 0 to 104.
-=> FORs with a single command dont need the brackets {}
-=> You dont need cout.flush() unless for test reasons maybe

mido
Learning poster
Posts: 78
Joined: Sun Jun 16, 2002 9:48 pm
Location: Cairo,Egypt

Post by mido » Tue Nov 25, 2003 4:18 pm

None of those, believe it or not...it's the kind of error that makes you bang your head against the wall....:)

Post Reply

Return to “Volume 103 (10300-10399)”