SRM 763 author notes

1.Loopsie Doopsie
The only digits that have a loop in them are (0,6,4,9,8).
We should not use any digit that does not contain any loop since if we included such a digit, we can always remove it to get a smaller number. Only 8 has 2 loops others have a single loop. To find the smallest number we should prioritize reducing the number of digits. So we use floor(K/2) times 8. If K is odd we need to use an additional digit. using 4 at the start will give us the smallest result. (If we include 0 instead, we will have to place it at the end which will result in a larger number).

2.Weird Triangle
We know that non-degenerate triangle inequality says:-
a+b>c
a+c>b
a+b>c
So,
If I choose vertices u,v and w.
And uv= A[u]+A[v], vw= A[v]+A[w], uw= A[u]+A[w]
So applying above,
uv + vw > uw
(A[u]+A[v])+(A[v]+A[w])>A[u]+A[w]
So A[v]>0
Similarly A[w]>0, A[u]>0
ans is (numberOfPositiveElements)C3

3.ET Sums
The process described finding the value of each node is nothing but performing the Euler tour on it. As a result, the values in the subtree of every node will form a contiguous range. Let mx(i) denote the maximum value in the subtree of node i which can be calculated using a simple dfs. In the node i, every value between i and mx(i) would be present. Now let us calculate the contribution of each node in the final sum. Node i will lie in the path from root to node of every node in it's subtree and it will be the depth(i)th node in each of those paths. Therefore, it's contribution will be:
cost[i]*(Sum{j=i to mx(i)} depth(i)^j), which forms a gp and can be calculated quickly using sum of gp formula.
The summation across all nodes will give us the required answer.
Time Complexity: O(NlogN)

4.Cut, cut, cut
We can deduce the following.
Let's say our line is L, and let's say it intersects with k previous lines.
We can say that the number of pieces gets incremented by k+1.

5.Root it right
Root the tree at 1. Find the following for each node using dfs:
cost[i] = cost of node i as described in the problem statement.
subcost[i] = sum of cost[j] across every node j which lies in the subtree of i.
sm[i] = sum of values nodes on the path from 1 to node i.
subsum[i]= sum of sm[j] across every node j which lies in the subtree of i.
ct[i]= number of nodes in the subtree of i.
Now if we root the tree at a child X of 1 instead, the difference in the sum of costs will be as follows:
A. For every node j in the subtree of X, node 1 will no longer lie on the paths and the coefficient of terms of cost will decrease by 1, effectively the new cost will be:
cost[j]=cost[j]-sm[j]-val[1]
The effective change in subcost will be:
subcost[i]=subcost[i]-subsum[i]-ct[i]*val[1]
B. For every node j outside the sub tree of X, node X will also lie on the paths and the coefficient of terms of cost will increase by 1, effectively the new cost will be:
cost[j]=cost[j]+sm[j]+val[X]
We can calculate the change similar to the previous step.
After calculation for total cost rooting the node in every possible way, we choose the minimum.
Time Complexity: O(N)


6.Product and product
We can find :
sum{for all possible combination(x1,x2..xn)}(product{i=1 to n}(A[i]+xi)) ---------(1)
and then divide it by (M+N-1)C(N-1).

Lets consider a polynomial,
P(x,i) = sum{i=0 to inf}((A[i]+i)*x^i)

We can see that (1) is a coefficient of x^m in product{i=1 to n}P(x,i)

If we try to compute this directly using ntt, the time complexity would by NMlogM

Lets see P(x,i):
P(x,i) = sum{i=0 to inf}(A[i]*x^i + i*x^i)
P(x,i) = (A[i]*sum{i=0 to inf}x^i) + (sum{i=0 to inf}i*x^i) ----------------(2)
Now sum{i=0 to inf}x^i is expansion of 1/(1-x)

And sum{i=0 to inf}i*x^i,
we know 1/(1-x) = 1+x+x^2...
Differentiating and multiplying by x,we get
x/(1-x)^2 = x+2x+3x^2...=sum{i=0 to inf}i*x^i

So resubstituting these in (2), we get
P(x,i) = (A[i]/(1-x))+(x/(1-x)^2)
P(x,i)=(x*(1-A[i])+A[i])/(1-x)^2

So now since the degree of the numerator is 1, we can multiply using divide and conquer and ntt in O(MlogN*logM)

Now we have something like this:

(1) = (polynomial of degree at most m)*(1-x)^(-2n)

We can expand (1-x)^-2n and then iterating the power of x in (1-x)^-2n we can calculate the coefficient of x^m.

Time Complexity: O(MlogNlogM)