ganeshk2's blog

Codechef December Cookoff CHEFNUMK
By ganeshk2, history, 7 years ago, In English

I recently attempted this problem https://www.codechef.com/COOK77/problems/CHEFNUMK
using MO's algorithm (offline sqrt decomp) but got TLE. Almost everyone used the same method to reach AC. Changing values of blocks affects the complexity is known, and i tried a few values. Comparing the following code
https://www.codechef.com/viewsolution/12297863
with my code
https://www.codechef.com/viewsolution/12299180
doesn't show much difference, help ?

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

»
7 years ago, # |
  Vote: I like it +24 Vote: I do not like it

You don't have to keep a BIT or any type of structure for answering. Just keep an array nr[i] = number of values in [l,r] at the actual step which have frequencies >= i. It's pretty easy to see how this array changes when you move with left or right.

To give you an example, if you move right to right + 1 and a[right + 1] = x then nr[freq[x] + 1]++ and freq[x]++. freq[x] = frequency of value x.

Having this array is pretty easy to answer the question. Is number of different values in [l,r]-nr[k + 1].

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

    True, the logn factor will affect the complexity and i should have given some more thought to it. Though what i wanted to know is many submissions passed with
    (N+Q)sqrtN*logN complexity in under 0.5 secs! There should be some other constants in play !

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
      ← Rev. 2   Vote: I like it +5 Vote: I do not like it

      True, I used MO + segment tree but it didn't pass TL. Though fenwick is faster than segment tree but still it would be great if some one can show an AC solution with segment tree.

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

        Good day to you,

        Well here is a "Segment Tree + MO" solution, but not sure if it is what you wanted (it is kinda slower than FW so it has "a few" optimizations {the code — not the ST})

        Have nice day ^_^

        → Reply