June Long Challenge cloning problem Deterministic solution

Правка en1, от murugappan_s, 2017-06-16 23:42:38

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. :)

Теги codechef, longchallenge, june, cloning

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en1 Английский murugappan_s 2017-06-16 23:42:38 1124 Initial revision (published)