I was already qualified, so I didn't wake up at 5 this morning to solve this round, but I just completed all the problems in practice.
For typewriter monkey, the maximum matches is easy. Find the longest initial substring which matches a final substring of the target, shorter than the whole string. This is the maximum they can overlap, and L minus this length is how many more letters you have to add to the initial L for each subsequent match. I used a dynamic programming strategy to calculate the number of expected matches. At each position p in the string, keep track of how many of the k^p possible strings the monkey could have typed end with the correct 1 first letter, 2 first letters, ..., L-1 first letters of the target. It is possible that a single state matches more than one case; for instance, if the target string was ANAGRAM, and the monkey has typed BANA, he has both 1 correct letter and 3 correct letters for two different possible ways to match the word. But these overlaps are fixed; for this example, the monkey will always have 1 correct every time he has 3 correct. So there are at most L (100) states at any given time, including 0 correct. For each letter typed, go through the list of states from the previous letter, and find all the letters which will extend any of the strings, and the new set of initial substrings of the target which will be matched after that letter is typed. For the example above, if the monkey types G, he now has 4 correct letters, if N, 2 correct letters, and if A, 1 correct letter. If he types any other letter he has no correct letters. For each of these cases, multiply the number of ways the previous state was reached by the number of keys with that letter on the keyboard to get the number of ways to arrive at the new state. Store this in the set of states for the next iteration, adding it to the existing value if there was another way to get to this state. If the new state includes L correct letters (a complete match), don't include this in the new state, but add this to a running total of complete matches to the target string. Since this will be a match for all possible letters the monkey can type after this, the number you need to add is the number of ways to get here times K^R, where R is the number of remaining letters the monkey can type. When you reach the end of the string of S letters, divide the total number of matches by K^S to get the expected number of matches. On Sun, May 10, 2015 at 12:49 PM, Vincent Le Quang < [email protected]> wrote: > For the question Round 1C 2015 B, (typewriter monkey), I think there must > have been an elegant non-brute force method. But with the pressure of time > I just decided to just go brute force and it was only good to solve the > small data-set. (meaning trying out every typing combinations and counting > probabilities). > > How did you guys manage to solve the large data-set? > > Thanks. > > -- > You received this message because you are subscribed to the Google Groups > "Google Code Jam" group. > To unsubscribe from this group and stop receiving emails from it, send an > email to [email protected]. > To post to this group, send email to [email protected]. > To view this discussion on the web visit > https://groups.google.com/d/msgid/google-code/2d98a18c-d205-4ca1-b41d-5d40bf9cf390%40googlegroups.com > . > For more options, visit https://groups.google.com/d/optout. > -- You received this message because you are subscribed to the Google Groups "Google Code Jam" group. To unsubscribe from this group and stop receiving emails from it, send an email to [email protected]. To post to this group, send email to [email protected]. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/CAMAzhziXtWJZKijJe3fzdf-WAXGF5ebThMdQo%3D99K%2Ba4gDPeFA%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
