Why does this algo not work for CHEFGRPH question FEB15 long challenge?

CHEFGRPH

This is the logic I used:

while taking input of the edges, if the newly added edge belongs to adjacent layers, I discard it.

I sort the edges with increasing destination layers and if the destination layers are same, sort it by vertex.

I maintain a cnt[] such that cnt[i]=dp[i][0]+…+dp[i][m-1] for all i

**k=1;
for(i=1;i<=n;i++){
   for(j=0;j<=m-1;j++){
       dp[i][j]=cnt[i-1];
       while(k<=sizeof edge array && i==destination layer && j==destination vertex)
           dp[i][j]=dp[i][j]+dp[source layer][source vertex];
       cnt[i]=cnt[i]+dp[i][j];
   }
}**

Here is the link to my solution. Any help is appreciated. Also it would help if I could get the test cases for which my code gives WA.

http://www.codechef.com/viewsolution/6325679

“Two paths are considered different if there is, at least, one edge which belongs to exactly one path. However, they are allowed to traverse the same set of vertices.”

You don’t discard edges between adjacent layers. You can have duplicate edges. Two edges from A to B mean 2 paths. Not sure about the rest of your code.

1 Like

But there is already an edge between all the vertices of adjacent layers. So no new edge is created. And “two edges from A to B mean two different paths”. How? Aren’t they same? How would one distinguish between the two paths?

Two paths are considered different if there is, at least, one edge which belongs to exactly one path. However, they are allowed to traverse the same set of vertices. In that case, there should be a multiple edge in the graph. It is also possible if some edge added by Chef connects two adjacent layers.