Can someone tell the approach for this interesting question: Question
Пожалуйста, прочтите новое правило об ограничении использования AI-инструментов.
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 4009 |
| 2 | jiangly | 3839 |
| 3 | Radewoosh | 3646 |
| 4 | jqdai0815 | 3620 |
| 4 | Benq | 3620 |
| 6 | orzdevinwang | 3612 |
| 7 | Geothermal | 3569 |
| 8 | ecnerwala | 3494 |
| 9 | Um_nik | 3396 |
| 10 | gamegame | 3386 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Um_nik | 164 |
| 2 | -is-this-fft- | 161 |
| 3 | maomao90 | 160 |
| 4 | atcoder_official | 158 |
| 4 | cry | 158 |
| 4 | awoo | 158 |
| 7 | adamant | 155 |
| 8 | nor | 154 |
| 9 | TheScrasse | 153 |
| 10 | Dominater069 | 152 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 04.10.2024 08:23:53 (j2).
Десктопная версия, переключиться на мобильную.
При поддержке
Correct me if I'm wrong. My first thought for this problem was dp. dp(i) -> maximum posters till i th element in some defined order that works (maybe sort using x and y?) but soon became doubtful if such an order even exists. For all 2 pairs we can find if the 2 posters are overlapping or not. If we create a graph and add edge b/w 2 nodes (posters) if they are NOT overlapping, then we need to find the largest connected component size which is completely connected (edge b/w every pair #E=n(n-1)/2)
this is a matching problem , it kinda makes sense that no greedy/dp algorithm would work even if you didnt knew the tags tho.Most of the time if it is a problem about selecting things that are limiting each other by someway and no greedy seems to work, it is a matching problem.You can learn bipartite matching algorithm and then try the problem again
I keep false solving