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.
See here: Competitive Programmer's Handbook pdf page 103-104
Thanks a lot.
I cant understand what the bit operations are doing. Can you explain them?
we have the same pfp
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)
Is I cann't done it with recursion + dp
I got tle
don't you think in else part there should be option.second=min(option.second,weight[p])?????
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.
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.
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)
Can anyone suggest a good problem similar to this one for practice?
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?