Блог пользователя accoder1nd

Автор accoder1nd, история, 3 года назад, По-английски

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

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
3 года назад, # |
Rev. 4   Проголосовать: нравится +7 Проголосовать: не нравится

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)$$$.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

    It would be really helpful if you can elaborate a little more!!

    I can't visualize how the dp is getting filled.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 6   Проголосовать: нравится +8 Проголосовать: не нравится

      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.

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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?

        • »
          »
          »
          »
          »
          3 года назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          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.

          • »
            »
            »
            »
            »
            »
            3 года назад, # ^ |
            Rev. 9   Проголосовать: нравится +5 Проголосовать: не нравится

            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

            • »
              »
              »
              »
              »
              »
              »
              3 года назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              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.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    3 года назад, # ^ |
    Rev. 3   Проголосовать: нравится +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.

    • »
      »
      »
      3 года назад, # ^ |
      Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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