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.
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:
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/python3importmathfromfunctoolsimportreduceedges=[][P,Q]=list(map(int,input().split()))deffindFactors(forest,P):min=100tree=[0]*3forkinrange(1,30):forlinrange(1,30):forminrange(1,30):ifk*l*m==Pandk+l+m<min:tree=[k,l,m]min=k+l+mifsum(tree):forest.append(tree)returnforestdefcombinations(n):returnn*(n-1)*(n-2)//6defsplitTreesForTwo(P):forest=[]whileP>0:ifP<4:forest.append(3)P=P-1else:foriinrange(P,2,-1):ifcombinations(i)<=PandP-combinations(i)>=0:forest.append(i)break;P=P-combinations(i)returnforestdefsplitToTrees(P,memo={}):forest=[]reminder=0ifPinmemo:returnmemo[P]whilelen(forest)==0andreminder<=P/2:forest=findFactors(forest,P-reminder)iflen(forest)>0:breakelse:reminder+=1#memorization step1memo[P-reminder]=forestifreminder>0:forest+=splitToTrees(reminder,memo)#memorization step2memo[P]=forestreturnforestdefmakeRoot(Q,lastNodeNumber=0):ifQ%2==0:Nroot=(3*Q)//2-3 #number of nodes in rootforiinrange(1,Nroot+1):ifi<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 rootforiinrange(1,Nroot+1):ifi<4:edges.append((i+lastNodeNumber,(i+1)%3+1+lastNodeNumber))else:edges.append((i-3+lastNodeNumber,i+lastNodeNumber))defmakeLeafs(tree,Q,lastNodeNumber=0):ifQ%2==0:Nroot=(3*Q)//2-2 #number of nodes in rootlastNodeNumber=Nroot+lastNodeNumber#numberoflastnodeinforestelse:Nroot=(Q+1)*3//2-3 #number of nodes in rootlastNodeNumber=Nroot+lastNodeNumber#numberoflastnodeinforest#start nodes - nodes to wich leafs will be added to form full treestarNodes=[lastNodeNumber-2,lastNodeNumber-1,lastNodeNumber]foriinrange(0,3):for_inrange(1,tree[i]+1):edges.append((starNodes[i],lastNodeNumber+1))lastNodeNumber+=1returnlastNodeNumberdefsolve(P,Q):ifQ>2:ifQ%2==0:Nroot=(3*Q)//2-2 #number of nodes in rootEroot=(3*Q)//2-3 #number of edges in rootelse:Nroot=(Q+1)*3//2-3 #number of nodes in rootEroot=Nroot#numberofedgesinrootforest=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))fortreeinforest:makeRoot(Q,lastNodeNumber)lastNodeNumber=makeLeafs(tree,Q,lastNodeNumber)else:forest=splitTreesForTwo(P)numberOfTrees=len(forest)numberOfLeafs=sum(forest)rootNodeNumber=1edges.append((numberOfTrees+numberOfLeafs,numberOfLeafs))fortreeinforest:forleafinrange(1,tree+1):edges.append((rootNodeNumber,rootNodeNumber+leaf))rootNodeNumber+=tree+1foriteminedges:print(*item)solve(P,Q)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Lovely Triplets
You are viewing a single comment's thread. Return to all 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:
Let's consider case 1.1, for Example Q = 4, P=5:
Let's consider case 1.2, for Example Q = 5, P=3:
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:
Below is my solution passed all the cases, just to help you if you'll stuck: