June Long Challenge cloning problem Deterministic solution

Revision en1, by 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. :)

Tags codechef, longchallenge, june, cloning

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en1 English murugappan_s 2017-06-16 23:42:38 1124 Initial revision (published)