So QR2 for TCO10 was yesterday, and I decided to take a look at the questions today.
Q1) Given a list of sell prices and buy prices for a specific type of object, and a tax on selling, determine maximum profit given you start with none of the item.
This is pretty easy. Calculate the tax for each sale and reduce the sell price accordingly. Then sort the adjusted sell prices descending and buy prices ascending, then while adjusted sell price is greater than the buy price, add the difference to the profit.
Q2) Given a square array of live, dead, unknown, determine the optimial values for unknown to ensure the maximum number of live cells after 1 round of the rules for Conway’s game of life. Important restriction that no cell will have 2 or more unknowns in its set of neighbours.
Again this is pretty easy, al because of the restriction, but there are a few tricks. First you need to put the the input array into a larger array so that you have a border (for easiest implementation a border of width 2), since cells may come to life outside of the input array. Because of the restrction, every unknown can be considered seperately, which means the algorithm runs O(n) in cells. For each neighbour of an unknown, calculate whether it will be alive or dead for each of live and dead options for the unknown. Do the same for the unknown itself. Chose the maximum sum of live cells for each of the two cases and set the unknown to that case. Once all unknowns are set, simulate the entire board for one step and return the live count.
Q3) Given a paragraph (upto 1000 characters) with all the spaces and puncuation removed, and a list of up to 50 words (each up to 50 characters) determine a ’tiling’ of the paragraph using the words (each word may be used 0 or more times) which maximizes the value of the square of the longest consecutive tiled sequence minus the number of uncovered characters.
This is a big jump in difficulty and I have to say that I probably would not have gotten this one out. It is fairly obviously dynamic programming, the problem comes in determining the right way to achieve it. My first guess was to dynamic program over the first N characters, with the last M covered, but I realised I also needed have the largest consecutive cover P as a variable parameter too. This meant that the dp space was length cubed, way too large. After looking at another competitors solution I now see the correct approach. Use dynamic programing to calculate the minimum number of uncovered tiles for a range starting at i and finishing at j. This can be achieved by starting with the minum for a range of one less length + 1, and then minimizing by checking which words match at the end of the range and using the minimum for the range minus the matched word. Note that the act of checking the words is quite expensive in the worst case, so pre caching whether each word matches for each location keeps the runtime under control.
Once we have the minimum number of uncovered tiles for each possible range, we loop over each possible range where that minimum is 0, square the range length and subtract the minimum number of uncovered tiles before and after the range. Return the maximum of all of those possible values and -length. This works because although it doesn’t descriminate as to whether the range selected is the maximum consecutive uncovered section, when the maximum consecutive uncovered section is selected, it will receive a larger score because the number of uncovered tiles will be the same and the selected range length will be larger.