ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

Discussion of Problem 2143. Victoria!

Dynamic programming by profile?
Posted by sadovnik 14 Nov 2019 18:33
Is it dynamic programming on the profile?
How to apply it?
Re: Dynamic programming by profile?
Posted by Alikhan Zimanov 1 May 2020 17:28
Yes, it is. Let dp[i][mask] be the maximal number of passengers we can sit on the first i rows such that none of them sit close to each other and the i'th row is occupied exactly as in the mask (0 <= mask <= 63, if the j'th bit in the mask is 1, then the seat (j + 1) is occupied, otherwise it is not). Now, to compute dp[i][mask] we need to iterate through all possible masks "prev" of the (i - 1)'st row. For each such valid mask prev ("valid" means that none of the passengers on the (i - 1)'st and i'th rows sit close to each other) we have to relax our answer by dp[i][mask] = max(dp[i][mask], dp[i - 1][prev] + (the number ones in the mask)). Additionally, we can maintain the previous mask pointer[i][mask] = prev for each dp[i][mask] which gives us the best answer. When done with computing dp, we have to run through all valid masks of the last row and check whether dp[n][mask] >= k. If there is no such mask, then the answer is impossible. Otherwise, remember this mask and easily restore the answer by using those pointers to "prev" masks.

Edited by author 01.05.2020 17:30

Edited by author 01.05.2020 17:30