Problem Link : https://www.codechef.com/NCCW2021/problems/AKNTWRK
AK works in a logistics company, and he is assigned with a task to build a road network between N cities. The size of a city is Pi and AK would like to build N−1 bidirectional roads connecting two cities such that any city can reached from any other city.
Assuming that the cost of building a road between ith and jth city is abs(i−j)∗D+Pi+Pj. Find the minimum possible cost to achieve the task
Input:
The first line contains two integers N and D.
The second line contains the array P of size N.
Output:
Print the answer.
Constraints
1≤N≤2∗10^5
1≤D≤10^9
1≤Pi≤10^9
Sample Input:
3 1
1 100 1
Sample Output:
106
EXPLANATION:
This cost can be achieved by, for example, building roads connecting City 1,2 and City 1,3.
I was thinking in terms of some MST(Minimum Spanning tree) based approach to solve this problem but the complexity will be greater than O(NlogN). Not able to come up with some efficient approach for this problem.
Please suggest some optimal approach. Thanks in advance :)
I think this can be done straightforward with lazy propagation.
Initially build the lazy tree with value p_i + (i-1) * D;
For each i, Then, query the minimum of 1 to i-1 and minimum of i+1 to n. and then add the cost. (while querying just include if l_idx > r_idx return infinity, where l and r are the range query indexes)
Now update the 1 to i-1 by D and i+1 to n by -D.
Update : The solution wont work. Wrong.
I think your idea is close to working.
Say we have two lazy range add, min query segment trees, initialized with values
$$$a_i = p_0+p_i+i \cdot d$$$, and $$$b_i = \infty+p_i+(n-i)\cdot d$$$, one for the "forward" edges and one for the "backward" edges, taking infinity as a really big value.
Then we simulate Prim's algorithm, take as initial vertex, node 0, finding the minimum outgoing edge fast with our segment trees. The minimum edge outgoing is either a forward or backwards edge, so we query both our segment trees with a findmin operation, and pick the cheaper option. The invariant will be to always hold exactly the cheapest edge to each nonvisited node in the segment tree or Infinity if it is already visited. When we take a new edge in our minimum spanning tree, we do a range add in the appropriate place in the segment trees, to now reflect the fact that we can use edges going outward of this new node. The details for where exactly to range add, will be a bit tricky, but it should work. This would give a O(n log(n)) algorithm (n rounds of doing O(1) queries to a segment tree).
I have a solution without segment tree. I already got AC as well as passing small tests against the naive solution.
Let's build the leftward tree as the following. For each node $$$i$$$, we only connect it to some of the nodes $$$j$$$ on its left side, that is, $$$j < i$$$. We actually can just pick one $$$j$$$ for $$$i > 1$$$, because thinking this in term of the rooted tree at node 1 (or 0, based on implementation), then picking $$$j$$$ is just like picking parent of $$$i$$$. Also to pick the optimal $$$j$$$, let's break down the formula $$$|i - j| \times d + p_i + p_j = (p_i + i \times d) + (p_j - j \times d)$$$, therefore for each $$$i$$$, we should just pick the one with minimal $$$p_j - j \times d$$$, this can be done by maintaining the minimal when we are iterating $$$i$$$ from 2 to n.
So to get the optimal solution, we can kind of build the leftward tree, and then try to add some rightward edges to fix the tree (that is, when adding the edge $$$u-v$$$ with cost $$$c$$$, we remove the maximum edge along the path from $$$u$$$ to $$$v$$$, if that edge is bigger than c). We can do better tho. Consider the rightward tree the same as the leftward counter part but with rightward edges. If the rightward and leftward share no edges, then we can actually just do MST with edges from 2 trees, because the other edges will never be in the final answer.
So now for the last case. Consider the shared edge $$$u-v$$$ ($$$u < v$$$). If we remove this edge from the rightward tree, we actually does not affect the result of the final tree because the set of edge are the same. So for $$$u$$$, we can pick the next $$$v$$$ with the second smallest $$$p_j + d \times j$$$. And if this edge is also in the leftward tree, we pick the third, ... Continue doing this process until we run out of nodes on the right of $$$u$$$, or if we find one, add it to the edge list. We won't doing this process forever, because the maximum number of edges that need to be skip is just the same as the number of edges of the leftward tree, therefore the process take at most $$$O(n)$$$ step.
For implementation, I use multiset for maintaining the set of rightward edge, and also I kept the adjacency edges of the leftward tree, with set or sorted vector. For picking $$$v$$$, we can look into the multiset and check if $$$v$$$ is in the adjacency list of $$$u$$$. So skipping and finding part is done in $$$O(n \log n)$$$, and also because of MST, the overall process is $$$O(n \log n)$$$
darkkcyan orz