retr0coderxyz's blog

Help Required CSES Distinct Colors
By retr0coderxyz, history, 5 years ago, In English

Hello guys,

I was trying to solve Distinct Colors: link.

I did a naive solution which obviously led to TLE.

TLE

I saw various solutions that use BIT. But I cant assimilate why BIT works here, what BIT represents here (for e.g. in case range sum query BIT keeps track of cummulative frequency.)

It would be great if someone tells some trick how to use BIT for various other purposes too.

Thanks!

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

Comments Comments (11)
| Write comment?
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

It's simple. Simply transform your tree into an array by doing a pre-order traversal. Then, notice that a subtree corresponds to a subarray. Now, you just need to solve the problem of finding the number of distinct elements in a subarray (which is actually SPOJ DQUERY).

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

    Thanks buddy, I have done till subarray part. epitome of this question lies around finding distinct numbers within range ( which I have used map and binary search to check here). So I need help in that part.

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

      There are several ways to solve the problem for the array version.

      The most straightforward is to use Mo's algo.

      Since you asked for fenwick tree solution specifically, I shall tell you something — it is not so straightforward (you need a clever trick).

      Segment tree with a vector in each node provides you with a much more straightforward solution.

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

        Can you elaborate on the segment tree part, Thanks — noob here :(

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

          Hint: (Sweeping from left to right), for each color in your array, store the index of the next occurence of that color. If there is none, use infinity.

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

      Actually, you can also solve this without flattening the tree. But that's a bit advanced for now...

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

LanceTheDragonTrainer gave some valuable insights, but still its not enough for me to pick up. I honestly don't understand "(Sweeping from left to right), for each color in your array, store the index of the next occurence of that color. If there is none, use infinity." works or what to do after that. It will be great if anybody could explain me in a well detailed manner out of your busy time, I would be really grateful.

Thank you!

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

    Notice that each distinct color will have only one index where the value of next_element is larger than your right end.

    → Reply