11721 - Instant View of Big Bang

[gaurav2289]

I tried this problem a lot number of times and getting WA. But I am unable to figure out the mistake as my code is working for all the test data I generate.
Algorithm I have used is --
1. Reverse the direction of each edge.
2. Set distance of coming to each node to 0.
3. Perform Bellman Ford.
4. Check for negative Cycle.
5. When a negative cycle is detected perform DFS from that node and list all the vertices that are visited.
6. If no negative cycle is found, print 'impossible'.

Please Help !! My code is --

Code: Select all

Removed After AC.

[jbernadas]

@gaurav2289:

I think you are idea is correct when there is only one negative cycle. Try with:

Code: Select all

1000 9
10 11 -10
11 12 -10
12 10 10
998 999 -10
999 998 9
800 12 1000
750 999 1000
750 111 -1000
111 750 1000

The correct output is:

Code: Select all

Case 1: 10 11 12 111 750 800 998 999

@admins:

I think the test data is wrong. I had to try many times until I realized some things:

• The nodes indices are between 0 and N, inclusive, not N-1. I had to add an extra node to the graph to make it work.
• Also, when printing the answer, only nodes strictly lower than N should be printed, even when N belongs to a negative cycle.

If you (the admins) want my code I can mail it to you.

Kind Regards.

[gaurav2289]

@ jbernadas
My code is working for this input as well. You are right Test data is faulty. I only included nth node as well and printed only n-1 node and got AC.
Thanks for your help.
Would you like to share your approach for this problem?

[r2ro]

I've been trying this problem out as well, and I can't seem to get an Accepted verdict.

I only included nth node as well and printed only n-1 node and got AC.

What do you mean by printed only n-1 node? Shouldn't you print all n nodes?

NVM: I got Accepted. For some odd reason, I had to change this line in my code:

Code: Select all

for (i = 0;i <= N_Var;i++)
	for (j = 0;j < M_Var;j++)
                  // code logic

and

Code: Select all

while (array_size > 0)
{
	num = pop();
	if (num == N_Var)
		continue;
	if (flag)
		printf (" ");
	else
		flag = true;
	printf ("%d",num);
}

I see that there are some discrepancies, I am pretty sure that making the first change i <= N should not matter as we are only considering from 1 to N-1, but I think that there's something left out in the problem set description. Either that, or there's a mistake in the input.

[gaurav2289]

@r2ro
I mean the same as mentioned by jbernadas above--

* The nodes indices are between 0 and N, inclusive, not N-1. I had to add an extra node to the graph to make it work.
* Also, when printing the answer, only nodes strictly lower than N should be printed, even when N belongs to a negative cycle.

P.S. -- Would you share approach to crack this problem.

[jbernadas]

Would you like to share your approach for this problem?

@gaurav2289: My approach is like, extract the kernel DAG of the graph using Tarjan's algorithm. Then, run Bellmann-Ford for each strongly connected component (aka: SCC) and see if there is a negative cycle. If there is, then the cycle is reachable from each node in that SCC, by definition of SCC. Then, I did a simple DP over the kernel DAG to check which components with negative cycle can be reached from components without negative cycles. Finally sort and print the answer.

[r2ro]

My approach was rather similar to yours;

- Alter the order of each edges, and then perform Bellman-Ford to identify all nodes w/ negative cycles.
- Nodes w/ negative cycles are explored and extracted and traversed through in the graph
- All Nodes that have been traversed through are pushed into a queue.
- If the queue is empty, then it is impossible.
- Otherwise, sort the queue, and then dequeue each node one by one and print them.

I actually wondered how one would be able to get a submission < 0.100 seconds, but maybe it's because my queue implementation was not that optimized.

[baodog]

Actually the problem limits are too loose. It should disallow O(V^2) type of solutions. It should be O(V).

1) The better solution is first construct SCC (strongly connected components), as well as the DAG after SCC decomposition.

2) Perform bellman ford negative cycle detection on only one node for each SCC (since every node can reach every other node in SCC,
it suffices to check for negative cycle only one node in that component).

3) Now, in the remaining DAG (directed acyclic graph), simply use memorization DP + DFS. If you can reach a SCC with a
negative cycle from a SCC, then all nodes in that SCC should be included. Sort and print the answer. That's it.

This can get you below 100ms with a good SCC implementation. Since E is O(V), the total time is O(V).

[jbernadas]

Actually the problem limits are too loose. It should disallow O(V^2) type of solutions. It should be O(V).

1) The better solution is first construct SCC (strongly connected components), as well as the DAG after SCC decomposition.

2) Perform bellman ford negative cycle detection on only one node for each SCC (since every node can reach every other node in SCC,
it suffices to check for negative cycle only one node in that component).

3) Now, in the remaining DAG (directed acyclic graph), simply use memorization DP + DFS. If you can reach a SCC with a
negative cycle from a SCC, then all nodes in that SCC should be included. Sort and print the answer. That's it.

This can get you below 100ms with a good SCC implementation. Since E is O(V), the total time is O(V).

That is my solution (of course, you explained it better). I would like to hear from the admins that data is going to be fixed.

[Jan]

Yes there is a wrong test data. I am sorry. I will send them the new data.

@baodog: In the iiuc contest I used the easier version of the problem. Wanted to upload the O(E) version of the problem in uva. I was busy that time, so couldn't send them the updated one. Sorry again.

[suhendry]

Have the test data been fixed?

My algorithm for this problem is:
1. Detect all negative cycles using Bellman-Ford algorithm. I use dist[] = {0} as the initial distance for all nodes.
2. For any node that lies in negative cycle, I push it into a queue. Node b lies in negative cycle if edge a-b can update the dist cost (after n-1 iteration).
3. For any node in my queue, I bfs it in the reverse graph (ie. the flow/direction for each edge is reversed) to get nodes that can reach negative cycles.

Is there any flaw in my algorithm?

EDIT: nevermind, I found my bug: "Node b lies in negative cycle if edge a-b can update the dist cost (after n-1 iteration)" -> it's wrong!

[zobayer]

A few more test cases:

Code: Select all

8

7 7
0 1 100
1 2 50
2 3 20
3 4 10
4 3 -20
1 5 5
5 6 5

6 6
0 1 100
1 2 50
2 3 20
3 2 -30
1 4 10
4 5 20

7 8
0 1 10
1 2 -15
2 1 5
2 3 -15
3 4 -30
5 4 -52
4 5 -10
5 6 100

2 1
0 1 -100

4 3
0 1 10
1 2 20
0 2 -31
 
3 3
0 1 1000
1 2 15
2 1 -42
 
4 4
0 1 10
1 2 20
2 3 30
3 0 -60

100 0

Correct output:

Code: Select all

Case 1: 0 1 2 3 4
Case 2: 0 1 2 3
Case 3: 0 1 2 3 4 5
Case 4: impossible
Case 5: impossible
Case 6: 0 1 2
Case 7: impossible
Case 8: impossible

Not sure if these help...

[mrtempo]

In Step 2. Would you please explain how would you detect a negative cycle in a SCC in O(E) ?

Actually the problem limits are too loose. It should disallow O(V^2) type of solutions. It should be O(V).

1) The better solution is first construct SCC (strongly connected components), as well as the DAG after SCC decomposition.

2) Perform bellman ford negative cycle detection on only one node for each SCC (since every node can reach every other node in SCC,
it suffices to check for negative cycle only one node in that component).

3) Now, in the remaining DAG (directed acyclic graph), simply use memorization DP + DFS. If you can reach a SCC with a
negative cycle from a SCC, then all nodes in that SCC should be included. Sort and print the answer. That's it.

This can get you below 100ms with a good SCC implementation. Since E is O(V), the total time is O(V).