DEVBDAY - Editorial

PROBLEM LINK:

Practice
Contest

Author: Praveen Dhinwa
Tester: Utkarsh Lath
Editorialist: Balajiganapathi Senthilnathan
Russian Translator: Sergey Kulik
Mandarian Translator: Gedi Zheng

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 EXPLANATION

Build 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

11
2 0
3 0
2 0
3 0
6 0
8 0
6 0
7 0
6 0
5 0
5 0

Graph for above test case

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
Now, how can we find the cycle corresponding to a single connected component? First note that, we just have to find a single vertex lying in the cycle, then we will go from i to f_i and so on and thus we will find the entire cycle.

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:

Author’s solution
Tester’s solution

6 Likes

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 - http://ideone.com/owYttZ

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

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 : http://www.codechef.com/viewsolution/7020592

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

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.

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…

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).

//