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

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

Post by Algoritmo » Wed Nov 26, 2003 5:33 am

mido wrote:None of those, believe it or not...it's the kind of error that makes you bang your head against the wall....:)
Hmm now I understood your code. I had not noticed your check() function was recursive and that it did print values (I'm not used to iostream.h).
But I think your code could be much simple if it eliminated the "vis" and "dep" arrays. "vis" has exactly the same function as "used" and "dep" stores information that's already present on "mat". Dep can either be eliminated or changed for boolean.
Anyway, it looks like you got accepted, but I am still looking for MY stupid error :D Just to make sure my method works, I have explained it below. Can anyone see a problem in this procedure below ?
1 - For each input A B, store that task B depends on task A (task B can only be done if task A has been done before)
2 - Find a task N that has not been done and does not depend on no other task.
3 - Mark task N as done and print it.
4 - Search for any task P that depends on task N and cancel that dependencies
5 - If all tasks have been done, quit. Else, return to step 2.
If this method is correct, than I must have one stupid error in my code too :roll:

aakash_mandhar
New poster
Posts: 38
Joined: Thu Dec 11, 2003 3:40 pm
Location: Bangalore

Post by aakash_mandhar » Wed Jan 21, 2004 2:32 pm

Can anyone plzzz tell me what is wrong with this code.. Or atleast a case where it does not work....

[cpp]
# include<iostream.h>
# define MAX 101

int a[MAX][MAX],i,j,d[MAX],x,y,n,m,dc;

int main()
{
while(1)
{
cin>>n>>m;
if(n==0 && m==0) break;
dc=0;
for(i=1;i<=n;i++)
{
d=0;
for(j=1;j<=n;j++)
{
a[j]=0;
}
}
for(i=0;i<m;i++)
{
cin>>x>>y;
d[y]++;
a[y][x]++;
}

while(1)
{
for(i=1;i<=n;i++) if(d>0) break;
if(i==n+1) break;
for(i=1;i<=n;i++)
{
if(d==0)
{
dc++;
cout<<i;
if(dc!=n) cout<<" ";
else cout<<"\n";
d=-1;
for(j=1;j<=n;j++)
{
if(a[j]) {a[j]--;d[j]--;}
}
i=0;continue;
}

}
if(i==n) break;
}
}
/*
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
cout<<a[j]<<" ";
}
cout<<"\n";
}
*/
return 1;
}
[/cpp]
...I was born to code...

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

Post by mido » Wed Jan 21, 2004 8:53 pm

Algoritmo, your idea sounds fine. All I can say is to check boundary cases. I didn't try your code to be honest, but it looks okay. As for my code, it's true that the used array is redundant (but I was a naive coder...maybe I still am).

User avatar
Pavl0
New poster
Posts: 16
Joined: Sun Apr 18, 2004 2:57 pm

10305

Post by Pavl0 » Sun Apr 18, 2004 8:44 pm

meyby someone knoe why j get wa ??



#include<stdio.h>

int lk=0;

struct V_
{
int odl;
int nbr;
struct E_ *last;
struct E_ *fst;


}V[110];

struct E_
{


struct E_ *next;
struct V_ *wrz;



}E[10100];


void dfs(int v,int len)
{
struct E_ krw;
if(V[v].odl>len)return;
V[v].odl=len;

krw.next=0;
if(V[v].fst!=0)krw=(*V[v].fst);
else return;
while(1)
{
dfs((*krw.wrz).nbr,len+1);
if(krw.next==0)break;
krw=(*krw.next);

}


}






void addcon(int zk ,int dk)
{
if(V[zk].last==0)V[zk].fst=&E[lk];
else (*V[zk].last).next=&E[lk];
V[zk].last=&E[lk];

E[lk].wrz=&V[dk];

lk++;
}


main()
{
int now,nok,i,j,zk,dk;
scanf("%d %d",&now,&nok);

for(i=1;i!=(now+1);i++){V.odl=0; V.nbr=i; }

for(i=0;i!=nok;i++)
{
scanf("%d %d",&zk,&dk);
addcon(zk,dk);
}

for(i=1;i!=(now+1);i++)
{
dfs(i,0);
}

for(i=0;i!=now;i++)
{
for(j=1;j!=(now+1);j++)if(V[j].odl==i)printf("%d ",j);
}


}

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

10305- Artificial Intelligence or topological sort?

Post by serur » Thu Apr 27, 2006 8:31 am

I just got AC 10305-Ordering Tasks with Topological Sort,
but Steven Halim says on his webpage to solve it with Hill climbing Algorithm(Artificial inteliigence).
What is it?
Last edited by serur on Sat Apr 14, 2012 3:31 pm, edited 1 time in total.

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha » Thu Apr 27, 2006 10:11 am

Hill climbing is a search algorithm. It dosen't find the best solution in the all cases. And I think in ACM it is useless.
In Hill climbing you go always upward. just like real Hill Climbing. It always find the best solution if there is only a best answer. (there is no local maximum)

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Mon May 01, 2006 3:43 pm

Thank you, Moha.

Your knowledge on search algorithms may be of vital importance :) for me now that I'm attempting at 652- "Eight". My heuristics here h()=max(f(),g()), where f()- manhattan distance, g()- number of mislaid tiles. I use iterative deepening search and invariably get MLE. I haven't the slightest idea how those nice fellows in the ranklist did in 64kb memory :).
To got immediate access to visited()/not visited() I store a big array of (876543210/32) elements and use bitwise operators, also before every DFS(depth) I do backtrack to set all the numbers obtainable from permuatation of {0,1,...,8} : visited[()>>5]=0;
Well, when left alone I tend to do extremely silly things :) so it would be great if someone helps me.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Mon May 01, 2006 7:47 pm

Well , and there is something even more apalling - q10181-"15-Puzzle"! I think I must abandon the idea of storing visited states at all. So is there a strategy that doesn't need to know whether the state was generated before and procesed?
I read IDA* and implemented it, but MLE..

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha » Tue May 02, 2006 12:30 am

Hi serur,
About problem 652, I got TLE with a A* with manhatan huristic. I think i should rewite it with IDA*.
But I got Accepted 10181, with a same method, the point is in the problem 10181 you shouldn't save all the visited state! for the first problem the state space is 9! but in the second is 15!. 9! can be saved in a bit array effecient.

I think IDA* is good dut to this fact that, in these problems they don't want the best answer but they want a good(less than 50 movement) answer.

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue May 02, 2006 1:56 am

652 can be solved with simple BFS, the state space size is just 9!.

Moha
Experienced poster
Posts: 216
Joined: Tue Aug 31, 2004 1:02 am
Location: Tehran
Contact:

Post by Moha » Tue May 02, 2006 7:36 am

I did a same method but i got TLE. Would you please send me some testcase with your time for me, to compare my time with yours?

Thanks

mf
Guru
Posts: 1244
Joined: Mon Feb 28, 2005 4:51 am
Location: Zürich, Switzerland
Contact:

Post by mf » Tue May 02, 2006 9:36 am

I did a same method but i got TLE. Would you please send me some testcase with your time for me, to compare my time with yours?
My program answers each test case in almost a constant time. It initially does a single BFS from the solved state, that's the most time-consuming part. Then it prints answers by traversing BFS's arrays.

serur
A great helper
Posts: 251
Joined: Thu Feb 23, 2006 11:30 pm

Post by serur » Tue May 02, 2006 2:56 pm

Thank you fellows, I got AC now!

to mf-
Your idea + my implementation of it very likely underlay author's version :D - when I implemented it, my answer for sample input was the same as in the description :D .

1.xxx sec - not that bad, yeh?

Again, thank you Moha and mf !
Last edited by serur on Sat Apr 14, 2012 3:31 pm, edited 1 time in total.

asif_rahman0
Experienced poster
Posts: 209
Joined: Sun Jan 16, 2005 6:22 pm

10305....is it correct?

Post by asif_rahman0 » Fri May 05, 2006 5:41 am

i m getting WA!!!!

input :
12 7
1 3
3 4
3 8
4 12
4 7
7 11
7 10
0 0
output:
1 2 5 6 9 10 11 7 12 4 8 3

correct???

Darko
Guru
Posts: 580
Joined: Fri Nov 11, 2005 9:34 am
Location: Calgary, Canada

Post by Darko » Fri May 05, 2006 8:00 am

My AC gives

Code: Select all

1 3 4 7 12 11 10 9 8 6 5 2
In your example job 3 has to come before 4 and 8 but it's the last job in your solution.

Btw, can't you guys keep it in a single thread or something?

[EDIT: sorry if there is someone reading while I am editing, heh, it's been a while]

Post Reply

Return to “Volume 103 (10300-10399)”