Hi Gozz, Could we please get some guidance on finishing the knights problem? I've given it a good crack but at this point it's soaking up too much pre-exam study time for me to continue. Thanks in advance

P.S. I don't think anyone knows how to do question 9 either

ANONYMOUS wrote: Please try to ask questions like this sooner in future. It is 81 work minutes before the exam and I am technically meant to be on urgent leave, so you are lucky I decided to do one last check in case there was something serious. I will also point out that knowing the solutions to sample exam questions is not necessarily helpful for your study. Knowing these solutions will not help. You need to train the skill to solve problems like this more generally. To that end I will (as best I can in the time I have) present as best a derivation as I can so you can hopefully learn from the process, as in the lectures. As discussed in the lecture where we reviewed the sample exam, both of these questions can be solved by DP. So you should be thinking about how to break this down into a recurrence in terms of subproblems (keeping in mind we need a DAG structure for this to work). Q8: We are asked to count the number of ways of placing knights on a board so they can't attack each other, so let's formalize that into a process with states and actions we can take in those states, as these states will then give us subproblems. The way I like to think about this is let's go from left to right, placing some configuration of knights in each column, and we are just trying to count the number of ways we can do that and get to the right end of the board without having any attacking each other. At any point, all we need to know is the column we are up to and any knights that could attack this column. Since we know knights can't move attack more than two columns away, that means we just need to know the configuration of the last two columns. Our state space is therefore (n, K) where n is the number of columns we have filled so far and K is the configuration of the last two columns (n-2 and n-1). There are 8 spaces in total in these two columns, meaning we can represent the configuration as just the set of these spaces that have knights on them, of which there are 2^8 = 256 possible configurations (implementation detail: this is a good opportunity to use a bitset). Our recurrence just needs to correspond to placing every permissible configuration in the next column. If f(n, K) is the number of ways of filling n columns such that the configuration of the last two columns is K, then we have the base case and recurrence: f(0, {}) = 1 # empty set because no knights can be off the board f(0, K) = 0 # where K is non-empty, since we can't have knights off the board f(n, K) = sum(f(n-1, K') | nothing in K' can attack anything in K) and our solution is then just sum(f(N, K)) for all K (or alternatively actually f(n+2, {}), to represent the two empty columns off the right end of the board). This means we have 256 N states with a 2^4 = 16 = O(1) recurrence, giving an overall complexity of O(N). The following is an interesting observation, but the above would be sufficient to get full marks, since it is more efficient than the naive. At this point you may also be able to make the observation that this is just a sum of the subproblems over previous (compatible) states, which is exactly how we did path counting in a DAG. Indeed, if we construct the DAG explicitly by computing the state dependency graph, then this problem is just path counting. And as we have seen, we can do path counting in O(V^3 lg N) using matrix exponentiation. Here V is most simply just the number of states, 256 N, but since we are counting paths of length N we don't actually need to know how far through the path we are anymore, and so we can reduce this to just V = 256. This gives an O(lg N) solution (with a substantial 256^3 constant factor). Q9: This problem can also be solved by DP. Again, think about the process of how we can construct possible solutions to this problem, so we can then use DP to pick the optimal one (Q8 used DP to count the number of solutions). The actions available to us may be "pick a subarray that will be part of our solution". We just need to keep enough state to make sure we don't pick something invalid (like two overlapping subarrays). The easiest way to do this is to insist that we pick the subarrays in order from left to right, and then all we need to keep track of is how many we have picked, and what prefix of the array we are now not allowed to pick from. This corresponds to subproblems with state space (n, K) where the subproblem is "what is the maximum sum possible by taking at most K subarrays from the prefix of length n?". Our base cases then correspond to the empty prefix or having no subarrays to use, and our recurrence is just trying all subarrays and recursing into the subproblem that optimizes the space to the left of our chosen subarray. f(0, K) = 0 f(n, 0) = 0 f(n, K) = max(sum(X[i:j]) + f(i, K-1) | 0 <= i < j <= N) And our overall solution is just f(N, k). This means we have O(N k) states with an O(N^2) recurrence for an overall complexity of O(N^3 k). This is good enough to get full marks, but there is a more efficient solution. I do not have the time to go into great detail, but: We can instead think about this process as scanning over elements left to right and deciding whether to take that element or not. To prevent us taking invalid constructions, we just need to know at every point how many subarrays we have left, and whether the previous element is already in a subarray and we can just extend that one or do we have to take a new one? Our subproblems are therefore "what is the maximum sum possible using at most K subarrays over the prefix of length n where the last subarray does/doesn't include element (n-1)?" This gives us state (n, K, r) where n is prefix length, K is number of subarrays, and r is True if there is a subarray ending at the end of the prefix and False otherwise. Writing the recurrence here is too messy, so I will leave it as an exercise to the reader. Hope that helps.