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?
→ Pay attention
→ Streams
→ Top rated
| # | User | Rating |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3611 |
| 4 | jiangly | 3583 |
| 5 | strapple | 3515 |
| 6 | tourist | 3470 |
| 7 | Radewoosh | 3415 |
| 8 | Um_nik | 3376 |
| 9 | maroonrk | 3361 |
| 10 | XVIII | 3345 |
→ Top contributors
| # | User | Contrib. |
|---|---|---|
| 1 | Qingyu | 162 |
| 2 | adamant | 148 |
| 3 | Um_nik | 146 |
| 4 | Dominater069 | 143 |
| 5 | errorgorn | 141 |
| 6 | cry | 138 |
| 7 | Proof_by_QED | 136 |
| 8 | YuukiS | 135 |
| 9 | chromate00 | 134 |
| 10 | soullless | 133 |
→ Find user
→ Recent actions
Codeforces (c) Copyright 2010-2026 Mike Mirzayanov
The only programming contests Web 2.0 platform
Server time: May/21/2026 13:56:06 (g1).
Desktop version, switch to mobile version.
Supported by
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.