# Kundu and Tree

# Kundu and Tree

Tuxdude + 3 comments I went through the editorial and the initial 3-4 sentences makes good sense, but the part of calculating the sum over product of all possible unique triplet combinations and reducing it tothe 4 for loops each running in O(n) time, does not since it has not been talked about. Could some one explain this or at least point me to some resource which might ?

I'm sorry to sound annoying about the Editorial, but please single letter variable names like B, C, D, etc. ? Wouldn't meaningful variable names with some comments make reading the code much easier for everyone ? This is not the only editorial I'm seeing this in BTW, please HackerRank addressing this would benefit a lot of people.aadilsaifi71 + 0 comments If Array A = {2, 1 ,2} and k represent sum of product of all unique k elements combinations.

for k = 1, sum = 2 + 1 + 2

for k = 2, sum = 2(1 + 2) + (1 * 2)

for k = 3, sum = 2 * (1 * 2)

Hope you have seen a general sequence here and those loops are actually reducing array to this general sequence :)

prasoontrivedi + 0 comments The idea is like this: Suppose given n sets and needed to select 2 elements from them such that both don't belong to same set(Here we need to find 3 such elements but I'll show for 2 to give the idea). So say that the array A={5,2,3,4,10,7} stores the size of each set. # of sets=6 and A[0]=5 ie. we use 0-based indexing. Lets state the problem mathematically: We need sum of : i * j for all distinct pairs (i,j) where i and j belong to array A. You can do it in O(n * n) by 2 loops :

for(int i=0;i < A.length-1 ; i++){for (int j=i+1;j < A.length;j++) sum+= A[i][j];What if , instead of 2 loops , we create another array B of same size and store in B[i] the sum of all elements from A[i] to A[A.length-1].

Now we can write sum as:

for(int i=0;i < A.length-1; i++) sum+=(A[i] * B[i+1]);

We were multiplying and then summing ... by this way we sum first in one loop , then multiply in another loop!

airibo + 0 comments [deleted]

brokenglishy + 1 comment For some reason, I can only pass the first 4 test cases, and the rest just failed with wrong answers.

frank44 + 1 comment I had the same issue. Don't forget to mod your answer by 10^9+7 :)

kaynaat007 + 0 comments how exactly did you fix the MOD ?. I am passing first 5 cases. Rest are wrong answers.

whitakerch + 2 comments Are we supposed to assume that the input vertices will be consecutive? This is not specified in the description and makes a difference as to how the problem should be solved.

i.e. Is this a possible input:

1 2 r

3 4 b

2 3 rkiner_shah + 0 comments I also was wondering the same!! Anyone plz reply!! Problem setter???

dheerajHackerRank Admin + 1 comment I'm afraid not. Input vertices might not always be in ascending order. If such is the case, it will be clearly mentioned in the problem statement.

kiner_shah + 1 comment So vertices can have branches?? N if yes..just two branches or more???

dheerajHackerRank Admin + 1 comment Any number of branches. It is not necessarily a binary tree.

jason_goemaat + 1 comment But only one parent because it is a tree, right?

JonnyOThan + 0 comments implicitly, yes. If there were more than one parent then there would be more than N-1 edges.

yf2zhang + 0 comments The sample input is very lame. It should be more complex so that people can understand.

yzarubin + 0 comments The editorial code is painful to look at. This problem is solveable using union find + dfs. Simply merge all consecutive black edges with union find, and then create a graph out of the componenets. Perform a dfs, and for each node

**i**:- Calculate the # of possible triplets if
**i**is part of the triplet - Calculate the # of possible triplets if
**i**is not part of the triplet

Code: https://www.hackerrank.com/challenges/kundu-and-tree/submissions/code/50715137

- Calculate the # of possible triplets if

xialin + 2 comments It's a math problem. Disjoin Set is used to help you get the count easier.. Do not rely on the data structure itself to solve the problem though. Below is how I solved the problem:

1) if there is no black edge, how many triplets can you get from N nodes (i.e. get any 3 from N elements)

2) any triplet cannot contain more than 1 node that has black edge. on the other hand, in a set containing M black-edge-connected nodes, selecting 2 or 3 nodes and forming a triplet will break the rule and should be excluded (a deduction from total)

3) you should find all the black-edge-connected nodes sets.

sunstat + 1 comment why 2) is true? 1--2*

**3****4---5 1 2 5 is still a valid set? where --- black, *** red?zhukongfeng + 0 comments because 1 and 5 are in two different black-edge-connected trees.

rcashie + 1 comment This helped me solve the problem. Thank you! For those not familiar with the math, have a look at this:

https://www.khanacademy.org/math/precalculus/prob-comb/combinations/v/combination-formula

techo + 0 comments

kauarba + 0 comments Can you put all the explanations in editorial in english statesments along with the code. It's very hard and time consuming to read the codes and understand the concept only from code.

vipulvikram3499 + 0 comments 1.)Remove all red edges.

2.)count number of nodes in each trees formed after removing red edges.

3.) Let {T1,T2,â€¦,Tm} be the maximal subtrees with all black edges, and suppose these trees have t1,t2,â€¦,tm vertices, respectively. For each Ti, the number of bad triplets with all three vertices among V(Ti) is C(ti,3). The number of bad triplets having two vertices among V(Ti), and one vertex among the remaining vertices is C(ti,2)(Nâˆ’ti)

. All bad triplets are of one of these forms. So we have that the number of good triplets is:

answer=(C(N,3)âˆ’(for i=1 to m)âˆ‘(C(ti,3)+C(ti,2)(Nâˆ’ti)))%1000000007

hemant_dhanuka + 0 comments **Very Nice Editorial but it was little bit tricky to solve **

*Consider that size of these components are a1, a2, a3,.... , ak.

So we have to pick three vertices out of given k disconnected component which can be done in S number of ways*

look at it http://qr.ae/TUT2wh for O(n*3) similar to O(n)

Sort 36 Discussions, By:

Please Login in order to post a comment