Hi, It is explicitly *not* our policy to require the smallest complexity solution for every problem. In many cases, the main idea or ideas of the problem get you to some solution, and then additional technical steps can make that smaller. Sometimes those technical steps are not interesting relative to the rest of the problem, or put an otherwise approachable problem unnecessarily out of reach for too many people, or make it too long to implement for little value (the contests are time limited after all). We sometimes <https://codingcompetitions.withgoogle.com/codejam/round/000000000043580a/00000000006d0a5c#analysis> mention this fact in the analysis, but sometimes we don't, as you've noticed.
One thing about the name "best" solution. You may want to start calling it "more efficient" or "smaller complexity". I would call the best solution to the one that solves the problem as posed (which includes time limits) with the best tradeoff between risk of getting hidden test sets wrong and time spent (since time not spent can be used on other problems). If you were just curious, we did know there were more efficient solutions in this problem. I remember multiple cases of people coming up with solutions we did not think about to problems, but I can't remember a case in which someone found a solution in a complexity we tried and failed to accomplish. Of course, it could have happened without me noticing, or I may be not remembering, or it could have happened before I started working for Code Jam. We do have more than just one person looking at problems, and for longer than 2.5 hours :). Best, Pablo On Wed, Apr 14, 2021 at 5:21 AM Sergii Olshanetskyi < sergii.olshanets...@gmail.com> wrote: > > @ 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 > <https://groups.google.com/d/msgid/google-code/fb3c8baa-499a-4284-bd69-6e13abfc2619n%40googlegroups.com?utm_medium=email&utm_source=footer> > . > -- -- 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/CANa5jcDz2BvWTdQB4aTJmrEZj0BZssDNHQXiQxDNZhqO3zJ1Xw%40mail.gmail.com.
