el_magnito's blog

Help with cses dp problem elevator.
By el_magnito, history, 4 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 (12)
| Write comment?
»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
4 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
»
4 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
  • »
    »
    3 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
    • »
      »
      »
      3 years 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
      • »
        »
        »
        »
        3 years 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
»
4 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone suggest a good problem similar to this one for practice?

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

The idea is to calculate for each subset of people two values: the minimum number of rides needed and the minimum weight of people who ride in the last group.

Above is the whole Idea for given problem, but I am not understanding that why we only need to check for last ride?

→ Reply