Subtask 1 [30%]

This subtask rewarded any brute force solutions, typically with recursion.

Time Complexity: \(O(2^{R + C})\)

Subtask 2 [70%]

Solution 1:

Using memoization, we can prevent any redundant recomputations. This turns the problem into a typical dynamic programming problem, where \(dp[i][j][k][l]\) represents the number of ways to get to cell \((i, j)\) with \(k\) turns, with \(l = \{0, 1\}\) representing the direction taken. Clearly, each state has \(O(1)\) transitions.

Time Complexity: \(O(RCK)\)

Solution 2:

We can model any path from \((1, 1)\) to \((R, C)\) as a sequence of up or rightward moves. We can arrange the \(K\) turns as \(\frac{K}{2}\) breaks in the \(R - 1\) up moves and \(C - 1\) right moves, so the final answer is the number of ways to split \(R - 1\) objects into \(\frac{K}{2}\) non-empty groups and \(C - 1\) objects into \(\frac{K}{2}\) non-empty groups. Extra care must be taken when \(K\) is odd. Some precomputation is needed to calculate binomial coefficients.

Time Complexity: \(O((R + C)^{2})\)