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. :)
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.
Just now saw your solution and to be frank it is very much precise compared to my solution.Thanks for the help.
My pleasure :)
Your solution looks like q*nlogn. How did it get AC? Please explain to me.