H. I Want That Cake
Author: Suhendry Effendy.
Prepared by: Suhendry Effendy, Felix Halim.
Problem: H – I Want That Cake
This is another problem which can be solved by dynamic programming. It’s not hard to come up with an O(N3) solution.
The dynamic programming state is dp[x][m], where x is the x-th person’s turn, m is the remaining number of cakes, and dp[x][m] is the winner for this state (either ‘A‘ or ‘B‘). If m ≤ K, then obviously the winner will be turn[x] (simply eat all the cakes). Otherwise, iterate from 1 to K and test whether there is next state (dp[x+1][m-eat]) which winner is the same as turn[x]. If there is one, then dp[x][m] = turn[x], otherwise, dp[x][m] = ~turn[x] (~turn[x] means the opponent of turn[x]).
However, a plain implementation of this solution will get TLE.
An O(N2) solution
Notice that there are overlapping computation in the previous O(N3) solution. For example, consider dp[x][m] and dp[x][m+1]; dp[x][m] iterate for dp[x+1][m-1] .. dp[x+1][m-K], while dp[x][m+1] iterate for dp[x+1][m] .. dp[x+1][m+1-K]. The difference between dp[x][m] and dp[x][m+1] are on dp[x+1][m-K] and dp[x+1][m]. We can exploit this structure to optimize the dynamic programming solution, specifically, the computation for each state can be done in O(1) by considering only the difference as previously explained. Hence the solution is O(N2).
An accepted O(N3) solution
There is, however, an easier solution. The previous O(N3) solution can be accepted if it is implemented with:
- Top-down approach (recursive + memoization),
- Iterate eat = K..1 (starts from the largest first, not 1..K),
- Terminate early (return right away whenever you get what you’re searching for).
I notice this solution when I saw Felix Halim’s TLE solution (he iterated from 1 to K), and realized that his solution will be much faster if he flipped the iteration order. Moreover, the running time for this solution is faster compared to the previous O(N2) solution. When we prepared this problem, we couldn’t find test data which is able to make this solution TLE. I suspect the time complexity of this solution is much lower than N3, but I didn’t do further analysis.