Rating changes for the last round are temporarily rolled back. They will be returned soon. ×

el_magnito's blog

Help with cses dp problem elevator.
By el_magnito, history, 6 weeks 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 (5)
»
6 weeks ago, # |
  Vote: I like it +1 Vote: I do not like it

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

→ Reply
»
13 days 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