@ porker2008 I did *not *ask to verify if my solution works in O(N) - I know it *does. *And people working at Google (not from the Code Jam team - as those never got back to me) confirmed that it *does*. I only mentioned the idea behind it the implementation.
My question was "I am curious why didn't the Google Code Jam team mentioned O(N) solution in the analysis section?.." , meaning if the Google Code Jam team knew that there is a much faster solution - why didn't they mention it. I will get it if they say that is not trivial to code. If they didn't know - that is a whole separate story... "Also the analysis does *not *suggest that O(N^2) is the *best *solution." So you are saying that the analysis contains *a *random solution which could be much worse than the best one? And it is a common theme for the analysis section not to include the best solution? On Thursday, April 8, 2021 at 3:41:22 PM UTC-4 porker2008 wrote: > 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/fb3c8baa-499a-4284-bd69-6e13abfc2619n%40googlegroups.com.
