hmnn about round 1A: A: Bruteforce/implementation, if you do some caching or if you do a precalculation, you can pass the large input as well.
B: This was a nice problem in my opinion, unless the idea was done before in some other contest and that's the reason a lot of people thought it was obvious. You'd have to do a Dijkstra. The main objective is to get rid of the 20e7 factor from the state. This is easier than it seems, imagine that the graph considers only your position in the city, and not the time, if you solved with Dijkstra, you would always get to each corner as soon as possible. Since for each corner there is only one time to consider, you can easily calculate the time you would have to wait before being able to cross. Add this waiting time to the "distance" for the next node. C: Let's say you already got x unique cards. If you buy a deck of N cards, then you can increase your unique card count by 0, 1, 2, .... , min( C-x, N) cards. Let's call P_i the probability that you'll get i cards, then we can get the result as: F(x) = 1.0 + p0*F(x+0) + p1*F(x+1) + ... + pk*F(x+k) Where k is min(C-x, N) Now, you just have to solve the equation: (1 - p0)*F(x) = 1.0 + p1*F(x+1) + ... + pk*F(x+k) F(x) = ( 1.0 + p1*F(x+1) + ... + pk*F(x+k) ) / (1 - p0) Do notice that F(N) = 0.0 You can reduce the execution time by using memo-ization or dp on this recursion. There's just the subproblem of calculating the probabilities. The probability would be: (combinations of C elements taken in groups of N that come with exactly i new cards from j special cards) / ( Combinations(C,N) ) The top of the fraction can be done like this: Combinations(j , i) * Combinations(C-j , N-i) Because you will have to take i cards from the group of j special cards, and take the remaining N-i cards from the group of non-special cards (C-j) So each of the probabilities p_i for is: p_i = ( Combinations( C-g, i) * Combinations(g , N-i) ) / Combinations (C,N) ) You can calculate Combinations() using the pascal triangle, remember to use 64 bits integers in this triangle... On Sep 11, 11:52 pm, Maxim Katsev <[email protected]> wrote: > Hi All, > > Is there going to be something like an editorial for Code Jam? Or does > anyone know independent reviews of Code Jam problems? > > Max --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "google-codejam" group. To post to this group, send email to [email protected] To unsubscribe from this group, send email to [email protected] For more options, visit this group at http://groups.google.com/group/google-code?hl=en -~----------~----~----~----~------~----~------~--~---
