accoder1nd's blog

By accoder1nd, history, 6 weeks ago, In English

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

Guys please share your approach

 
 
 
 
  • Vote: I like it
  • +7
  • Vote: I do not like it

»
6 weeks ago, # |
Rev. 4   Vote: I like it +7 Vote: I do not like it

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   Vote: I like it +1 Vote: I do not like it

    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   Vote: I like it +8 Vote: I do not like it

      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.

      • »
        »
        »
        »
        2 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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?

        • »
          »
          »
          »
          »
          2 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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<l_2< \dots<l_k$$$. If you remove the last team, then the remaining teams can work on $$$[1,i']$$$ where $$$i'<i$$$. This hints towards a dp solution with subproblems being covering intervals $$$[1,i]$$$. Denote this by $$$dp_i$$$.

          Now, we need to figure out the transitions. We removed some team working on $$$[1,i]$$$ to reach a smaller subproblem. So, iterate over all possible teams which contain bridge $$$i$$$ in their interval. We will assume that this is one of the teams working in the optimal case. Removing this team would give a smaller subproblem which we have already solved. Suppose the current team works on the interval $$$[p,q]$$$ where $$$(p \le i \le q)$$$. So, we need to modify $$$dp_i$$$ to $$$min(dp_i, dp_{p-1}+q-p+1)$$$ where the minimum is taken for all intervals $$$[p,q]$$$ containing $$$i$$$. Do this for each $$$i$$$ from $$$1$$$ to $$$n$$$. This would give TLE so we can use a lazy segment tree.

          • »
            »
            »
            »
            »
            »
            2 weeks ago, # ^ |
            Rev. 9   Vote: I like it +5 Vote: I do not like it

            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<L2<...<Lk and R1<R2<...<Rk (This is because if 2 teams have the same starting point and different ending points, then only one of the teams will be in the optimal solution. Ex: [1,2], [1,3] -> 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<L2<...<Lk and R1<R2<...<Rk. Right?

            Because of this, we can say that if we remove the last team, tk, then we will obtain the optimal solution for the interval [1, i'] where Lk <= i' < Rk. So, for any team [p, q] where p<=i<=q, the cost of this team is dp[i']+(q-p+1) where p <= i' < q (And dp[i] would be min of all such teams). But why did you use dp[p-1] ? I am confused from here since p <= i' < q.

            Also, I did a dry run for this for the first test case: n=4 m=3 teams={(1,2),(2,3),(3,4)} and this is the dp array:[0, 2, 2, 4, 4] As we can see, dp[i] tells us the cost of working from [1,i]. In this case, i=1 gives 2 but the cost of working from [1,1] or just segment 1 is 1 since only one team works on it.

            These are the things that are confusing to me

            • »
              »
              »
              »
              »
              »
              »
              2 weeks ago, # ^ |
                Vote: I like it 0 Vote: I do not like it

              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' <i$$$. But as $$$dp_i$$$ is monotonically increasing($$$dp_x \le dp_y$$$ if $$$x<y$$$), we can just use $$$dp_{p-1}$$$.

              Also, the cost in your example is 2, not 1. We need to work on $$$[1,1]$$$ but the sum of teams that end up working for each bridge is 2.(1 for bridge 1 and 1 for bridge 2). You can't simply neglect the extra cost that results from some team working outside the interval of interest.

              • »
                »
                »
                »
                »
                »
                »
                »
                2 weeks ago, # ^ |
                  Vote: I like it 0 Vote: I do not like it

                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′<i?? Why will i' be >= 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   Vote: I like it 0 Vote: I do not like it

    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].

»
2 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

It would be nice if you could share a link to the problem, so that those who want to, can attempt it.

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like 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]=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]$$$

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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   Vote: I like it +3 Vote: I do not like it

    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   Vote: I like it 0 Vote: I do not like it

      you have to take both of them. first take [1,4] and then [2,5], And for complexity you can use segment tree.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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

»
2 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone give the code for this

»
2 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

    Nice solution and needs std only. Pushing forward lets forget about managing traversal cost change because of overlapping in compare to pulling forward solution.

  • »
    »
    2 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    can you elaborate on how this works? like, what is your logic and why?