Lovely Triplets
Lovely Triplets
+ 0 comments what does he mean by undirected and length of edge ?
+ 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)
+ 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)
+ 0 comments Hey! I liked it!
+ 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
Sort 14 Discussions, By:
Please Login in order to post a comment