[code jam] Re: Code Jam Qualification Round 2021 - "Reversort Engineering" has complexity O(N) instead of O(N^2)

Hi Sergii, Thanks very much for sharing! I think your solution is very similar to Ronald's idea. I am now very confident that it is solvable in O(N) space and time and the implementation is much simpler than I imagined. 在2021年4月30日星期五 UTC-7 上午10:10:00 写道： > Hi

[code jam] Re: Code Jam Qualification Round 2021 - "Reversort Engineering" has complexity O(N) instead of O(N^2)

Hi porker2008, No problem at all. Please see the code below. Just a disclaimer - during code jams I am creating the worst code ever (due to the time limit), so please be kind to me :) So again, the idea is to create the 'worst' solution with last elements + one more iteration to get the

[code jam] Re: Code Jam Qualification Round 2021 - "Reversort Engineering" has complexity O(N) instead of O(N^2)

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

Re: [code jam] Re: Code Jam Qualification Round 2021 - "Reversort Engineering" has complexity O(N) instead of O(N^2)

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

[code jam] Re: Code Jam Qualification Round 2021 - "Reversort Engineering" has complexity O(N) instead of O(N^2)

@ 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

[code jam] Re: Code Jam Qualification Round 2021 - "Reversort Engineering" has complexity O(N) instead of O(N^2)

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