PROBLEM LINK:Author: Praveen Dhinwa DIFFICULTY:Easy PREREQUISITES:Basic Graph PROBLEM:For a birthday party, $n$ persons can be invited. The $i$th person gives Rs. $r_i$ (can be negative too, in case, you have to give that person $r_i$ rupees) as gift but requires that $f_i$ th person must also be present. What is the maximum amount of money that can be earned from the gifts. SHORT EXPLANATIONBuild a graph with $n$ nodes. There is an edge from $f_i$ to $i$ for all $i$. Note that this graph only consists of a number of components each having a simple cycle with possibly a few simple paths going out from it. For each component, we sum the values of all gifts in the cycle and do a dfs away from the cycle. For each path from the cycle, if the sum of values is positive, we add the value to the total value of the component. If the total value of the component is positive then we can add them to our answer otherwise we won't invite anyone from this component. EXPLANATION:Consider a graph with $n$ nodes corresponding to the $n$ persons. We add a directed edge from $f_i$ to $i$. What this means is that, if there is an edge from $a$ to $b$, then we have to invite person $a$ if we want to invite person $b$. Also, if we have invited a person $x$, then we can potentially invite all those nodes which have an incoming edge from $x$. Note that in this graph, each node has exactly one incoming edge. An example graph is shown below for input
If we draw such a graph for a few examples, we will find a pattern in the graph: the graph is made up of a number of (weakly connected) components each of which has exactly one simple cycle and possibly few paths going out from the cycle. Let us formally prove this observation. Suppose there is a component which does not have any cycle, then there must be a node which does not have any incoming edge  a contradiction. To proceed we observe that inviting a person in one component does not affect our choices in another component. Thus, we can calculate the maximum value we can get for each of the components one by one and sum them up. Let us see how we can solve for a particular component. First note that if we are to invite anyone from this component then we have to invite everyone from the cycle. So, we sum the values of all nodes in the cycle. We can now consider this cycle as a single node having this value. So, now we have to determine the maximum value we can get. Here is the important observation: if for a node $x$, we have invited some people who require node $x$ to be invited directly or indirectly, then the sum of the values of these people have to be non negative. Because otherwise we can exclude these people from the party and have a better total amount. This gives us an idea for the algorithm: for each node $x$, we solve recursively for each of its children (i.e nodes to which there is an outgoing edge from x). We invite a children only if we can get a positive value after inviting it. Finally, we sum up all such values from the children and add the node's own value to this sum. If this total value is positive then we can return it else it will be better to not invite $x$ or anyone who depends on $x$, so we return 0. For each component, we call the above procedure starting from the cycle node and add the answer we got for all the components to get the total gift amount. Implementation Notes So, for finding a single vertex lying in the cycle, let us construct a graph $G$ of $n$ nodes where edges are from $f_i$ to $i$. Now, pick any vertex in the component and keep taking the only outward edge in the graph. Finally, in the end, you will reach one vertex which surely lies in the cycle. Time Complexity:$O(n)$ AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 22 May '15, 20:44

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 answered 25 May '15, 00:39
Unfortunately, my WA code gives correct answer fot these cases!
(25 May '15, 11:07)
I'm getting correct answers for these cases. The complexity is O(N) but I'm getting TLE. Please help : http://www.codechef.com/viewsolution/7020592
(25 May '15, 11:19)
1
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.
(25 May '15, 19:29)
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
(03 Jun '15, 21:27)

@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. answered 25 May '15, 18:41

@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. answered 25 May '15, 02:56

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... answered 25 May '15, 00:21

@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. answered 25 May '15, 00:43

can you tell on why does my code give NZEC ? :( 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. answered 25 May '15, 00:59

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  http://ideone.com/owYttZ answered 25 May '15, 01:10

What is the formal proof for the claim that each component will have exactly one simple cycle ? answered 25 May '15, 01:48

what format is the example input. I am having trouble understanding it. answered 25 May '15, 02:42

can't it be done by longest path in a graph algorithm answered 25 May '15, 09:08

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. answered 25 May '15, 11:20

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 answered 25 May '15, 12:38

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. answered 28 May '15, 02:34

excellent question!