ss_96's blog

By ss_96, history, 22 months ago, In English,

I was trying to solve the following question:

You are playing a game in which you have a rectangular grid of nn cells. Each cell is either empty or has a firework. Empty cells are marked with ".", cells with firework are marked with "" . Two cells are said to be adjacent if they share a side.

If firework in any cell explodes it destroys itself and the empty cells connected to it. Two cells are connected if there is a path of empty adjacent cells between them. You have to find the number of cells that will be destroyed if the fireworks are triggered independently. Input Constraints: 1≤n≤1000 Sample Input 4

* . . *

. . * .

* . . *

* . . *

Sample Output 66(9(for 1st *)+10+10+9+10+9+9(for 7th *)).

I simply applied a BFS and added individual sum.The problem is that it only passed some test cases,wrong answer and time limit exceeded in some.Can some please suggest what test case am I missing in handling? My code: https://gist.github.com/Sharma96/16071e66b0a36828c3566196289f0c92

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

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ss_96 (previous revision, new revision, compare).

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by ss_96 (previous revision, new revision, compare).

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I haven't read your code, but bfs seems an overkill. If I understand correctly the problem, then you only have to check 4 cells for each firework, and flag them exploded. If it hasn't been exploded yet, then increase the count by one.

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    the 4 adjacent cells will be exploding further cells if they are empty cells,how will I maintain that without a BFS?

  • »
    »
    22 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    1 small question,the value of 'n' in the question can vary from 1 to 1000,but,when the value of n is 1000,then an array of 1000*1000 size is to be created.Will this not lead to a memory overflow?How to handle this type of scenario?

    • »
      »
      »
      22 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Don't worry. It won't overflow as long as you use static(global) declarations of arrays.

      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        So I should simply write arr[1000][1000] outside main? This might be a silly question.(I am new to C.P.)

        • »
          »
          »
          »
          »
          22 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Yeah, just write that outside "int main()" and it will be OK.

»
22 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Your time complexity is O(n^4) so it is obvious that you get a TLE.

You can solve the problem like this:

  1. DFS(or BFS) the whole grid once to calculate which connected component each cell belongs to, and the size of each connected component.

  2. For each firework, get the set of the connected component of the 4 adjacent cells, and simply calculate the sum of there sizes.

The sample case work like this:

F11F

11F2

F11F

F11F

(F=firework)

The size of the first connected component('1' grid): 8

The size of the second connected component('2' grid): 1

Firework 1: 8('1' grid)+1(itself)

Firework 2: 8('1' grid)+1('2' grid)+1(itself)

(And so on)

(Don't forget to use 64-bit integers as 32-bit integers might overflow)

(Sorry for my poor English)

  • »
    »
    22 months ago, # ^ |
    Rev. 3   Vote: I like it 0 Vote: I do not like it

    Thanks for the answer.

    1.)So,I should put the first empty cell in my queue and put 1 in all the cells reachable from my current cell,then again find an empty cell until I find another empty cell,and repeat the same process.

    2.)Then for each firework,add all the size of the different numbers adjacent to it.

    The time complexity for 1.) is O(n^2),for the second point,for each F,then for each number,search the whole grid,so it would be O(n^3).Right?

    • »
      »
      »
      22 months ago, # ^ |
      Rev. 2   Vote: I like it 0 Vote: I do not like it

      In fact, in the second part, for each F we only need to consider 4 cells and simply add the sizes which are already calculated instead of do DFS(BFS) for another time. So it would be O(4*n^2)=O(n^2).

      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Ok,Thanks!

        Just 1 point more please,my code was failing in 1 test case,do you think any corner case was not handled?

      • »
        »
        »
        »
        22 months ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        But,how will I number every cell with just 1 BFS traversal.

        Let us assume I got the first empty cell,called BFS for it and marked all cells as 1 which were connected to it.For finding empty cells which were left,I have to traverse the grid again.So would it be O(n^4)?

        • »
          »
          »
          »
          »
          22 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          As simple as those below:

          for i=first to last for j=first to last if(not visited(cell[i][j]) bfs from (i,j)

          Each cell is traversed at most once, so it's O(n^2) in total.

          • »
            »
            »
            »
            »
            »
            22 months ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Thanks for your time and effort! I was thinking the same but thought the wrong time complexity for it.

»
22 months ago, # |
  Vote: I like it 0 Vote: I do not like it

2nd question of Hiring Challenge!

  • »
    »
    22 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    My contest has already ended as it was a 3 hour test, and I asked after my challenge was completed,I would have shared the question link, but it was not accessible to me after I competed the test!