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.
O(N) time O(1) space solution that passes all test cases:
#include<iostream>#include<ios>constintmod=1000000007;intadd(inta,intb){returnstatic_cast<int>((0L+a+b)%mod);}intmul(inta,intb){returnstatic_cast<int>((1L*a*b)%mod);}intmain(){std::ios_base::sync_with_stdio(false);intn=0;std::cin>>n;inta=0,b=0,c=0,d=0,m=1;for(inti=0;i<n;++i){intbp=b,cp=c,dp=d,mp=m;std::cin>>a;m=add(2,mul(4,mp));d=add(3*a,mul(2,dp));b=mul(mp,add(8*a,mul(3,dp)));intbterm[]={mul(4,bp),3*a,mul(2,dp)};for(intterm:bterm)b=add(b,term);c=mul(mul(12,mp),add(a,bp));intcterm[]={a,mul(4,cp),mul(8,bp),mul(16*a,mul(mp,mp))};for(intterm:cterm)c=add(c,term);}std::cout<<c;}/*First, lets compute some auxiliary quantities. Define M[i] as the number of nodes after the i-th iteration. We then haveM[0] = 6M[i] = 4 M[i-1] + 2Also, define D[i] as the length of the longest path after the i-th iteration, e.g. that between one corner and the other. We then haveD[0] = 3 A[0]D[i] = 3 A[i] + 2 D[i-1]Also, define B[i] as the sum of paths ending at the southeast corner (we can pick any corner of course, but to be clear and definitely, let's pick the southeast one). This is slightly tricky to compute, so let's draw a picture:W X| |g--h| |Y ZSuppose this is the tree after the i-th iteration, so that the edges here have length A[i], while g and h are nodes, and W, X, Y, and Z are all equivalent, e.g. the tree after the (i-1)th iteration. We use different letters for convenience in referring to them.We want to compute B[i], which is the sum of all paths that end at the bottom right, e.g. southeast corner of Z. Let's look at the picture and list all contributions:- M[i-1] - 1 paths originating from within Z = B[i-1]- the path starting from node h = A[i] + D[i-1]- the path starting from g = 2 A[i] + D[i-1]- M[i-1] paths starting from within X: = B[i-1] + M[i-1] * (2 A[i] + D[i-1])- 2 M[i-1] paths starting from within W or Y = 2 * (B[i-1] + M[i-1] * (3 A[i] + D[i-1]))Summing all these up, we haveB[i] = 4 B[i-1] + 3 A[i] + 2 D[i-1] + M[i-1] * (8 A[i] + 3 D[i-1])Finally, let's compute the value of C[i], e.g. the sum of all the pairwise paths after the i-th iteration. For convenience, let's repeat the same picture again:W X| |g--h| |Y Z- 1 path from g to h = A[i]- paths within W, within Y, within X, or within Z = 4 C[i-1]- paths from g to W, g to Y, h to X, or h to Z: = 4 (B[i-1] + A[i] * M[i-1])- paths from g to X, g to Z, h to W, or h to Y: = 4 (B[i-1] + 2 A[i] * M[i-1])- 2 paths from W to Y or X to Z: = 4 M[i-1] B[i-1] + 4 A[i] M[i-1]^2- 4 paths from W to Z or W to X or Y to Z or Y to X = 8 M[i-1] B[i-1] + 12 A[i] M[i-1]^2The last two are non obvious and merit explanation: letB[i-1] = sum p_k where p_k is the length of a path ending at a corner. A path from W to Y, where path k is chosen in W and path k' is chosen in Y, has distance = p_k + p_k' + 2 A[i-1]Take this quantity and perform a double sum over k and k'. The sum of p_k is given by M[i-1] B[i-1], and the sum of A[i-1] is given by M[i-1]^2 A[i-1].Hence, taking every item above and summing, we end up withC[i] = A[i] + 4 C[i-1] + 8 B[i-1] + 12 A[i] M[i-1] + 12 M[i-1] B[i-1] + 16 A[i] M[i-1]^2To obtain C[0], we note that C[-1] = 0, B[-1] = 0, and M[-1] = 1, so we haveC[0] = 29 A[0] */
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
HackerRank City
You are viewing a single comment's thread. Return to all comments →
O(N) time O(1) space solution that passes all test cases: