Hi all,
Unfortunately, due to some personal reasons the editorials of following problems are delayed. They will be posted by end of this week tenatively
- KS1 - Done
- SYNBAC - Pending Approval
CHGORAM
Let’s consider the euler tour of the tree and build a merge sort tree over it. Let’s consider an arbitrary vertex x as a candidate for p2. Then with the help of the merge sort tree we can calculate for every adjacent vertex the number of vertices in its subtree that are less or greater than x in O(log^2 n). Let there be k adjacent vertices, a_1, …, a_k and the number of vertices with smaller index in the appropriate subtree be l_1, …, l_k, similarly the vertices with larger index be g_1, …, g_k. Then for example if we have the permutation p={1,2,3} or {3,2,1}, then we want to calculate \sum_{i!=j} l_i * g_j, this can easily be calculated in O(k) time in the following manner, let L=l_1+…+l_k and G=g_1+…+g_k, then the above sum is LG-\sum^{k}_{i=1} l_ig_i. There are 2 other cases which can be similarly examined. And because for this arbitrary x vertex we have calculated the answer in O(k log^2 n) then for the whole problem we have a O(n log^2 n) solution. We can reduce this to O(n log n) by applying fractional cascading. However we can also notice that the queries are offline thus a sorting method is feasible too (and much faster in practice), i.e let’s look only at queries like in an interval [l;r] we want to calculate the numbers which are larger than y (the case when we want to calculate the numbers which are smaller than y can similarly be solved). Then we put these queries and the indices of the vertices in one list and sort them by their index (for the queries the index is y and for the vertices its their index :P), and then just loop over them from the largest index to the smallest, and do a point increase in a fenwick tree at a vertex, and calculate the sum from l to r for a query.
CSTREE
We use generalized cayley’s formula (https://math.stackexchange.com/questions/2550064/proof-of-generalized-cayleys-formula) and inclusion/exclusion.
For inclusion/exclusion. We need to count the number of spanning trees that use at least t forbidden edges. We can split t = t_1+t_2+...+t_k, where t_i is number of forbidden edges we used in i-th copy of graph. We also need to take the size of the components into account, so if we use t_i edges in the i-th copy, there will be n-t_i components with some sizes s_{i,1},...,s_{i,n-t_i}. The number of spanning trees in total with this configuration is sum product$(s_{i,j}) * (kn)^(kn-t)$, over all valid ways to split the sizes of each component.
The second term is only dependent on the number of forbidden edges we use, so we can pull it out.
We can split the first term per component, so we only need to find these values for one tree, then we can use polynomial multiplication to get the values for k copies.
To compute sum product (s_{i,j}) for one tree, use the generalized matrix tree theorem. Consider a matrix M, with M_{i,i} = deg(i) and M_{i,j} = -1 if there is an edge and 0 otherwise. Fix some set A. If you delete the i-th row and column for every i in A, then the determinant of M will be the number of forests of the original graph with every node in A belonging to a separate component.
Consider the matrix M. If we add a variable x along the diagonal of M, then the determinant of M will be some polynomial in x. We claim that the coefficient of x^k is exactly what we need to compute. It sums over all ways to split some nodes into k different components. Forests are counted multiple times according to the product of their sizes, which is what we need.
So the solution will look something like this:
- Compute the determinant of matrix M + I * x to get a polynomial (easiest way can be to evaluate this at x=0,x=1,…,x=n-1, then do polynomial interpolation to get coefficients)
- Exponentiate this polynomial to k-th power (maybe need fft here).
- Take i-th coefficient and multiply by (-1)^(i) * (k*n)^(k*n-i)), and sum them up to get the final answer
TSEQ
We can build an HLD there. Then we can split every path into O(log(N))
paths. You can note that only values with A_i not equal to -1 matter.
So we can check whether these values satisfy the non-decreasing
condition. If no then the answer is 0.
Now for every A_i not equal to -1 let’s maintain the number of ways to
change -1 till the next A_i not equal to -1 on its heavy path(This can
be done easily with some binomial coefficients and if we store set of
A_i not equal to -1 on every heavy path) And store this values in
segment tree. For -1 these values should be equal to 1. Now roughly
speaking we can query product on the range in segment tree. And for
most left and rightest A_i on the path we can find the number of ways
to change values of -1 on it and on the previous heavy path by hand
again with some binomial coefficients.
Update : O(log(N))
Query : O(log^2(N))