SNSOCIAL - Editorial

I tried to use a multi source bfs but the solution timed out for some reason. Could someone help me find out why it times out?

https://www.codechef.com/viewsolution/13939897

Thanks in advance.

I tried this question using 2 priority queues.First priority is sorted on the basis of value and second on the basis of time to make that cell max.I am getting WA, can anybody tell me where I went wrong.

https://www.codechef.com/viewsolution/17191459

@krishnadey30

Dey, Your code can go upto O(n^2m^2) because in the second nested loop you are iterating the outer loop till d and inner loop till c but consider a case where half the elements are max then c will (nm)/2 and d will also be
(n*m)/2 so total complexity will be O(n^2 * m^2) so it gave TLE. Correct if Iā€™m wrong.

@rahul_2608

if you are at cell (i,j),then you can go to 8 cells from (i,j) and they are

(i,j+1)

(i,j-1)

(i-1,j)

(i+1,j)

(i-1,j+1)

(i-1,j-1)

(i+1,j+1)

(i-1,j+1)

instead of writing all 8 possibilities separately we can take two arrays dx[] and dy[] and store corresponding values and we can check all possibilities in one for loop