So like last year, I scraped through in R1A with only 1 out of the available questions solved.\u00a0 But this year I was a bit faster, so I got 655th rather than 800+.<\/p>\n
I was actually very close to a respectable score – an off by 1 which took me almost 2 hours to find… *sigh*<\/p>\n
Q1) Given an inclusive upper bound on the number of games played today (and at least 1 game was played), with an ‘exact integer’ percentage win rate for today of Pd and an ‘exact integer’ percentage win rate for all time Pg, is the scenario even possible?<\/strong><\/p>\n A1) The large inputs put the inclusive upper bound at 10^15 – which seemed daunting at first, but fairly quickly I discovered a short cut which I thought made it irrelevant…<\/p>\n First we can rule out a couple of obvious scenarios – if Pg is 100% then Pd must be 100% or something is wrong.\u00a0 Similarly Pg of 0% implies Pd of 0% or again we fail.\u00a0 For me the next thing I realized was that if the inclusive upper bound was >= 100 then the option of 100 is available – an important option in the presence of percentages.\u00a0 In this case every value of Pd is valid.\u00a0 In that case all that remains is to consider whether Pg is valid…<\/p>\n Pg being valid is actually very simple, so long as it isn’t 0 or 100, we can add so many games prior to today, that today becomes irrelevant, other than to serve as a tiny modulation factor which needs to be compensated for to make Pg an exact integer.\u00a0 This applies regardless of whether the number of games today was 100, or much smaller.<\/p>\n Final scenario is where the inclusive upper bound doesn’t include 100.\u00a0 This is less than 100 options to step through, so why not!\u00a0 For each value of n, we check whether n*Pd is an integer, or similarly, whether n*Pd = 0 mod 100.\u00a0 If we find a match the situation is plausible, if not then the situation is invalid.<\/p>\n So as I alluded to earlier the upper bound max of 10^15 isn’t a problem, 3 if statements take care of all scenarios >= 100.\u00a0 However when I went to run my code on the large input file, it crashed!\u00a0 I hadn’t noticed exactly how big the upper bound max was, and was using int.Parse.<\/p>\n Q2) In a variant of hangman where there is no way to lose, just a score that gets worse the more useless guesses you make, you are choosing words from a dictionary and your friend is playing to a specific strategy.\u00a0 You want to choose the word which will give your friend the worst score – if there are equal options the first word in the dictionary is the one you take.\u00a0 If the strategy can be described by a permutation of the alphabet, where each letter is guessed in turn unless there are no dictionary words which match the previous guesses which contain the letter, in which case the letter is skipped, given a list of these permutations and the dictionary, what word should you select?<\/strong><\/p>\n A2)\u00a0 A very wordy question (pun not intended!), and for the longest time the question text itself was self-contradicting.\u00a0 Large input had a dictionary size of 10k words and up to 100 permutations to try for each dictionary.\u00a0 Maximum of 10 test cases meant that it wasn’t entirely insane though.\u00a0 A brute force attack requires iterating over the dictionary, for each entry in the dictionary – and performing this multiple times even – it was clearly not going to work in time O(D^2*P) is billions upon billions of operations for the large input.<\/p>\n I spent a while considering whether there was some dynamic programming approach but eventually came to the conclusion that I was just trying too hard, and that an O(D*P) solution would be okay even with a rather high constant multiplier.\u00a0 So I started implementing.\u00a0 The approach is not to try each possible word choice and simulate, but instead to simulate all possible word choices at once.<\/p>\n At this point I should mention something which possibly isn’t clear from how I wrote the question above, which is that since the first thing you do in hangman is to write down the full list of blanks, your friend immediately knows the length of the word, so whatever word you select your friend will only consider words of that length.<\/p>\n Put all the words of a specific length in a list, then going through each one determine what its response to the current letter being tried in the strategy.\u00a0 The responses (which can be represented by a bit field as maximum word length is small) break the words into groups.\u00a0 Each of these groups is self consistent – if any of those words had been the originally selected word, the group would be same set of words that your friend would consider as still plausible and the basis of the strategy.\u00a0 Once each group is created you can move to the next letter in the strategy, applying it to each group, splitting it into potentially even more groups which remain self consistent.\u00a0 All that remains is to keep track of the score for each group, and then select the best score once you get to the end.\u00a0 Repeat for each different word length, and select the best of the best.<\/p>\n Keeping track of the score for each group is fairly easy, first group has score 0.\u00a0 If a group response to a letter by splitting into 2 or more groups, and one of those groups contains words that do not have that letter, that group has its score increased by 1 compared to the input group.\u00a0 Key thing to notice here is that if the response of a group to a letter is to not split, and the words do not contain the letter, the score doesn’t go up – because this corresponds to the scenario where the strategy is to skip a letter, because none of the plausible words contain the letter.<\/p>\n I actually had this all written with almost an hour to go, I even took the time to generate the maximal input file to make sure it wasn’t too slow.\u00a0 Except it didn’t produce the correct answers.\u00a0 I was confused, I hunted for potential issues – only found 1, and it was still wrong.\u00a0 With 30 minutes to go I decided I would write the brute force implementation, just get the points for the small input or if I had time, maybe use it to work out why the proper implementation didn’t work.\u00a0 But I made copious mistakes in the brute force code – even though it was theoretically simpler, I got it wrong in multiple ways.\u00a0 After the competition finished, I still had to fix 3 more bugs before it passed the practice small input.\u00a0 At this point I compared it to my proper implementation, and found a specific test case to focus on.\u00a0 Turned out that my proper implementation was actually much better, it hadn’t suffered from any of the bugs of the brute force code.\u00a0 Just a single mistake, iterating over the dictionary of grouping words by length, I hadn’t used foreach, but had instead just iterated over the possible lengths, 1 to 10.\u00a0 Except my loop stopped at 9, oops!<\/p>\n Q3) You are playing a special single-player card game.\u00a0 You have at least 1 card in hand at the start, and the rest in the deck – with a total of up to 80 cards.\u00a0 You start with 1 turn remaining until the end of the game, but each card has 3 values.\u00a0 T, S and C.\u00a0 T is the number of additional turns you gain by playing it, S is the score you get by playing it, and C is the number of cards you draw from the deck, if you play it.\u00a0 You actually know the exact order and contents of both your hand and the deck before you start – determine the maximum score you can achieve.<\/strong><\/p>\n A3)\u00a0 This was the ‘hard’ problem and I definitely agree it was far harder than Q2.\u00a0 Only 3 people got out the large input, and barely over 100 got the small.<\/p>\n The key difference between small and large was of course the limits imposed.\u00a0 In the small input, C is at most 1, where as in the large input C could also be 2.\u00a0 I think with the C is at most 1 limit, the problem can be more obviously turned into a dynamic programming problem…<\/p>\n I certainly had to look up the answer here, but the key comes from determining properties of the ideal answer and using those to limit your search space, which would otherwise be huge.\u00a0 Firstly it is worth realizing that you should always play a T>0 card if you have one available.\u00a0 Since they give more turns, there is no downside to playing them.\u00a0 Next is the C=0 cards.\u00a0 For a given maximal solution, any C=0 cards (which are not T>0 cards) can be reordered to the end.\u00a0 Furthermore amongst C=0,T=0 cards you will always want to play them in largest score first order.\u00a0 All that remains is to determine the order of playing the C=1 and C=2 (T=0) cards in between, if they are played at all.<\/p>\n The final and most important trick here is to determine that if you play 2 C=1 or 2 C=2 (T=0) cards, they can be reordered such that you play the one which arrives in your hand first, first.\u00a0 Finally this gives enough limitations on the search for an ideal solution.\u00a0 So we have a graph with status ‘index in deck of last drawn card’, number of turns remaining (capped at 80, since over 80 is pointless), the first C=1 card we might yet play, and the first C=2 card we might yet play and the first T>0 card we might yet play.\u00a0 The transitions on this graph always increase one or more of these 5 values, so it is an acyclic directed graph.\u00a0 Since there are no cycles you can fairly easily search this graph for the ‘longest path’ from the source, where each edge is a score and each vertex has an end bonus related to maximal use of remaining turns to play available C=0 cards.<\/p>\n To enumerate the possible transitions we have ‘play a T> card’, ‘play a C=1 card’, ‘play a C=2 card’, ‘decide to never play the current C=1 card’, ‘decide to never play the current C=2 card’.\u00a0 A performance improvement option here is to remove the C=1\/C=2 card options if there is a play a T>0 card option, since we know playing T>0 first is never a bad thing (Or alternatively, get rid of all T>0 from the status info and state transitions – presume to have used all the could be in the hand as part of every transition, and in determining the initial status). Use a DFS to generate the graph, as it is going to be sparse and maximum recursion is 80. Also add backwards pointing links because they will be useful for determining the maximum length.<\/p>\n Recursion with memotization will solve the problem at this point.\u00a0 Starting from the implicit end node which every node connects to via the play of playable C=0 cards, recur across each back pointing link added before, using the edge weight (score increase due to that action) to build upon the result of the recursion.\u00a0 Memotization to ensure the runtime is fine.<\/p>\n","protected":false},"excerpt":{"rendered":" So like last year, I scraped through in R1A with only 1 out of the available questions solved.\u00a0 But this year I was a bit faster, so I got 655th rather than 800+. I was actually very close to a respectable score – an off by 1 which took me almost 2 hours to find… … Continue reading GCJ11 R1A<\/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-336","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\/336","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=336"}],"version-history":[{"count":0,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=\/wp\/v2\/posts\/336\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=336"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=336"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.themissingdocs.net\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=336"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}