Discussion on Lovely Triplets Challenge

Sort 14 Discussions, By:

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

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 year ago+ 0 comments

Hey! I liked it!

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

Load more conversations