daihan's blog

KOIREP — Representatives Sliding Window problem
By daihan, 8 years ago, In English

I am trying to find out the logic to solve this problem , KOIREP — Representatives , i tried for 7 days still get no idea to solve it .

Can anyone please tell me how can i effeciently solve it ? Problem tagged with Sliding window alias two pointer .

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

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

This could be solved using two pointers. Firstly sort all numbers and for each of them remember the group ID to which it belong to. Then for each position l in sorted array we can find the smallest possible r such as there are n different groups on the segment from l to r. Time Complexity : O(n * m * log(n * m));

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

    awesome thanks

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

      You're welcome! :)

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

        how can I efficiently implement "distinct group from index L to R "?. I was thinking that inserting group no. into set, set size will tell me number of distinct group from L to R, I will erase a data from set if the frequency of that data from index L to R becomes 0. But inserting into set complexity is nlog2n.

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

          You can just keep a cnt[] array where cnt[i] tells you the number of elements of the i'th Group ID. Now keep a variable answer. Whenever you move a pointer update cnt[i] i.e. if it comes inside the sliding window then increase otherwise decrease it. If cnt[i] becomes one then answer++ and if cnt[i] becomes 0 then update answer--. This is a common technique and it it will be beneficial to get familiar with it.

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

            Can you please share your solution?

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

              My approach is similar to what mentioned above. You can see my code here.

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

      I did it storing pointers to every class and moved only that pointer which has least ability(made sure I sorted every class) if you want I can share my solution.

      → Reply