SNSOCIAL - Editorial

editorial
, , , , ,
21

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.

22

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

23

@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.

24

@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

25

Anyone please suggest , where is my code lagging, passing all sample Tcases

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define fast ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
#define vi vector
#define vvi vector<vector>
#define vll vector
#define vvll vector<vector>
#define loop0(i, n) for (ll i = 0; i < n; i++)
#define loop1(i, n) for (ll i = 1; i <= n; i++)
#define loop(i, a, b, n) for (ll i = a; i <= b; i++)
#define end ‘\n’
#define vpi vector<pair<int, int>>
#define vpll vector<pair<long long int, long long int>>
#define pb push_back
const int inf = 1e9 + 7;

// const int V = 1e5 + 10;
// vector<pair<int, int>> adj[V];
// vector level(V, inf);
ll mx;
ll r, c;
bool isValid(ll x, ll y, vvll &g)
{
if (x >= 0 && y >= 0 && x < r && y < c && g[x][y] != mx)
return true;
return false;
}
int main()
{
fast;
ll t = 1;
cin >> t;
while (t–)
{
cin >> r >> c;

    vvll g(r, vll(c));

    loop0(i, r)
    {
        loop0(j, c)
        {
            cin >> g[i][j];
            mx = max(mx, g[i][j]);
        }
    }
    queue<pair<ll, ll>> q;
    loop0(i, r)
    {
        loop0(j, c)
        {
            if (g[i][j] == mx)
                q.push({i, j});
        }
    }
    ll timer = -1;
    vll dx{-1, -1, -1, 0, 0, 1, 1, 1};
    vll dy{-1, 0, 1, -1, 1, -1, 0, 1};

    while (!q.empty())
    {
        ll sz = q.size();
        while (sz--)
        {
            ll x = q.front().first;
            ll y = q.front().second;
            q.pop();
            for (ll i = 0; i < 8; i++)
            {
                if (isValid(x + dx[i], y + dy[i], g))
                {
                    q.push({x + dx[i], y + dy[i]});
                    g[x + dx[i]][y + dy[i]] = mx;
                }
            }
        }
        timer++;
    }

    cout << (timer==-1?0:timer) << end;
}
return 0;

}