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 .
→ Обратите внимание
До соревнования
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
37:07:12
Зарегистрироваться »
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
37:07:12
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3823 |
| 3 | Benq | 3738 |
| 4 | Radewoosh | 3633 |
| 5 | jqdai0815 | 3620 |
| 6 | orzdevinwang | 3529 |
| 7 | ecnerwala | 3446 |
| 8 | Um_nik | 3396 |
| 9 | ksun48 | 3390 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | cry | 167 |
| 2 | Um_nik | 163 |
| 3 | maomao90 | 162 |
| 3 | atcoder_official | 162 |
| 5 | adamant | 159 |
| 6 | -is-this-fft- | 158 |
| 7 | awoo | 157 |
| 8 | TheScrasse | 154 |
| 9 | Dominater069 | 153 |
| 9 | nor | 153 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 22.11.2024 04:27:48 (k1).
Десктопная версия, переключиться на мобильную.
При поддержке
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));
awesome thanks
You're welcome! :)
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.
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.
Can you please share your solution?
My approach is similar to what mentioned above. You can see my code here.
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.