The analysis for the problem suggest O(N^2) as the best solution. However, it can be solved in O(N).
The idea is to break the expected array into two parts of size X and Y: 1) X are the numbers can be put at first position without any permutations [ 1 2 3 4 ..... ] 2) Y are the number that have to be at specific positions to get the needed complexity [ 12 3 4.... 9 11 10 8] It is possible to create the most costly solution for N digits, by putting each number at the worst position. For instance, the most costly solution for N = 5 would be: 2 4 5 3 1. My approach is to use Y numbers to generate the expected cost, and numbers X are just printed as they are. My submission worked. I also tested in locally on N = 10^6. I am curious why didn't the Google Code Jam team mentioned O(N) solution in the analysis section?.. -- -- You received this message because you are subscribed to the Google Groups Code Jam 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 https://groups.google.com/d/forum/google-code?hl=en --- 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 view this discussion on the web visit https://groups.google.com/d/msgid/google-code/4e97cc70-490c-413e-8803-4d73286153f7n%40googlegroups.com.
