Блог пользователя ganeshk2

Codechef December Cookoff CHEFNUMK
Автор ganeshk2, история, 8 лет назад, По-английски

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 ?

  • Проголосовать: нравится
  • +19
  • Проголосовать: не нравится

»
8 лет назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

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].

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +6 Проголосовать: не нравится

    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 !

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
      ← Rev. 2   Проголосовать: нравится +5 Проголосовать: не нравится

      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.

      → Ответить
      • »
        »
        »
        »
        8 лет назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        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 ^_^

        → Ответить