Dang it, you had this brainwave 3 hours before me. On 12 May 2015 04:09, "Joseph DeVincentis" <[email protected]> wrote:
> Today while I was trying to explain this problem to a friend, I realized > there was a simpler solution. No looping through letters typed or tracking > states is necessary. To find the expected value, you just need to add up > the number of sequences of S keypresses which have the target string > starting at position 1, those which have the target string starting at > position 2, etc. and divide by the K^S possible sequences. This counts some > strings multiple times, but in exactly the way that we want; every > occurrence of the target string, including overlapping ones, will be > counted. > > The number of sequences with the target string in a given position is just > the product of the number of keys containing each letter in the target > string, for those positions, times K^(S-L) for the other positions which > can be any key whatsoever. > > There are S-L+1 positions where the target string could start. So if X is > the product of the number of keys containing each letter of the target, > then the expected number of matches is X*(S-L+1)*K^(S-L)/K^S, or simply > X*(S-L+1)/K^L. > > > > On Sun, May 10, 2015 at 8:40 PM, Joseph DeVincentis <[email protected]> > wrote: > >> 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/CAMAzhzjCC-ttp_u_%3DEvyAhhriyftfbT0SK2R4DqwzwYTJgXN_A%40mail.gmail.com > <https://groups.google.com/d/msgid/google-code/CAMAzhzjCC-ttp_u_%3DEvyAhhriyftfbT0SK2R4DqwzwYTJgXN_A%40mail.gmail.com?utm_medium=email&utm_source=footer> > . > 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/CAECKw-PVu5rXB%3DvDvjRW25PrR0vw8DUoGZ71%2BbQiwR9%3DdT247g%40mail.gmail.com. For more options, visit https://groups.google.com/d/optout.
