Discussion on Lovely Triplets Challenge

Sort 13 Discussions, By:

1 year ago+ 0 comments

Hey! I liked it!

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.

3 years ago+ 0 comments

what does he mean by undirected and length of edge ?

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:

the example in description is far away from real solution, don't waist time for analyzing it.
The problem should be splited in two cases, which slightly different in solutions: First one when Q>2 and Second when Q=2:
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)

5 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

Load more conversations