How to approach problems like this Playlist or Josephus problem, where we delete some element and rejoin the circle. Also, if anyone can provide 2-3 similar problems, it will be really helpful to master this concept.
Thank you
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3880 |
| 2 | jiangly | 3669 |
| 3 | ecnerwala | 3654 |
| 4 | Benq | 3627 |
| 5 | orzdevinwang | 3612 |
| 6 | Geothermal | 3569 |
| 6 | cnnfls_csy | 3569 |
| 8 | jqdai0815 | 3532 |
| 9 | Radewoosh | 3522 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 161 |
| 2 | maomao90 | 160 |
| 3 | adamant | 156 |
| 4 | maroonrk | 153 |
| 5 | atcoder_official | 149 |
| 6 | -is-this-fft- | 148 |
| 6 | SecondThread | 148 |
| 8 | Petr | 147 |
| 9 | nor | 144 |
| 10 | cry | 143 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 28.07.2024 13:21:27 (k3).
Десктопная версия, переключиться на мобильную.
При поддержке
In many deletion problems, only a small change occurs in the array/circle. For example, in the problem Playlist, at most three GCD pairs change. This can usually help in either simulating the problem or getting to some other observation.
In this problem the number of elements in circle get reduced by 2-3 , but how to approch problems where we have to reduce it to 1 element.
Ex : Given an circular array , you can merge two adjacent elements and replace to by F(a[i],a[i+1]) .Find the maximum value you can get after n-1 operations ??
In deletion problems, there are some common approaches like doubling the array, using a data structure (set, segment tree) to erase and then binary searching or observing minor changes after deleting an element.
I like to use a circular linked list. It is extremely intuitive as it is literally a circle (I feel this makes more sense than for example, doubling the array).
https://www.geeksforgeeks.org/circular-linked-list/