HighHopes's blog

Help in a Grid Problem
By HighHopes, history, 5 years ago, In English

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?

  • Vote: I like it
  • -9
  • Vote: I do not like it

»
5 years ago, # |
← Rev. 2   Vote: I like it +1 Vote: I do not like it

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.

this
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    One more solution which i guess is correct:

    Spoiler
    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +9 Vote: I do not like it
      Correct special case
      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          ← Rev. 3   Vote: I like it +1 Vote: I do not like it

          https://en.wikipedia.org/wiki/Vacuous_truth

          the problem doesn't mention anything like NO SOLUTION

          What do you expect from HackerEarth?

          → Reply
          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            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.

            → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it +1 Vote: I do not like it

          Because the condition "all the g cells can be traversed ... " literally holds.

          → Reply