### accoder1nd's blog

By accoder1nd, history, 6 weeks ago, You have to construct a bridge in the city of berland. The bridge consist of n sections (1 to N) There are M constructions teams , the i'th team will work on the section from (li to ri)of the bridge.The bridge is said to be constructed if all the section from (1 to N) are worked on by at least one of teams The cost of building a section is the number of teams that worked on it so the cost of building the bridge is the sum of cost of building all the sections.

and you have to choose a subset of the teams such that bridge is completely constructed and cost is minimum possible,else print -1

Eg:= n=4 m=3 teams={(1,2),(2,3),(3,4)}

optimal way is to choose team and team 3 so output is 4.

Eg:= n=4 m=2 teams={(1,3),(2,4)}

you have to choose all the teams and cost will be 6 as section 2 and 3 will worked on by 2 teams.

Constraints: 1<=n,m<=10^5 1<=li,ri<=n

Asked in contest which is over now Comments (19)
 » 6 weeks ago, # | ← Rev. 4 →   Note that the cost is the sum of the lengths worked upon by all the teams. Now, let $dp_i$ denote the minimum cost to work on the interval [1,i]. Initially, $dp_0=0$ and $dp_i=INF$ for $i>0$. After, processing $dp_i$, take all the teams $[l,r]$ with $l=i+1$. Do the change: $dp_j=min(dp_i+r-l+1,dp_j)$ for all $j$ such that $l \le j \le r$. This can be done using lazy segment trees. Finally $dp_n$ is the answer. The time complexity is $O((m+n)*logn)$.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   It would be really helpful if you can elaborate a little more!!I can't visualize how the dp is getting filled.
•  » » » 6 weeks ago, # ^ | ← Rev. 6 →   Suppose you have to work on the interval $[1,i]$. Of all the teams working for this when the cost is minimum, consider the one with the highest $l$. This team works on $[l,r]$ where $l \le i$ and $r \ge i$. What happens if you remove this team? The remaining teams can work comfortably in the interval $[1,l-1]$ (or maybe more, if they can work on $[1,l']$ where $l'>l-1$ then cost would be $dp_{l'}+r-l+1 \ge dp_{l-1} + r -l+1$ cause $dp$ is monotonic here. So, it suffices to use $dp_{l-1}$ here.) So, $dp_i \le dp_{l-1} + r -l+1$. You can iterate over all possible $[l_j,r_j]$ such that $l_j \le i \le r_j$, and find the minimum of $dp_{l_j-1}+r_j-l_j+1$, but that would be costly. Instead, you update the values moving from left to right.
•  » » » » I am sorry, I still don't understand your approach. I am still new so my first question is, how do we know that we can even use dp in this? How does this problem demostrate optimal substructure and overlapping sub problems? Second, can you explain why you did this: dpj=min(dpi+r−l+1,dpj) dpj represent the min cost of working on interval [1,j] so how is that cost related to dpi+r-l+1? dpi would be min cost of working from interval [1,i]. how is the range of a team that works from l,r used here? wouldn't we instead need to find minimum number of teams at some segment of the bridge to calculate the cost?
•  » » » » » In the first comment I have mentioned that the cost is equivalent to the sum of the lengths worked on by the teams.Imagine that you needed to just work on $[1,i]$ and teams $t_1, t_2, \dots, t_k$ work on it(in the optimal case) with intervals $[l_1,r_1], [l_2,r_2], \dots, [l_k, r_k]$ where $l_1 •  » » » » » » 2 weeks ago, # ^ | ← Rev. 9 → Please correct me if I am wrong. This is my understanding so far:Suppose we have an interval [1,i] and k teams work on it (in the optimal solution): t1:[L1, R1], t2:[L2,R2] ... tk:[Lk,Rk] where L1 only one of these can be in the optimal solution) Same goes for 2 teams ending at the same point. This proves that all starting and ending points are different i.e. this is true:L1 •  » » » » » » » For one interval$[p,q]$where$p \le i \le q$you need to change$dp_i$to$min(dp_i, dp_{i'}+q-p+1)$for all$p-1 \le i'
•  » » » » » » » » Can you clarify how if we have the interval [1,i] and a team such that p<=i<=q then if we remove that team, we will have the interval [1,i'] where p−1≤i′= p-1 ? And even if it is true, (i understand that the dp will be monotonically increasing) but why is just using dp[p-1] ok?Also, in my example, the cost from [1,2] will be 2 but since you defined dp[i] as the "minimum cost to work on the interval [1,i]", this means that from [1,1] there is only 1 team working there and the cost should be 1 (granted that the range of the team working is from [1,2] -> if it was asking for the interval [1,2] then it is correct) Suppose we just had n=2 and m=1 and the team was t1:[1,2] Then the cost of working on just the first interval [1,1] will be 1 and the cost of working on [1,2] will be 2
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   I think we can use almost usual segment tree (skip ) if while traversing [l, r] intervals sorted by r we inc every dp[r] by r: dp[r] = min{dp[r], (min(dp[l:r]) — this_mins_index) + (r-l+1) + r }This increase would ensure for example, that if dp[i1] = dp[i2] i1 < i2, will be different by (i2 — i1) points — this will take into account that overlapping with bigger set of segments should result in extra cost. So the final answer will be dp[n]-n. But we need either store the pairs (min, index) in segtree or store (index) but compare values stored in some array — cost[index].
 » It would be nice if you could share a link to the problem, so that those who want to, can attempt it.
 » My idea: Sort all the segments on the basis of the increasing order of endpoint. Let $dp[i]$ denote the minimum cost to cover segment from 0 to i. $dp=0$; Traverse all segment form left. Suppose we are at the kth segment. Let the kth segment has $l$ and $r$. We will update $dp[r]$,$dp[r]=min(dp[r],min(dp[j])+(r-l+1))$ for $l-1<=j<=r$;After that return $dp[n]$
•  » » can you please explain why we have taken min of all the dp[j] where j lies from l-1 to r.
•  » » 2 weeks ago, # ^ | ← Rev. 3 →   Well, would it fit in the time limit? I think it is $O(n^2)$ in the worst case. This may also give WA. Imagine 5 bridges and 2 teams: [1,4] and [2,5]. Can you tell me how does your solution work here?Edit: I got it, I misread the dp that you wrote.
•  » » » 2 weeks ago, # ^ | ← Rev. 3 →   you have to take both of them. first take [1,4] and then [2,5], And for complexity you can use segment tree.
•  » » I have a few questions, why sort the segments based on endpoint? why not start point?Also, your logic is that if there is a segment [l, r] then you will assign the cost of r-l+1 to all i such that l<=i<=r and keep track of the min?PS. Can you explain why j is from l-1 to r?? this is really confusing
 » can anyone give the code for this
 » Sort the array of pairs by left[i] . Maintain a priority_queue of{-totcost_to_reach_right,right}.Insert : {0,0} Traverse the array and check if left[i]<= top_of_pq.S, if yes then insert {totcost-(r-l+1),right[i]} if no then pop the top element of pq . If at any point the pq is empty OR if atlast the top_of_pq.S!=n then ans is -1 . Otherwise print -1*top_of_pq.F.
•  » » 2 weeks ago, # ^ | ← Rev. 2 →   Nice solution and needs std only. Pushing forward lets forget about managing traversal cost change because of overlapping in compare to pulling forward solution.
•  » » can you elaborate on how this works? like, what is your logic and why?