Hello Sergii, I am sorry you misunderstood my words. I am not asking you or challenging you to verify your solution works in O(N). I am sure it does. You don't need to convince me. I am just too curious to see your implementation myself because I couldn't come up with one and I did not fully understand what you are saying in your approach. By looking your code, maybe I can get a bit more of your idea from your code directly.
If you don't want to share any details of your implementation, its fine. P.S. Now I kind of understand how to construct those Y numbers thanks to Ronald's analysis. 在2021年4月14日星期三 UTC-7 上午5:21:25<Sergii Olshanetskyi> 写道: > > @ 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/f544da8b-6d1f-45ee-81b4-e6f3b8cd8619n%40googlegroups.com.