# 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 + 2 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!

malharjajoo + 0 comments @prasoontrivedi, I think you meant

for(int i=0;i < A.length-1 ; i++){for (int j=i+1;j < A.length;j++) sum+=

**A[i] * A[j];**since your array A is only 1-D ...

malharjajoo + 0 comments @prasoontrivedi, thanks for that explanation for the 2D case .. I was able to extend it to the 3-D case and implement the solution myself :)

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.

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

nubbel + 0 comments Here's my O(n) solution in Java. It works as follows:

- It constructs disjoint components consisting of vertices only connected by black edges using disjoint sets (i.e. Union-Find sets)
- It calculates the number of all possible triplets, i.e. binom(n, 3): "from n elements choose 3 without regarding the order"
- For each distinct component C_i subtract from the number of possible triplets:
- the number of triplets within the component, i.e. binom(n_i, 3) where n_i is the size of component C_i
- the number of triplets build from 2 vertices of the component and 1 other (not in the component), i.e. binom(n_i, 2) * (n - n_i)

- Print the result modulo 10^9 + 7

import java.io.*; import java.util.*; import java.text.*; import java.math.*; import java.util.regex.*; class DisjointSet { DisjointSet parent = this; int size = 1; DisjointSet findRoot() { if (parent != this) { // path compression parent = parent.findRoot(); } return parent; } void union(DisjointSet other) { if (other == this) return; DisjointSet root = findRoot(); DisjointSet otherRoot = other.findRoot(); if (otherRoot == root) return; // union by size if (root.size >= otherRoot.size) { otherRoot.parent = root; root.size += otherRoot.size; } else { root.parent = otherRoot; otherRoot.size += root.size; } } } public class Solution { final static long mod = 1_000_000_007; public static void main(String[] args) { Scanner scanner = new Scanner(System.in); int n = scanner.nextInt(); DisjointSet[] components = new DisjointSet[n + 1]; for (int i = 0; i < n - 1; i++) { int a = scanner.nextInt(); int b = scanner.nextInt(); char color = scanner.next().charAt(0); // ignore red edges if (color == 'r') continue; DisjointSet aComponent = createComponentIfNeeded(components, a); DisjointSet bComponent = createComponentIfNeeded(components, b); aComponent.union(bComponent); } // uniquify components Set<DisjointSet> uniqueComponents = new HashSet<>(); for (int i = 0; i < n; i++) { DisjointSet component = components[i]; if (component != null) { uniqueComponents.add(component.findRoot()); } } long validTriplets = choose3from(n); // all possible triplets for (DisjointSet component : uniqueComponents) { // subtract all triplets within the components validTriplets -= choose3from(component.size); // subtract all triplets build from 2 vertices of the components and 1 other vertex validTriplets -= choose2from(component.size) * (n - component.size); } // apply modulo for some reason beyond my imagination System.out.println(validTriplets % mod); } // lazily create a component static DisjointSet createComponentIfNeeded(DisjointSet[] components, int index) { if (components[index] == null) { components[index] = new DisjointSet(); } return components[index]; } // optimized calculation of binom(n, 3) static long choose3from(int n) { if (n < 3) return 0; // k = 3 // n! / ( k! (n-k)! ) = (n-k+1) * ... * n / k! = (n - 2) * ... * n / 6 long res = 1; for (int x = n - 2; x <= n; x++) { res *= x; } return res / 6; } // optimized calculation of binom(n, 2) static long choose2from(int n) { if (n < 2) return 0; // k = 2 // n! / (k! (n-k)!) = (n-k+1) * ... * n / k! = (n - 1) * ... * n / 2 long res = 1; for (int x = n - 1; x <= n; x++) { res *= x; } return res / 2; } }

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

kaushik_lele + 0 comments Editorial has very poor explanation. It should be more elaborated and the program there should follow better coding standards formatting, naming conventions and comments.

Otherwise editiroial is as cryptic as problem making it very less useful.

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.

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.

Sort 41 Discussions, By:

Please Login in order to post a comment