DEVBDAY - Editorial

Can you tell me for which test case my code gives WA…

Or Whether my logic is incorrect…

I have implemented Kosaraju algorithm for finding the strongly connected components and for finding the cost of each component…

And then doing dfs for each non visited component to get the cost of each path…

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

If your solution is not getting accepted, please check once on this case

3
6
2 3 1 1 2 3
-1 -1 -1 2 2 2
5
5 1 4 5 4 
-964684432 74513386 -390331583 309950241 202556218 
6
5 3 1 3 3 2
1 -10 3 -2 4 -5

Answer should be

3
512506459
8
2 Likes

@asvcracker007, your code fails for the case when there are two or more independent connected components.
for example,
when n=6,
fi array [2,1,4,3,6,5],
r array [1,1,1,1,1,1],
answer should be 6 by inviting all friends. your code gives 2.

can you tell on why does my code give NZEC ? :frowning:
http://www.codechef.com/viewsolution/7019338
I basically find every directed cycle and for each node in the cycle i run ufs(which is just a fancy name for dfs :P) .Also the above testcase is working correctly.

Could someone please help me in finding out why I am getting a TLE with this code? I think I have the complexity right and the above testcase runs in ideone correctly, in no time at all.
link - owYttZ - Online C++0x Compiler & Debugging Tool - Ideone.com

What is the formal proof for the claim that each component will have exactly one simple cycle ?

what format is the example input. I am having trouble understanding it.

@niting112 because if your path is having more than one cycle , then there must be a node having two outdegree else 2nd cycle cant be made , this is not the case in the question .
This can be understood by drawing it on paper . hope it helps.

1 Like

can’t it be done by longest path in a graph algorithm

The complexity of my code is O(N) but I’m still getting TLE, can someone help please?
http://www.codechef.com/viewsolution/7020592

It works on the sample cases and the test cases provided here.

I am getting correct answers for the sample cases and also for the test cases given here but the result is TLE , can someone help please?
http://www.codechef.com/viewsolution/7020896

@niting112 If a component has more than one cycle, then atleast one node must have 2 incoming edges, which is not possible. Why? Because each person can have at max ONE best friend. So incoming edges for every node are 1.

2 Likes

for some reason, if you ever use memset on your code you will automatically get TLE on this problem. So if you are having this verdict, avoid memset and see what happens.

How is the answer for

6
2 3 1 1 2 3
-1 -1 -1 2 2 2

3 ?, Which set of friends is he gonna invite ? Pls help…

Unfortunately, my WA code gives correct answer fot these cases!

I’m getting correct answers for these cases. The complexity is O(N) but I’m getting TLE.
Please help : CodeChef: Practical coding for everyone

Also check for this case

1
10
10 8 7 7 6 4 5 5 4 7
-3 11 9 -13 -16 1 10 -3 14 16

Correct answer is : 29

Most of the WA’s will fail on this case.

1 Like

same here.

Yes, the answer is 3, and you have to invite all of them (you only invite the inner loop so you can invite the other friends who actually give you positive values).

here is one that helped me get AC

1

9

6 6 6 1 7 7 9 1 5

-1 7 7 -1 -3 -3 8 -7 0

Answer:16