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:

votes

Please Login in order to post a comment

  • hosamsultaan
    3 years ago+ 0 comments

    what does he mean by undirected and length of edge ?

    2|
    Permalink
  • Reshetnyak
    4 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
  • ayoub_elyalaoui
    5 years ago+ 0 comments

    Solution

    #!/usr/bin/env python3
    def choose(n, r):
        return n * (n-1) * (n-2) // (r * (r-1) * (r-2))
    def product(xs):
        y = 1
        for x in xs:
            y *= x
        return y
    def generate_primes(n):
        p = [True] * (n + 1)
        p[0] = False
        p[1] = False
        for i in range(n+1):
            if p[i]:
                yield i
                for j in range(2*i,n+1,i):
                    p[j] = False
    primes = list(generate_primes(5000))
    def factorize(n):
        qs = []
        for p in primes:
            if p*p > n:
                break
            while n % p == 0:
                qs.append(p)
                n //= p
        if n != 1:
            qs.append(n)
        return qs
    def core_size(q):
        return ((q - 1) // 2) * 3
    def select_factors(p, q, width, memo):
        if p in memo:
            return memo[p]
        qs = [p, 1, 1]
        qv = core_size(q) + sum(qs)
        for i in range(min(width, p)):
            ps = [1, 1, 1]
            for r in factorize(p - i):
                ps[ps.index(min(ps))] *= r
            pv = core_size(q) + sum(ps)
            if i:
                nps, npv = select_factors(p - product(ps), q, width=width, memo=memo)
                pv += npv
            if pv < qv:
                qs = ps
                qv = pv
        memo[p] = (tuple(qs), qv)
        return memo[p]
    def make_core(v, e, q):
        if q % 2 == 1:
            xs, v = [v, v+1, v+2], v+3
            for i in range(3):
                e.append((xs[i], xs[(i+1)%3]))
        else:
            xs, v = [v, v, v], v+1
        for i in range(3):
            for j in range(q//2 - 1):
                e.append((xs[i], v))
                xs[i] = v
                v += 1
        return xs, v
    def make_triplets(v, e, q, ps):
        xs, v = make_core(v, e, q)
        for i in range(3):
            for _ in range(ps[i]):
                e.append((xs[i], v))
                v += 1
        return v
    def make_coalesced_core(v, e, l):
        for i in range(l):
            e.append((v, v + i+1))
        v += l+1
        return v
    p, q = map(int,input().split())
    v = 0
    e = []
    if q == 2:
        while p:
            l = 3
            while choose(l+1,3) <= p:
                l += 1
            p -= choose(l,3)
            v = make_coalesced_core(v, e, l)
    else:
        while p:
            ps, _ = select_factors(p, q, width=500, memo={})
            v = make_triplets(v, e, q, ps)
            p -= product(ps)
    print(v, len(e))
    assert v <= 100
    for a, b in e:
        print(a+1, b+1)
    
    1|
    Permalink
  • natali20011993
    1 year ago+ 0 comments

    Hey! I liked it!

    0|
    Permalink
  • Akatoki
    4 years ago+ 0 comments

    I divided this problem into 2 cases: when Q is even and odd. And the code below is what I wrote just for the even cases. It worked correctly for the test case #0 where P=3 and Q=2; however, I received an X on the test case #16 where P=3505 and Q=2. My code should print one of the correct answers for the test #16 as well, but somehow I got a cross. Would anyone here have an idea why this is hapenning? I would appreciate your help.

    #!/bin/python3
    
    import sys
    
    def printTopRow(num):
        for i in range(num):
            print(i+1,i+2)
    
    def printLowerRows(P, Q, b):
        for i in range(P):
                for j in range(int(Q/2)):
                    if j == 0:
                        print(int(Q/2)+1+i*Q, b+1+i*int(Q/2))
                    else:
                        print(b+i*int(Q/2)+j, b+i*int(Q/2)+j+1)
    
    
    
    if __name__ == "__main__":
        P, Q = map(int, input().split())
    
        if Q % 2 == 0:
            """Case 1: Q is even"""    
            m = int((3/2)*P*Q)
            n = m+1
            biggest = P*Q+1
    
            print(n,m)
            printTopRow(biggest-1)
            printLowerRows(P,Q,biggest)
    
        else:
            """Case 2: Q is odd"""
            pass
    
    0|
    Permalink
Load more conversations

Need Help?


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