Would you mind if you can share your code here? You mentioned you use the Y numbers to generate the expected cost. I am not sure if that's possible to be done in O(N) without looking at your implementation.
Also the analysis does *not *suggest that O(N^2) is the *best *solution. It just give you *a *solution that is easy to implement and still fit the time constraint. 在2021年4月6日星期二 UTC-7 下午1:28:32<Sergii Olshanetskyi> 写道： > 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 google-code@googlegroups.com. To unsubscribe from this group, send email to google-code+unsubscr...@googlegroups.com. 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 google-code+unsubscr...@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/google-code/e74fefc6-95bd-491e-91b0-006eeaff2960n%40googlegroups.com.
