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.
  1. Prepare
  2. Algorithms
  3. Constructive Algorithms
  4. Lovely Triplets
  5. Discussions

Lovely Triplets

  • Reshetnyak
     + 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)