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 <https://ideone.com/lu7o2W> is much simpler than I imagined. 在2021年4月30日星期五 UTC-7 上午10:10:00<Sergii Olshanetskyi> 写道： > 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 desired complexity. > > for test_case_number in range(int(number_of_cases)): > input_params = raw_input().split(" ") > N = int(input_params[0]) > C = int(input_params[1]) > > min_value, max_value = get_boundaries(N) > > if C < min_value or C > max_value: > print("Case #{}: {}".format(test_case_number + 1, "IMPOSSIBLE")) > continue > > current_C = C > > array = [-1] * N > > start_index = 0 > last_index = len(array) - 1 > > current_n = start_index + 1 > > while start_index < last_index: > min_v, max_v = get_boundaries(N - current_n) > > if current_C - 1 < max_v: > array[start_index] = current_n > current_n += 1 > start_index += 1 > current_C -= 1 > continue > > spooky_start = start_index > array[spooky_start] = current_n > > start_index += 1 > current_n += 1 > > start = False > > while current_n <= N: > if start: > array[start_index] = current_n > start_index += 1 > else: > array[last_index] = current_n > last_index -= 1 > > current_n += 1 > start = not start > > next_min_index = current_C - max_v > > swap(array, 0, next_min_index - 1) > > result = ' '.join(str(i) for i in array) > > # actual = solve(array) > # assert actual == C > > print("Case #{}: {}".format(test_case_number + 1, result)) > > On Sunday, April 25, 2021 at 11:27:51 AM UTC-4 porker2008 wrote: > >> 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/b3483347-b7c2-4a67-b9e1-e58523f09470n%40googlegroups.com.
