el_magnito's blog

Help with cses dp problem elevator.
By el_magnito, history, 3 years ago, In English

I am stuck in the ELEVATOR problem in cses dp section. I tried to find the solution online but couldn`t find any reliable source. PROBLEM LINK — https://cses.fi/problemset/task/1653. It would be a great help if someone can explain the idea behind it.

Tags #dp
  • Vote: I like it
  • 0
  • Vote: I do not like it

Comments Comments (11)
| Write comment?
»
3 years ago, # |
  Vote: I like it +1 Vote: I do not like it

See here: Competitive Programmer's Handbook pdf page 103-104

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks a lot.

    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      I cant understand what the bit operations are doing. Can you explain them?

      → Reply
      • »
        »
        »
        »
        12 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        s&(1<<p) — checking is p-th bit set(true if set, false if not).

        s^(1<<p) — XOR operation unsets only p-th bit(if s was 111 and we applied s^(1<<1) then s transformed to 101)

        → Reply
      • »
        »
        »
        »
        4 months ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        we have the same pfp

        → Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it 0 Vote: I do not like it

I solved in this way I have two fields DP and Moves

Moves[Mask] — the minimum number of elevator rides

DP[Mask] — Minimum Weight Sum of People for the last Move

We know that we have moves in the priority so the transitions were

newDp = (DP[mask ^ (1 << j)] + w[j]) % x

newMoves = (Moves[mask ^ (1 << j)] + (newDp > Dp[mask ^ (1 << j]))

It means that if newDp is bigger that x then new Move is added, and we change the Moves and DP, if Moves > newMoves or (newDp < DP and Moves = newMoves)

→ Reply
»
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it 
for (int s = 1; s < (1<<n); s++) {
// initial value: n+1 rides are needed
best[s] = {n+1,0};
for (int p = 0; p < n; p++) {
if (s&(1<<p)) {
auto option = best[s^(1<<p)];
if (option.second+weight[p] <= x) {
// add p to an existing ride
option.second += weight[p];
} else {
// reserve a new ride for p
option.first++;
option.second = weight[p];
}
best[s] = min(best[s], option);
}
}

don't you think in else part there should be option.second=min(option.second,weight[p])?????

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

    no option.second=min(option.second,weight[p]) is incorrect, because we are considering last ride. It means (let the current ride be nth ride), --> we have already completed (n — 1)th ride, so we cannot go back to some kth ride which is obviously (1 <= k < n) and update it.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      can you tell me why for input {2,3,4,5,9} and lift capaicty as 12 the above algorithm prints:-

      best[31].first as 1 and best[31].second as 11

      don't you think (best[31].first) which is actually minimum no of rides should print 2, not 1.

      → Reply
      • »
        »
        »
        »
        21 month(s) ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        best[mask].first is the number of complete rides, and best[mask].second is the weigth of the current ride.

        If best[mask].second == 0, thus the minimum number of rides for mask is best[mask].first, else this number is best[mask].first + 1 (+1 because of the incomplete ride)

        → Reply
»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

For a mask, for a set bit b, we are checking whether it can fit in the group already formed with least sum, at this time it is possible that for current mask the minimum sum group will not be (weight[b]+dp_sum[remaining]) and we should now change this dp_sum[current_mask] to sum of the group with least sum. Why we are not doing that? For ex: we have 8,6,4 and max_wt=10, and dp_sum[(8,6)] = 6 and rides[{8,6}] = 2 and on checking for weight 4, dp_sum[{8,6}]+4=10, we are actually doing dp_sum[{8,6,4}]=10 but should not we do dp_sum[{8,6,4}] = 8; as from {8}, {6,4} these groups, 8 has minimum sum group.

→ Reply