Always hated Bayes formula - meaning I always needed to draw a picture fist before I could properly used it. Maybe this is the cause of my problem with "Good Luck".
So, I read through official analysis but still couldn't get to the right answer. I'll explain what I did and maybe somebody can point at what I did wrong: a) in preprocessing stage I created a big-big table (actually in form of Dictionaries). All probabilities in this table sum up to 1.0 (in reality 0.999994 something, due to rounding issues). Total probability of 1.0 is split into separate number for each (sequence, number) tuple. Sequence meaning all potential sequences (18K+) and number - all number which can be potentially created out of those sequences. Formula for calculating sequence probability is (example): 2 2 2 3 3 3 4 4 4 5 5 6 12! / 3! * 3! * 3! * 2! * 1! = 1,108,800 potential ways to draw over 12^7 = 13,841,287,201, divided: 8.01e-05 - this is probability of such sequence appearing. Then I go through all potential numbers from this sequence (4,096 of them in total, with 1 not so interesting). For each number I calculate probability and multiply it by probability of the sequence. This is how I get to (sequence, number) table where all numbers sum up to one. Surprisingly, Python is able to do it in less then one minute. I expected much worse. b) Next, we get to the numbers themselves. Having received N numbers as the input: - it is obvious, that each number can be a result of limited number of sequences. So first thing to do is to get the intersection of sequences for all numbers. If we are lucky we will end up with one sequence (this is what happens more than 50% of the time in first small input). In this case answer is obvious. But in many cases we will end up with as many as 500-600 sequences. So here comes the question of probabilities - which sequences is better than the other. To decide on that, I come back to my probabilities array. I pick all (sequence, number) probabilities from the intersection. The fact that they are in intersection means that all sequences I search through can generate all numbers I am interested in. No I need to properly combined probabilities to see which sequence is most likely to produce this specific set of numbers. I tried doing it in different way but nothing works. I think this is where I make some kind of error. Can anybody guide me in the right direction? -- 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/msg/google-code/-/hkPDUZttzmIJ. For more options, visit https://groups.google.com/groups/opt_out.
