Re: Dynamic programming by profile?

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*

Re: Dynamic programming by profile?

Posted by

svr 22 Mar 2021 13:27

Simple recursion with set<string,int> memorisation also works

May be tests are weak