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