murugappan_s's blog

June Long Challenge cloning problem Deterministic solution
By murugappan_s, history, 8 years ago, In English

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

  • Vote: I like it
  • +2
  • Vote: I do not like it

»
8 years ago, # |
  Vote: I like it +4 Vote: I do not like it

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.

→ Reply
  • »
    »
    8 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Just now saw your solution and to be frank it is very much precise compared to my solution.Thanks for the help.

    → Reply
    • »
      »
      »
      8 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      My pleasure :)

      → Reply
      • »
        »
        »
        »
        7 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Your solution looks like q*nlogn. How did it get AC? Please explain to me.

        → Reply