So like last year, I scraped through in R1A with only 1 out of the available questions solved. 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… *sigh*
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?
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…
First we can rule out a couple of obvious scenarios – if Pg is 100% then Pd must be 100% or something is wrong. Similarly Pg of 0% implies Pd of 0% or again we fail. 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. In this case every value of Pd is valid. In that case all that remains is to consider whether Pg is valid…
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. This applies regardless of whether the number of games today was 100, or much smaller.
Final scenario is where the inclusive upper bound doesn’t include 100. This is less than 100 options to step through, so why not! For each value of n, we check whether n*Pd is an integer, or similarly, whether n*Pd = 0 mod 100. If we find a match the situation is plausible, if not then the situation is invalid.
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. However when I went to run my code on the large input file, it crashed! I hadn’t noticed exactly how big the upper bound max was, and was using int.Parse.
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. 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. 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?
A2) A very wordy question (pun not intended!), and for the longest time the question text itself was self-contradicting. Large input had a dictionary size of 10k words and up to 100 permutations to try for each dictionary. Maximum of 10 test cases meant that it wasn’t entirely insane though. 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.
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. So I started implementing. The approach is not to try each possible word choice and simulate, but instead to simulate all possible word choices at once.
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.
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. The responses (which can be represented by a bit field as maximum word length is small) break the words into groups. 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. 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. 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. Repeat for each different word length, and select the best of the best.
Keeping track of the score for each group is fairly easy, first group has score 0. 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. 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.
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. Except it didn’t produce the correct answers. I was confused, I hunted for potential issues – only found 1, and it was still wrong. 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. But I made copious mistakes in the brute force code – even though it was theoretically simpler, I got it wrong in multiple ways. After the competition finished, I still had to fix 3 more bugs before it passed the practice small input. At this point I compared it to my proper implementation, and found a specific test case to focus on. Turned out that my proper implementation was actually much better, it hadn’t suffered from any of the bugs of the brute force code. 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. Except my loop stopped at 9, oops!
Q3) You are playing a special single-player card game. 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. You start with 1 turn remaining until the end of the game, but each card has 3 values. T, S and C. 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. 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.
A3) This was the ‘hard’ problem and I definitely agree it was far harder than Q2. Only 3 people got out the large input, and barely over 100 got the small.
The key difference between small and large was of course the limits imposed. In the small input, C is at most 1, where as in the large input C could also be 2. I think with the C is at most 1 limit, the problem can be more obviously turned into a dynamic programming problem…
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. Firstly it is worth realizing that you should always play a T>0 card if you have one available. Since they give more turns, there is no downside to playing them. Next is the C=0 cards. For a given maximal solution, any C=0 cards (which are not T>0 cards) can be reordered to the end. Furthermore amongst C=0,T=0 cards you will always want to play them in largest score first order. 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.
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. Finally this gives enough limitations on the search for an ideal solution. 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. The transitions on this graph always increase one or more of these 5 values, so it is an acyclic directed graph. 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.
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’. 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.
Recursion with memotization will solve the problem at this point. 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. Memotization to ensure the runtime is fine.