11721 - Instant View of Big Bang

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

Moderator: Board moderators

Post Reply
gaurav2289
New poster
Posts: 10
Joined: Tue Jul 07, 2009 11:59 am
Location: Ithaca, NY

11721 - Instant View of Big Bang

Post by gaurav2289 » Mon Oct 26, 2009 10:53 pm

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.
Last edited by gaurav2289 on Tue Oct 27, 2009 2:21 pm, edited 1 time in total.

jbernadas
New poster
Posts: 16
Joined: Tue Apr 24, 2007 11:23 pm
Location: Caracas, Venezuela

Re: 11721 - "Instant View of Big Bang"

Post by jbernadas » Tue Oct 27, 2009 12:32 am

@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
New poster
Posts: 10
Joined: Tue Jul 07, 2009 11:59 am
Location: Ithaca, NY

Re: 11721 - "Instant View of Big Bang"

Post by gaurav2289 » Tue Oct 27, 2009 10:11 am

@ 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
New poster
Posts: 38
Joined: Thu Sep 25, 2008 9:26 am

Re: 11721 - "Instant View of Big Bang"

Post by r2ro » Tue Oct 27, 2009 12:16 pm

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
New poster
Posts: 10
Joined: Tue Jul 07, 2009 11:59 am
Location: Ithaca, NY

Re: 11721 - "Instant View of Big Bang"

Post by gaurav2289 » Tue Oct 27, 2009 2:20 pm

@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
New poster
Posts: 16
Joined: Tue Apr 24, 2007 11:23 pm
Location: Caracas, Venezuela

Re: 11721 - "Instant View of Big Bang"

Post by jbernadas » Tue Oct 27, 2009 7:23 pm

gaurav2289 wrote: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
New poster
Posts: 38
Joined: Thu Sep 25, 2008 9:26 am

Re: 11721 - "Instant View of Big Bang"

Post by r2ro » Wed Oct 28, 2009 12:57 am

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
Experienced poster
Posts: 202
Joined: Wed Jul 04, 2007 6:53 am

Re: 11721 - "Instant View of Big Bang"

Post by baodog » Wed Oct 28, 2009 5:00 am

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
New poster
Posts: 16
Joined: Tue Apr 24, 2007 11:23 pm
Location: Caracas, Venezuela

Re: 11721 - "Instant View of Big Bang"

Post by jbernadas » Wed Oct 28, 2009 5:07 am

baodog wrote: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
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Re: 11721 - "Instant View of Big Bang"

Post by Jan » Sat Nov 07, 2009 9:19 pm

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.
Ami ekhono shopno dekhi...
HomePage

suhendry
New poster
Posts: 14
Joined: Sat Aug 31, 2002 6:55 am

Re: 11721 - "Instant View of Big Bang"

Post by suhendry » Fri Jun 04, 2010 3:37 pm

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!
Suhendry Effendy

zobayer
Experienced poster
Posts: 110
Joined: Tue May 06, 2008 2:18 pm
Location: CSE-DU, Bangladesh
Contact:

Re: 11721 - Instant View of Big Bang

Post by zobayer » Thu Jun 09, 2011 5:38 pm

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...
You should not always say what you know, but you should always know what you say.

mrtempo
New poster
Posts: 1
Joined: Wed Sep 04, 2013 3:39 am

Re: 11721 - "Instant View of Big Bang"

Post by mrtempo » Wed Sep 04, 2013 4:08 am

In Step 2. Would you please explain how would you detect a negative cycle in a SCC in O(E) ?
baodog wrote: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).

Post Reply

Return to “Volume 117 (11700-11799)”