You are not logged in. Please login at www.codechef.com to post your questions!

×

DEVBDAY - Editorial

6
1

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

This question is marked "community wiki".

asked 22 May '15, 20:44

balajiganapath's gravatar image

6★balajiganapath ♦♦
75542742
accept rate: 77%

edited 11 Feb '16, 17:35

admin's gravatar image

0★admin ♦♦
19.7k350498541

excellent question!

(03 Jun '15, 21:28) ironmandhruv4★

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
link

answered 25 May '15, 00:39

dpraveen's gravatar image

4★dpraveen ♦♦
2.5k52136170
accept rate: 20%

edited 25 May '15, 00:43

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

(25 May '15, 11:07) yash_155★

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) additya19983★
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) filmwalams5★

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) ironmandhruv4★

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

link

answered 25 May '15, 18:41

rachitjain's gravatar image

5★rachitjain
1307
accept rate: 0%

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

link

answered 25 May '15, 02:56

docodon's gravatar image

4★docodon
776
accept rate: 0%

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

link

answered 25 May '15, 00:21

asvcracker007's gravatar image

5★asvcracker007
-13159
accept rate: 0%

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

link

answered 25 May '15, 00:43

sigkill_'s gravatar image

5★sigkill_
1
accept rate: 0%

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.

link

answered 25 May '15, 00:59

sumeet_varma's gravatar image

7★sumeet_varma
1458
accept rate: 20%

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

link

answered 25 May '15, 01:10

shinjiikari's gravatar image

4★shinjiikari
15117
accept rate: 0%

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

link

answered 25 May '15, 01:48

niting112's gravatar image

2★niting112
12
accept rate: 0%

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

link

answered 25 May '15, 02:42

codedog29's gravatar image

3★codedog29
556
accept rate: 0%

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

link

answered 25 May '15, 09:08

terminated's gravatar image

3★terminated
435
accept rate: 0%

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.

link

answered 25 May '15, 11:20

additya1998's gravatar image

3★additya1998
942
accept rate: 15%

same here.

(27 May '15, 14:01) cristhianr3★

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

link

answered 25 May '15, 12:38

jyotipatel's gravatar image

2★jyotipatel
1
accept rate: 0%

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.

link

answered 28 May '15, 02:34

cristhianr's gravatar image

3★cristhianr
212
accept rate: 0%

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

link

answered 28 May '15, 07:14

sumitjha4321's gravatar image

3★sumitjha4321
813
accept rate: 0%

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

(29 May '15, 23:01) cristhianr3★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,482
×3,706
×74
×24
×5

question asked: 22 May '15, 20:44

question was seen: 5,384 times

last updated: 11 Feb '16, 17:35