PROBLEM LINK:Author: Hanlin Ren DIFFICULTY:Hard PREREQUISITES:Divide and conquer, sweep line/segment tree PROBLEM:$G$ is a directed acyclic graph with $N$ vertices numbered from $1$ to $N$. There are $3$ classes of edges in $G$:
For any pair of vertices $s < t$, let $d(s, t)$ be the length of the shortest path from $s$ to $t$ in $G$. The task is to compute the sum of $d(s, t)$ for every $1 \leq s \lt t \leq N$. QUICK EXPLANATION:Use divide and conquer to remove $3$ central nodes, which disconnects the graph, solve the problem recursively into smaller graphs and combine the results into the final result. EXPLANATION:First of all, notice that the graph $G$ is a directed acyclic graph and has $O(N)$ edges with a very small constant. Subtask 1In the first subtask, we have $N \leq 10^3$ and sum of $N$ over all test cases not greater than $10^4$. This allows the most straightforward method of iterating over all vertices, and for a fixed vertex $i$, compute the sum of distances from $i$ to all other vertices $j > i$. This can be easily done in $O(N)$ time for a fixed vertex $i$ because the graph is a directed acyclic graph (see here for more details). In our case, it's even easier because the topologic order of $G$ is just $1, 2, \ldots, N$. Subtask 2In the second subtask, we know that there is a specific relation between weight of edges in all classes: $b_i = a_i + a_{i+1}$ If we take a closer look at above equations, we can notice that if $P$ is the shortest path from $i$ to $j>i$, and $P$ uses at least one edge of the second or the third class, then there exists another path $P'$ of the same length that $P$, such that $P'$ use only edges from the first class. This is true because any edge of the second class in $P$ can be replaced by two consecutive edges of the first class without changing the length of the path. Similarly, each edge of the third class in $P$ can be replaced by three consecutive edges of the first class without changing the length of the path. Thus, we can reduce the graph to a path graph where vertices $i$ and $i+1$ are connected by an edge with weight $a_i$ and there are no other edges in the graph. Moreover, between any two vertices $i < j$ there is now exactly one path. How to solve this simpler problem on the path graph? Well, it's pretty easy. An Edge $(i,i+1)$ for $i=1,2, \ldots, N1$ is taken into the final result $i \cdot (Ni)$ times because it is a part of that many shortest paths connecting vertices with indices $x \leq i$ with vertices with indices $y \geq i+1$. Subtask 3In the third subtask, we also know something specific about relation of weight of edges from the first and the third class: $c_i = a_i + a_{i+1} + a_{i+2}$ Using a similar reasoning as in the solution for the second subtask, we can reduce the input graph to a graph with edges only from the first and the second class. The solution for such a graph is the same as the solution for the third subtask, except the fact that one crucial step is easier to perform. Please read the description of the intended solution below to get the overall idea, and the distinction between these two solutions it also pointed out there. Subtask 4In the last subtask, we have the original constraints. The idea here is to use divide and conquer approach in order. Let's assume that we are solving the problem for an induced graph $G$ with vertices from range $[L, R]$ only. Clearly, the final result will be the solution for a graph with vertices in a range $[1, N]$. Now, the crucial observation comes: Let $m$ be some vertex such that $L < m < R$. Then, if we remove vertices $m1, m$ and $m+1$ from $G$, then we get two disconnected graphs $G_L$ and $G_R$ denoted by vertices in ranges respectively $[L, m2]$ and $[m+2, R]$. Thus, we can solve the problem recursively for both of them, add subresults computed for these subproblems, and the only remaining thing to do is to compute:
where $f(l, r, m)$ is the sum of all shortest paths from vertices with numbers smaller than $m$ to vertices with numbers larger than $m$, while $g(l, r, m)$ is the sum of all shortest paths to vertices $m1$ and $m$ and from vertices $m$ and $m+1$. The result for graph $G$ denoted by $[L, R]$ is then the sum of subresults for graphs $G_1$ and $G_2$ plus $f(l,r, m)$ plus $g(l,r,m)$. One more thing before we take a look at how to compute values of $f$ and $g$. Notice that as often in divide and conquer approaches, we want to divide the problem into as equal (in terms of size) subproblems as we can. Here, picking $m = (L+R)/2$ does the job because it reduces the size of the problem by a factor of $2$ every time. Moreover, when the size of a subproblem is small enough, so $RL+1 < C$, where $C$ is some constant, we can solve the problem with a quadratic solution described as the solution to the first subtask. This is a common technique used to speed up a solution in practice. Now, how to compute values of $f$ and $g$ defined above? Let's start with $g$ because it's easier. Notice, that $g$ is just a sum of three different sums. Each of them is a sum of the shortest paths to or from a fixed vertex, so a single such sum can be computed easily in $O(N)$ time by solving a standard shortest path problem in a DAG. Now the harder part, computing $f$. Let's consider two vertices $i < m$ and $j > m$. Then, $d(i, j)$ is the smallest of the following $3$ values: $d_1(i, j) := d(i, m1) + d(m1, j)$ Thus, we are interested, for all $i < m$ and $j > m$, how many times $d(i, m1)$ contributes to the final result, so how many times path $d(i, m1)$ is a part a a shortest path in all shortest paths counted in $f(l, r, m)$. Similarly, we want to count the same for $d(m1, j)$, $d(i, m)$, $d(m, j)$, $d(i, m+1)$, and $d(m+1, j)$. We are going to show how to do it only for $d(i, m1)$, because other cases are very similar. Now, we are interested in how many times $d(i, m1)$ is counted into $f(l,r,m)$, which is equal to the number of times $d_1(i, j)$ is smaller than $d_2(i,j)$ and also is smaller than $d_3(i,j)$. If any two paths, for example $d_1(i, j)$ and $d_2(i, j)$ are equal, we say that the one with smaller subscript is smaller, so $d_1(i,j)$ is smaller in this case. In other words, for a fixed node $i$, we are interested in number of $j$, such that $m < j \leq r$, and both below equations are fullfilled: $d(i, m1) + d(m1, j) \leq d(i, m) + d(m, j)$ above equations can be rewriten as: $d(m1, j)  d(m,j) \leq d(i, m)  d(i, m1)$ Now, if we let: $x_0 = d(i,m)  d(i,m1)$ and $x_j = d(m1,j)  d(m,j)$ Then we are interested in the number of points $(x_j, y_j)$ in $2d$ plane, such that $x_j \leq x_0$ and $y_j \leq y_0$. This last problem can be solved with for example a sweep line algorithm, sweeping through all $O(RL)$ points in sorted order by their $x$ coordinates and maintaining a set of all points seen so far sorted by their $y$ coordinate. It follows, that the time needed to compute $f(l, r, m)$ is $O((RL) \cdot \log (RL))$, and its dominated by the time of sorting the points and performing query operations to the set sorted by $y$ coordinates. Now, we showed how to decompose a problem using divide and conquer and how to combine the results computed for subproblems with additional values, $f$ and $g$, into the final result. The total time complexity of this approach can be written as $T(N) = 2 \cdot T(N/2) + O(N \log N)$, which is equal to $O(N \log^2 N)$. For implementation details please refer to both setter's and tester's solutions. AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 13 Mar '17, 02:46

I think this is a very good problem! answered 13 Mar '17, 18:07

In the subtask 2 in the editorial above "An Edge (i,i+1)(i,i+1) for i=1,2,…,N−1i=1,2,…,N−1 is taken into the final result i⋅(N−1) times because it is a part of that many shortest paths connecting vertices with indices x≤ix≤i with vertices with indices y≥i+1y≥i+1." It should be i(Ni) instead of i(N1). answered 13 Mar '17, 22:29

Apologies.I have solved this problem for second subtask, still not been able to figure out where I am wrong. answered 14 Mar '17, 22:31
1
Take a closer look when you do: "long long int p= a[i]i(ni);" Notice that a[i], i, and n are declared as 32bit integers in your code, so the result of their multiplication is also 32bit integer and you have overflow
(14 Mar '17, 22:54)
Thanks. That was silly mistake. I am have tried atleast 45 times(but was not able to notice overflow). This is the best problem I have encountered this month.
(14 Mar '17, 23:14)
