Блог пользователя murugappan_s

Автор murugappan_s, история, 7 лет назад, По-английски

This month's codechef long challenge had a great set of problems. One problem was cloning(https://www.codechef.com/problems/CLONEME/).

I couldn't solve it during the contest,but upsolved it just now.

I did it finding prefix square sums and prefix sum of the input and used a mergesort tree.To resolve collisions for ranges which have same prefix square sums and prefix sums,I had to do a lot of collision resolution work(computing various prefix power sums).

I find the pairs of numbers which differ in the intervals.If that count of pairs is greater than 1,we can answer them easily else find whether they occur at same position by find number of elements strictly lesser than and less than the value,then answer them. Here is my submission : https://www.codechef.com/viewsolution/14267198

Is there a deterministic solution or any better solution which has less collision?? If there is any good editorial please provide the link. Thanks in advance.

Please don't down-vote before reading.(sorry if it was harsh).Once again thanks in advance. :)

  • Проголосовать: нравится
  • +2
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

https://www.codechef.com/viewsolution/14268263 I have used just 3 arrays. Prefix sum, prefix sum of squares and prefix sum of power 3/2. No collisions occurred.