ROBO2 - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: negativecode
Tester: sushil2006
Editorialist: iceknight1093

DIFFICULTY:

Easy

PREREQUISITES:

BFS

PROBLEM:

There’s an N\times M grid, each cell of which is either empty or blocked.
Two robots are placed at (1, 1). Every second, both robots must move to an adjacent free cell.
The objective is to make both robots reach (N, M) simultaneously. However, the robots aren’t allowed to be in the same cell (except for (1, 1) and (N, M)).
Find the minimum time needed to achieve this.

EXPLANATION:

If there was only a single robot, the minimum time required is fairly easy to find, and simply equals the length of the shortest path from (1, 1) to (N, M). This can be computed in \mathcal{O}(NM) with a BFS.

Let T denote the minimum time needed for a single robot.
With two robots, T is clearly a lower bound on the answer too.
Note that if (1, 1) and (N, M) are not connected then no valid solution exists either, so we only care about the case where they’re connected.

Let’s check if the answer can be exactly T.
For this, there must be two disjoint paths between (1, 1) and (N, M), so we need to figure out a way to check for this.

How to perform this check?

There are several different ways to do this.

A rather simple one is as follows: find all cells that are on any shortest path from (1, 1) to (N, M).
This can be done using BFS: compute d_1(x, y) to be the shortest path from (1, 1) to (x, y), and d_2(x, y) to be the shortest path from (N, M) to (x, y).
Then, (x, y) lies on some shortest path if and only if d_1(x, y) + d_2(x, y) = d_1(N, M).

Once all cells on the shortest path are known, sort them by their distance to (1, 1), i.e., d_1(x, y) values.
Now, if there’s any “level” of the shortest path that contains exactly one cell, every shortest path much pass through this cell and two disjoint paths cannot exist. Otherwise, a valid pair of paths will always exist.

There are other solutions too, for example by greedily constructing the paths: this can be seen in the author’s code attached below.


We now know whether the answer can be T or not.
What can we do if it’s not T?
As it turns out, in every other case, either the answer is T+2, or no path exists!
This is because:

  • If one of the cells adjacent to (1, 1) is blocked, both robots are forced to make the same move in the very first second, which is forbidden.
  • Otherwise, robot 1 can follow the shortest path, while robot 2 can first move away from (1, 1) to the other cell, then move back to (1, 1), and then follow the shortest path itself.

TIME COMPLEXITY:

\mathcal{O}(NM) per testcase.

CODE:

Author's code (C++)
#include<bits/stdc++.h>
using namespace std;
#define INF 1e17
#define FOR(a, b, c) for (int a = b; a < c; a++)
#define int long long
#define pb push_back
typedef vector <int> vint;
//----------------------DEBUGGER----------------------------------------------------------
#define dbg(x) cout << #x <<" "; _print(x); cout << endl;
 
void _print(int t) {cout << t;}
void _print(string t) {cout << t;}
void _print(char t) {cout << t;}
void _print(long double t) {cout << t;}
void _print(double t) {cout << t;}
void _print(unsigned int t) {cout << t;}
 
 
template <class T> void _print(vector<vector<T>> v) {for(int j =0;j<v.size();j++){cout <<endl<<"[ "; for (T i : v[j]){_print(i); cout << " ";} cout << "]";};}
template <class T, class V> void _print(pair <T, V> p);
template <class T> void _print(vector <T> v);
template <class T> void _print(set <T> v);
template <class T, class V> void _print(map <T, V> v);
template <class T> void _print(multiset <T> v);
template <class T, class V> void _print(pair <T, V> p) {cout << "{"; _print(p.first); cout << ","; _print(p.second); cout << "}";}
template <class T> void _print(vector <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
template <class T> void _print(set <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
template <class T> void _print(multiset <T> v) {cout << "[ "; for (T i : v) {_print(i); cout << " ";} cout << "]";}
template <class T, class V> void _print(map <T, V> v) {cout << "[ "; for (auto i : v) {_print(i); cout << " ";} cout << "]";}
template <class T> void _print(vector<vector<vector<T>>> v){for(int k =0;k<v.size();k++){_print(v[k]);}}
//----------------------------------------------------------------------------------------

int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
void get_path(vector <vint> &dist, vector<pair<int,int>> &path, int mini){
    int x = 0, y = 0;
    int n = dist.size(), m = dist[0].size();
    FOR(i,0,dist[0][0]){
        int dis = dist[x][y];
        vector <pair<int,int>> cand;
        FOR(i,0,4){
            int nx = x + dx[i], ny = y + dy[i];
            if(nx < n && ny < m && nx >= 0 && ny >= 0 && (dist[nx][ny] == dis-1)){
                cand.pb({nx, ny});
            }
        }
        sort(cand.begin(), cand.end());
        if(mini == 0){
            path.pb(cand.back());
            tie(x, y) = cand.back();
        }
        else{
            path.pb(cand[0]);
            tie(x, y) = cand[0];
        }
    }
}
void solve(){
    int n, m; cin >> n >> m;
    vector <string> grid(n);
    vector <vint> visited(n, vint (m)), dist(n, vint(m, INF));

    FOR(i,0,n){
        cin >> grid[i];
    }

    queue <pair<pair<int,int>,int>> q;
    q.push({{n-1, m-1},0});
    dist[n-1][m-1] = 0;

    while(!q.empty()){
        int x, y;
        auto p = q.front(); q.pop();
        tie(x, y) = p.first;
        int dis = p.second;

        if(visited[x][y]) continue;
        visited[x][y] = 1;

        FOR(i,0,4){
            if((x + dx[i] < n) && (y + dy[i] < m) && (x + dx[i] >= 0) && (y + dy[i] >= 0)){
                if(!visited[x+dx[i]][y+dy[i]] && grid[x+dx[i]][y+dy[i]] != '#'){
                    dist[x+dx[i]][y + dy[i]] = dis + 1;
                    q.push({{x + dx[i], y + dy[i]}, dis + 1});
                }
            }
        }
    }

    if(dist[0][0] == INF || grid[0][1] == '#' || grid[1][0] == '#'|| grid[n-2][m-1] == '#' || grid[n-1][m-2] == '#' ){
        cout << -1 << endl;
        return;
    }

    int ans = dist[0][0] + 2;
    vector <pair<int,int>> path1, path2;
    get_path(dist, path1, 1);
    get_path(dist, path2, 0);

    int flag = 2;
    FOR(i,0,path1.size()-1){
        if(path1[i] == path2[i]) flag = 0;
    }
    
    cout << ans - flag << '\n';
   
    


}
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    cout << fixed << setprecision(10);
    int t;
    cin >> t;
    FOR(i,1,t+1){
        solve();
    }
}
Tester's code (C++)
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

template<typename T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
typedef long long int ll;
typedef long double ld;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

#define fastio ios_base::sync_with_stdio(false); cin.tie(NULL)
#define pb push_back
#define endl '\n'
#define sz(a) (int)a.size()
#define setbits(x) __builtin_popcountll(x)
#define ff first
#define ss second
#define conts continue
#define ceil2(x,y) ((x+y-1)/(y))
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
#define yes cout << "Yes" << endl
#define no cout << "No" << endl

#define rep(i,n) for(int i = 0; i < n; ++i)
#define rep1(i,n) for(int i = 1; i <= n; ++i)
#define rev(i,s,e) for(int i = s; i >= e; --i)
#define trav(i,a) for(auto &i : a)

template<typename T>
void amin(T &a, T b) {
    a = min(a,b);
}

template<typename T>
void amax(T &a, T b) {
    a = max(a,b);
}

#ifdef LOCAL
#include "debug.h"
#else
#define debug(...) 42
#endif

/*



*/

const int MOD = 1e9 + 7;
const int N = 1e5 + 5;
const int inf1 = int(1e9) + 5;
const ll inf2 = ll(1e18) + 5;

vector<ll> dx = {-1,1,0,0};
vector<ll> dy = {0,0,-1,1};

void solve(int test_case){
    ll n,m; cin >> n >> m;
    char a[n+5][m+5];
    rep(i,n+5) rep(j,m+5) a[i][j] = '#';
    rep1(i,n) rep1(j,m) cin >> a[i][j];

    if(a[1][2] == '#' or a[2][1] == '#'){
        cout << -1 << endl;
        return;
    }

    if(a[n-1][m] == '#' or a[n][m-1] == '#'){
        cout << -1 << endl;
        return;
    }

    ll dis1[n+5][m+5], dis2[n+5][m+5];
    memset(dis1,-1,sizeof dis1);
    memset(dis2,-1,sizeof dis2);

    // dis from (1,1)
    {
        queue<pll> q;
        q.push({1,1});
        dis1[1][1] = 0;
        while(!q.empty()){
            auto [i,j] = q.front();
            q.pop();

            rep(x,4){
                ll i2 = i+dx[x], j2 = j+dy[x];
                if(a[i2][j2] == '#') conts;
                if(dis1[i2][j2] != -1) conts;
                q.push({i2,j2});
                dis1[i2][j2] = dis1[i][j]+1;
            }
        }
    }

    // dis from (n,m)
    {
        queue<pll> q;
        q.push({n,m});
        dis2[n][m] = 0;
        while(!q.empty()){
            auto [i,j] = q.front();
            q.pop();

            rep(x,4){
                ll i2 = i+dx[x], j2 = j+dy[x];
                if(a[i2][j2] == '#') conts;
                if(dis2[i2][j2] != -1) conts;
                q.push({i2,j2});
                dis2[i2][j2] = dis2[i][j]+1;
            }
        }
    }

    ll sp = dis1[n][m];
    if(sp == -1){
        cout << -1 << endl;
        return;
    }

    // find all nodes on the sp
    vector<ll> cnt(n*m+5);

    rep1(i,n){
        rep1(j,m){
            if(a[i][j] == '#') conts;
            if(dis1[i][j] == -1 or dis2[i][j] == -1) conts;
            if(dis1[i][j]+dis2[i][j] == sp){
                ll d = dis1[i][j];
                cnt[d]++;
            }
        }
    }

    ll ans = sp;

    rep1(i,sp-1){
        if(cnt[i] == 1){
            ans = sp+2;
            break;
        }
    }

    cout << ans << endl;
}

int main()
{
    fastio;

    int t = 1;
    cin >> t;

    rep1(i, t) {
        solve(i);
    }

    return 0;
}

“Otherwise, a valid pair of paths will always exist.” Is there simple proof for this?

I used the LGV lemma to avoid having to deal with this (although the downside is that this requires gambling on the modulo).

1 Like

ROBO2 looks unbelievable to me. It means the author find 2 disjoint shortest path without any network flow algorithm?

https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=1747

This is a close problem which used network flow algorithm.

2 Likes

As it turns out, in every other case, either the answer is T+2 or no path exists!
This is because:

  • If one of the cells adjacent to (1,1) is blocked, both robots are forced to make the same move in the very first second, which is forbidden.
  • Otherwise, robot 1 can follow the shortest path, while robot 2 can first move away from (1,1) to the other cell, then move back to (1,1), and then follow the shortest path itself.

The last point means that the robots do not enter the final position simultaneously? But the question says they have to enter simultaneously right? Please Correct me if I’m wrong.

2 Likes

they have to be at (N,M) simultaneously , no need to reach simultaneously.

2 Likes

As Every second, both the robots must each move to an adjacent empty square.
How is this possible :- As it turns out, in every other case, either the answer is T+2 , or no path exists!

Update : answer can be T+2 only if both adjacent cells of (1,1) and both adjacent cells of (N,M) are
empty. (i.e a[1][2] = a[2][1] = a[N][M-1] = a[N-1][M] = ’ . ’ .

1 Like

yup, you’re right, answer can’t be T+2 always, this is a necessary condition.

Why both of adjacent cells to (n,m) should be free ?

ROBO 1 after reaching (N,M) cannot stay there for next 2 secs, so it should go to other adjacent cell (which is not in shortest path) and come back to N,M.

2 Likes

Understood! Thanks :innocent:

Can you explain this part ?

OK straight to the point. The answer is either:

  1. -1 this can be checked easily
  2. The minimum time if we can find 2 different minimum time paths
  3. The answer can be minimum time + 2 understandable just do a jaywalk

Question: Give me a proof that it can never be minimum time + 1. Don’t just say, “not possible”. OK intuitively it seems not possible. I didn’t found any case where it is possible but I want a certain black and white reason.

1 Like

As in case of t+2 , the robot 2 follows shortest path of robot 1 but they wont reach n,m simultaneously right . But in the question it has been mentioned .

Can you explain what was the issue with the solution? Is it wrong or something?

Now I have a rigorous proof.

https://codeforces.com/blog/entry/138726

I don’t have a solid reasoning but you can think of it in this way , let’s say you are starting at (1,1) and want to reach cell (N,M) , so obviously , each step you want to take is towards your goal , that is for the shortest path , you would want to take total (N - 1) down steps and (M - 1) right steps , resulting in (N + M - 2) steps. Let’s say at any point of time this path is blocked by the cell ‘#’ , then essentially , you can’t take a right or down step and are forced to take a step towards the left or up (away from your target) , each of this step is forced to be compensated with a step in the opposite direction at some instance of time , that is , if you take a step towards the left , then you are forced to go right at some point (resulting in an addition of 2 steps and not 1) , so the parity of the length of the SHORTEST paths from the source to destination never changes , that is lets say we were to figure out what are the K shortest path lengths from (1,1) to (N,M) , then all the numbers in there would have the same parity…(I hope I am clear)

1 Like

Now , can someone help ME with my problem , like my logic was the same , if we find 2 shortest paths , then answer is their length , else its their length + 2 , although it seems the way i check if there exists multiple shortest paths is wrong , what i did was find one shortest path and all the elements along the path , and if at any instant , i reach any of the cell in that path in the same time through a different path , then my job is done , else its not , Here’s my code , pls lmk if u find any test case that’s going wrong or any flaw in the logic itself…
https://www.codechef.com/viewsolution/1125174725

That’s not a proof. That is called intuition which is not always correct(but I wish).

Proof: A grid(with no non-linear jump) is a bipartite graph(proof: chromatic number 2). So each vertex belongs to either of 2 different sets. Let’s color them black and white(resembling a chess board). So you have 2 sets like so:
Set A (only white color nodes) and Set B (only black color nodes).

Consider this case: Going from black node to white node with distance x. So any other route from node black to white has to go to Set B and then back to Set A(because same set have no edges in bipartite graph) and any odd length like x+1, x+3, x+5 means that we travelled in the same set which is not possible in bipartite graph so minimum we have to switch the set and then come back which is nothing but 2 operations and can only be 2*n

Take all other cases Black to White, Black to Black, White to Black, White to White and verify that its always 2*n.

So from minimum the answer can only increase by 2.

Key observation: Given grid is a planar Bipartite graph

Too deep for me , i need to clear a bit more concepts before the proof starts making sense to me…

They do enter simultaneously. First R1 reaches at T then at T+1 moves to some adjacent square, then both are 1 square away from reaching (n,m). Then, both of them come to (n,m) at T+2

1 Like