Can this problem : Bounded distinct be solvable using two pointer ? If yes what is the logic ? I implemented it with two pointer but code become very much complex . My code . Getting WA for this code .
№ | Пользователь | Рейтинг |
---|---|---|
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 |
Can this problem : Bounded distinct be solvable using two pointer ? If yes what is the logic ? I implemented it with two pointer but code become very much complex . My code . Getting WA for this code .
Название |
---|
I think you're somewhat on the right track based on what I could understand from your code. Just try to make it a lot simpler. What are your two pointers? What should be the state at the end of each iteration?
The simplest idea I could think of is to find the largest valid subarray for each starting index. Left pointer would be the starting index and at each iteration we move the right pointer until we find a duplicate (or hit either the end of the array or maximum allowed interval length) and count the number of valid intervals starting from this index. Sample implementation.
I wasted most of the time in contest for a small mistake in this problem. The final answer can range upto 1e10, you should use long long for the answer instead of int. :P