ss_96's blog

By ss_96, history, 2 years ago, ,

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

• -8

 » 2 years ago, # |   0 Auto comment: topic has been updated by ss_96 (previous revision, new revision, compare).
 » 2 years ago, # |   0 Auto comment: topic has been updated by ss_96 (previous revision, new revision, compare).
 » 2 years ago, # |   0 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.
•  » » 2 years ago, # ^ |   0 the 4 adjacent cells will be exploding further cells if they are empty cells,how will I maintain that without a BFS?
•  » » 2 years ago, # ^ |   0 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?
•  » » » 2 years ago, # ^ |   0 Don't worry. It won't overflow as long as you use static(global) declarations of arrays.
•  » » » » 2 years ago, # ^ |   0 So I should simply write arr[1000][1000] outside main? This might be a silly question.(I am new to C.P.)
•  » » » » » 2 years ago, # ^ |   0 Yeah, just write that outside "int main()" and it will be OK.
 » 2 years ago, # | ← Rev. 2 →   0 Your time complexity is O(n^4) so it is obvious that you get a TLE.You can solve the problem like this: DFS(or BFS) the whole grid once to calculate which connected component each cell belongs to, and the size of each connected component. 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:F11F11F2F11FF11F(F=firework)The size of the first connected component('1' grid): 8The size of the second connected component('2' grid): 1Firework 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)
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 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?
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 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).
•  » » » » 2 years ago, # ^ |   0 Ok,Thanks!Just 1 point more please,my code was failing in 1 test case,do you think any corner case was not handled?
•  » » » » 2 years ago, # ^ |   0 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)?
•  » » » » » 2 years ago, # ^ |   0 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.
•  » » » » » » 2 years ago, # ^ |   0 Thanks for your time and effort! I was thinking the same but thought the wrong time complexity for it.
 » 2 years ago, # |   0 2nd question of Hiring Challenge!
•  » » 2 years ago, # ^ | ← Rev. 2 →   0 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!