Disclaimer: This problem is from a contest on Hackerearth(hiring for intern) held on 13th April.
I was unable to solve this problem, can anyone help how to solve it? Can it be solved greedily or we need to use some graph algo?
→ Обратите внимание
До соревнования
Codeforces Round #956 (Div. 2) and ByteRace 2024
00:06:30
Зарегистрироваться »
Codeforces Round #956 (Div. 2) and ByteRace 2024
00:06:30
Зарегистрироваться »
*есть доп. регистрация
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | tourist | 3803 |
| 2 | jiangly | 3707 |
| 3 | Benq | 3627 |
| 4 | ecnerwala | 3584 |
| 5 | orzdevinwang | 3573 |
| 6 | Geothermal | 3569 |
| 6 | cnnfls_csy | 3569 |
| 8 | Radewoosh | 3542 |
| 9 | jqdai0815 | 3532 |
| 10 | gyh20 | 3447 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | awoo | 163 |
| 2 | maomao90 | 160 |
| 3 | adamant | 159 |
| 4 | maroonrk | 152 |
| 5 | -is-this-fft- | 150 |
| 6 | atcoder_official | 148 |
| 6 | SecondThread | 148 |
| 8 | nor | 147 |
| 9 | TheScrasse | 146 |
| 10 | Petr | 144 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 07.07.2024 17:28:31 (h1).
Десктопная версия, переключиться на мобильную.
При поддержке
The answer doesn't exceed 2. When the answer is 0, grid is already disconnected. When the answer is 1... , I don't have so good solution, but I'm glad if you read this.
First, if there is a cycle made of G, grid can't be disconnected by this part. Find them by searching Ds which don't touch edges of the grid, then replace all D in the cycle.
Second, find G which have several relatives like followings.
The grid has no cycles, so replacing this G will disconnect the grid.
One more solution which i guess is correct:
1) if grid is already disconnected, answer is 0.
2) if it has an articulation point then answer 1.
3) else answer is 2 (because we can always isolate some corner g by placing 2 d's).
Special case: if there is exactly 1 g then answer is obviously 1.
if there is exactly 1 g, or exactly 2 connected g, then answer is obviously NO SOLUTION
Why no solution, we can replace those g's by d and the grid is disconnected.
also the problem doesn't mention anything like NO SOLUTION.
https://en.wikipedia.org/wiki/Vacuous_truth
What do you expect from HackerEarth?
Oh wow! I didn't knew this before. Thanks for the link.
But that means either the author assumes that if there are all d's then it is disconnected or the problem statement lacks this information.
Because the condition "all the g cells can be traversed ... " literally holds.