So QR2 for TCO10 was yesterday, and I decided to take a look at the questions today.<\/p>\n
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.<\/p>\n
This is pretty easy.\u00a0 Calculate the tax for each sale and reduce the sell price accordingly.\u00a0 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.<\/p>\n
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.\u00a0 Important restriction that no cell will have 2 or more unknowns in its set of neighbours.<\/p>\n
Again this is pretty easy, al because of the restriction, but there are a few tricks.\u00a0 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.\u00a0 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.\u00a0 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.\u00a0 Once all unknowns are set, simulate the entire board for one step and return the live count.<\/p>\n
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.<\/p>\n
This is a big jump in difficulty and I have to say that I probably would not have gotten this one out.\u00a0 It is fairly obviously dynamic programming, the problem comes in determining the right way to achieve it.\u00a0 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.\u00a0 This meant that the dp space was length cubed, way too large.\u00a0 After looking at another competitors solution I now see the correct approach.\u00a0 Use dynamic programing to calculate the minimum number of uncovered tiles for a range starting at i and finishing at j.\u00a0 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.\u00a0 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.<\/p>\n
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.\u00a0 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.<\/p>\n","protected":false},"excerpt":{"rendered":"
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.\u00a0 Calculate the … Continue reading TCO10 QR2<\/span><\/a><\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[3,6],"tags":[],"class_list":["post-139","post","type-post","status-publish","format-standard","hentry","category-code-competitions","category-random-musings"],"_links":{"self":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/139","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=139"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/139\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=139"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=139"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=139"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}