We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Constructive Algorithms
  4. Lovely Triplets
  5. Discussions

Lovely Triplets

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 14 Discussions, By:

recency

Please Login in order to post a comment

  • thecodingsoluti2
    2 weeks ago+ 0 comments

    Here is problem solution - https://programs.programmingoneonone.com/2021/07/hackerrank-lovely-triplets-problem-solution.html

    0|
    Permalink
  • natali20011993
    2 years ago+ 0 comments

    Hey! I liked it!

    0|
    Permalink
  • bigjuicer1337
    2 years ago+ 1 comment

    Kids are indeed lovely. I hope that I will have a son and a daughter one day with my current girlfriend I met on SteamyLocals, since so far our relationship has been great. Online dating websites have really revolutionized dating in the Internet age, in my opinion. You can now find partners and friends without taking a step outside, which is great for anxious people.

    -1|
    Permalink
  • hosamsultaan
    4 years ago+ 0 comments

    what does he mean by undirected and length of edge ?

    2|
    Permalink
  • Reshetnyak
    5 years ago+ 0 comments

    After 2.5 days i finally solve it. Here is main tips for you to help.

    First of all i would notice following main features:

    1. the example in description is far away from real solution, don't waist time for analyzing it.
    2. The problem should be splited in two cases, which slightly different in solutions: First one when Q>2 and Second when Q=2:
    3. For your analysis First case also should be splited in two cases: 1.1 when Q is even and 1.2 when Q is odd.

    Let's consider case 1.1, for Example Q = 4, P=5:

    in this case the graph will be equal to one tree consisting of Root (looks like 3-ray star) and Leafs conected to each ray: (1,2) (1,3) (1,4) (2,5) (2,6) (2,7) (3,8) (4,9) then:

    Number of Nodes in root: Nroot = 3/2Q - 2

    Total number of Nodes: Ntotal = Nroot + P

    and P=k * l * m (wehre k,l,m - number of leafs on each ray of root)

    Let's consider case 1.2, for Example Q = 5, P=3:

    This case similar to first one but the Root is slightly different:

    Tree = (1,2) (2,3) (3,1) (1,4) (2,5) (3,6) (4,7) (4,8) (5,9) (6,10)

    Number of Nodes in root: Nroot = 3/2Q - 3

    Total number of Nodes: Ntotal = Nroot + P

    and *P=k * l * m* (wehre k,l,m - number of leafs on each ray of root)

    If P is high then graph become a forest consisting a several trees with similar roots but different number of leafs on each trees.

    And the main task of this Problem is to split P into trees with 3 factors, in a way that total number of nodes in graph were minimal and < 100, for example if P=129 we can split it in this way:

    P = k * l * m + x * y * z = 4* 4 * 8 + 1 * 1 * 1

    here we create 2 trees, but it could be more for different P's! To solve this task you need to build recursion function

    Now let's consider case when Q = 2:

    in this case the Trees of graph will look like just a stars (mean root is single node and all leafs connedted to it)

    for example P = 11 and Q = 2, then we need forest of two trees: (1,2) (1,3) (1,4) and (5,6) (5,7) (5,8) (5,9) (5,10)

    the number of different combinations Cr(n) of r numbers depending on number of leefs in tree n , from combinatorics:

    Cr(n) = n! / (r! * (n-r)!) in our case r = 3 (triplet!) then:

    C(n) = n * (n-1) * (n-2) / 6

    knowing C(n) formula we can solve our main task: Split P into trees with leafs x,y... : P = C(x) + C(y) + C(z) + ...

    Below is my solution passed all the cases, just to help you if you'll stuck:

    #!/bin/python3
    import math
    from functools import reduce
    
    edges = []
    [P,Q] = list(map(int,input().split()))
    
    def findFactors(forest, P): 
        min=100
        tree=[0]*3
        
        for k in range(1,30):
            for l in range(1,30):
                for m in range(1,30):
                    if k*l*m == P and k+l+m<min:
                        tree = [k,l,m]
                        min=k+l+m
        if sum(tree):
            forest.append(tree)
        return forest
    
    def combinations(n):
        return n*(n-1)*(n-2)//6
    
    def splitTreesForTwo(P):
        forest = []
    
        while P > 0: 
            if P<4:
                forest.append(3)
                P=P-1
            else:    
                for i in range(P,2,-1):
                    if combinations(i) <= P and P - combinations(i) >= 0:
                        forest.append(i)
                        break;
    
                P = P - combinations(i)
        return forest
    
    def splitToTrees(P,memo={}):
        forest=[]
        reminder = 0
        
        if P in memo:
            return memo[P]
        
        while len(forest) == 0 and reminder <= P/2:
            forest = findFactors(forest, P-reminder)
            if len(forest) > 0:
                break
            else:
                reminder +=1
        #memorization step1
        memo[P-reminder] = forest
        
        if reminder > 0:
            forest += splitToTrees(reminder, memo)
        #memorization step2
        memo[P] = forest
        
        return forest
    
    def makeRoot(Q,lastNodeNumber=0):
        if Q%2 == 0:
            Nroot = (3*Q)//2-3 #number of nodes in root
            for i in range(1,Nroot+1):
                if i < 4:
                    edges.append((1+lastNodeNumber,i+1+lastNodeNumber))
                else:
                    edges.append((i-2+lastNodeNumber,i+1+lastNodeNumber))
        else:
            Nroot = (Q+1)*3//2-3 #number of nodes in root
            for i in range(1,Nroot+1):
                if i < 4:
                    edges.append((i+lastNodeNumber,(i+1)%3+1+lastNodeNumber))
                else:
                    edges.append((i-3+lastNodeNumber,i+lastNodeNumber))
    
    def makeLeafs(tree, Q,lastNodeNumber=0):
        if Q%2 == 0:
            Nroot = (3*Q)//2-2 #number of nodes in root
            lastNodeNumber = Nroot + lastNodeNumber #number of last node in forest
        else:
            Nroot = (Q+1)*3//2-3 #number of nodes in root
            lastNodeNumber = Nroot + lastNodeNumber #number of last node in forest
        
        #start nodes - nodes to wich leafs will be added to form full tree
        starNodes = [lastNodeNumber-2,lastNodeNumber-1,lastNodeNumber]
        
        for i in range(0,3):
            for _ in range(1,tree[i]+1):
                edges.append((starNodes[i],lastNodeNumber+1))
                lastNodeNumber += 1
        
        return  lastNodeNumber
    
    
    def solve(P,Q):
        if Q>2:
            if Q%2 == 0:
                Nroot = (3*Q)//2-2 #number of nodes in root
                Eroot = (3*Q)//2-3 #number of edges in root
            else:
                Nroot = (Q+1)*3//2-3 #number of nodes in root
                Eroot= Nroot #number of edges in root
    
            forest = splitToTrees(P)
            numberOfTrees = len(forest)
            numberOfLeafs = sum(map(sum, forest))
            lastNodeNumber = 0
            
            #adding number of Nodes and Edges:
            edges.append((Nroot*numberOfTrees + numberOfLeafs, Eroot*numberOfTrees + numberOfLeafs))
    
            for tree in forest:
                makeRoot(Q,lastNodeNumber)
                lastNodeNumber = makeLeafs(tree,Q,lastNodeNumber)
    
        else: 
            forest = splitTreesForTwo(P)
            numberOfTrees = len(forest)
            numberOfLeafs = sum(forest)
            rootNodeNumber = 1
            
            edges.append((numberOfTrees + numberOfLeafs,numberOfLeafs))
            
            for tree in forest:
                for leaf in range(1,tree+1):
                    edges.append((rootNodeNumber,rootNodeNumber+leaf))
                
                rootNodeNumber += tree + 1
        
        for item in edges:
                print(*item)
    solve(P,Q)
    
    2|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy