Moderator: Board moderators

Algoritmo
New poster
Posts: 32
Joined: Wed Oct 15, 2003 12:10 pm
Contact:
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 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
If this method is correct, than I must have one stupid error in my code too

aakash_mandhar
New poster
Posts: 38
Joined: Thu Dec 11, 2003 3:40 pm
Location: Bangalore
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
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).

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

### 10305

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

}

}

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

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?

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:
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
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
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:
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:
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:
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:
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
Thank you fellows, I got AC now!

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

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?

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
``1 3 4 7 12 11 10 9 8 6 5 2``