Three easier questions this round, although I have to say I found the ‘easy’ question the hardest… Advancing cut-off was either of the first 2 problems and the smalls from both the others and a few minutes to spare.\u00a0 Solving the 3rd problem and smalls of the other was worth 1 more point and ~400 places as a result.<\/p>\n
Q1) In a game of finding all the locations of a 1xW rectangle in an RxC space, where before each guess the opponent is free to move the 1xW rectangle anywhere that is consistent with the previous answers, determine the minimum number of guesses to guarantee victory assuming the opponent plays to maximize your guesses.<\/strong><\/p>\n A1) So I spent a while rabbit holing entirely the wrong direction.\u00a0 I seem to have ‘divide and conquer’ on the brain, this is the second time I’ve gotten stuck on a problem this year because I was convinced that dividing the problem in half was optimal.<\/p>\n So in practice this question boils down to forcing the opponent to have no options as fast as possible.\u00a0 This starts by reducing the places the rectangle can be.\u00a0 The fastest way to do this is obviously (in hind sight) to guess W cells away from an edge of where it could be.\u00a0 The opponent will answer no unless it has to, a yes easily reaches a smaller number of guesses.\u00a0 No answer eliminates W spots.<\/p>\n When you are down to one last row with 2*W-1 or less possible spots the strategy changes.\u00a0 W spots you know everything, so just guess every spot left to victory.\u00a0 Between 2*W-1 and W+1 inclusive you know some subset of the middle. Guess immediately next to that, the opponent will answer no (or possibly yes if there is more than one unknown spot left, it makes no difference to them if they are assume we play ideal).\u00a0\u00a0 Once they answer no, we know everything and can guess all the remaining spots.<\/p>\n In the end this entire problem can be boiled down to C\/W*R + W – (C%W==0 ? 1 : 0).\u00a0 Each row other than the last takes C\/W guesses to eliminate entirely.\u00a0 The last takes C\/W – 1 guesses to get down to the last section, then W+1 guesses to pin everything down.\u00a0 With one exception if C%W == 0, the last section is W spots, so only W guesses are required to pin everything down.<\/p>\n In the end I wonder why the limited the large input to just 20 x 20, I guess it leaves open a DP solution rather than just the greedy.<\/p>\n Q2) Given a list of letters (size N) to choose from at random, a length of output (size S) and a ‘target’ sequence (size T), determine the maximum number of times the target sequence could appear, then determine the difference between that and the expectation value for number of times it appears in the output if generated at random.<\/strong><\/p>\n A2) So this is a deceptively easy problem.\u00a0 I usually don’t like probability problems, but in this case the details clearly point out that multiple overlapping instances all count.\u00a0 Hence the probabilities are independent and easily calculated.\u00a0 List of letters can be turned into base probabilities by summing 1\/N for each letter.\u00a0 The target is then converted into a probability by the product of those base probabilities for each letter in the target.\u00a0 The full expectation value is then that ‘target’ probability times S-T+1, since each possible starting point is fully independent.<\/p>\n The maximum number of times target sequence can appear is determined by the maximal non-complete overlap of the target sequence with itself.\u00a0 Which can be determined with a simple nested for loop.\u00a0 The maximum is then (S – T)\/(T-overlap) + 1.\u00a0 One length T, then as many T-overlap sections that will fit.<\/p>\n Q3) Given a list of values that you can have up to c of each of, determine the minimum number of extra values in order to be able to create every possible total between 1 and V.<\/strong><\/p>\n A3)\u00a0 I found this question easy, but only because I’ve had previous experience with this kind of question before.\u00a0 Its a greedy problem.<\/p>\n Start off with having used none of the provided values.\u00a0 With this you can make 0.\u00a0 Take the smallest unused provided value, if it is what you can currently make + 1, or smaller, add c * that value to what you can currently make.\u00a0 Otherwise add c * (what you can currently make + 1) and increment the extra values you had to have counter.\u00a0 Repeat until you can make V or higher.<\/p>\n One corner case to be careful of for large input. While the target V can never be more than 1 billion, and the provided values are always small, the extra values you have to add can be very closer to 1 billion, so adding c * extra value can overflow a 32 bit integer very easily.<\/p>\n","protected":false},"excerpt":{"rendered":" Three easier questions this round, although I have to say I found the ‘easy’ question the hardest… Advancing cut-off was either of the first 2 problems and the smalls from both the others and a few minutes to spare.\u00a0 Solving the 3rd problem and smalls of the other was worth 1 more point and ~400 … Continue reading GCJ15 R1C<\/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],"tags":[],"class_list":["post-795","post","type-post","status-publish","format-standard","hentry","category-code-competitions"],"_links":{"self":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/795","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=795"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/795\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=795"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=795"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=795"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}