WATRA - Editorial

PROBLEM LINK:

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

Author: Ahmet Kaan Avcı
Tester: Rahul Dugar
Editorialist: Aman Dwivedi

DIFFICULTY:

Easy - Medium

PREREQUISITES:

Binary Search, Dijkstra’s Algorithm

PROBLEM

You are given a matrix A of dimensions N \times M, where each cell of a matrix contains a pipe that can hold at most A_{ij} liters of water at any moment. You are also given the orientation of each pipe i.e. (left, right, up or down). A pipe may transfer its water only to the cell adjacent to it in the given direction.

Your task is to find the maximum water that can reach cell (N, M) at any moment by operating at most K times. Operation is defined as follows:

  • In a single operation you can rotate the pipe in a clockwise direction. However, this operation reduces the capacity of the pipe by 1. You can perform this operation only when the capacity of the pipe is greater than 1.

QUICK EXPLANATION:

We start by assuming the maximum amount of water that can reach the last cell as the average of minimum and maximum capacities given in the testcase. Then we continue applying binary search on this set of values ranging from minimum to maximum capacity conditioned to move to the right half of the subarray under consideration if the average of left and right extremes is a possible answer, and to the left half otherwise.
Considering X represents an assumed value and C the current capacity of a cell. We turn the matrix into a graph with cells represented as nodes, such that a cell will have only those adjacent cells as its children reaching whom is possible without losing over C-X litres from the capacity and cost of the edge is the lost capacity. In this graph we find the shortest path, and if its cost \leq K then X is a possible answer.

EXPLANATION:

The key idea is to perform binary search for possible answers over the set of integers ranging from the minimum to maximum capacities of water held by a pipe. We check if X liters of water can reach cell (N, M) at any moment by operating at most K times for any X, which in this case will be values chosen through binary search.

The following process needs to be followed for each selected X

We need to find whether X liters of water can reach cell (N, M) at any moment by performing the given operation at most K times.

Suppose we are in cell (i,j) which has the capacity of A_{ij} liters. In order to visit one of the adjacent cells say (i+1, j) from the cell (i,j) the new capacity of cell (i,j) should be greater than or equal to X. The new capacity is A_{ij} - op, where op is defined as the number of rotations needed to change the orientation of the pipe.

Why

If the new capacity of cell (i,j) is less than X then the minimum amount of water that can be transferred from this pipe will be less than X. If this pipe is included in our path then the maximum water that can reach cell (N, M) will always be less than X.

The cost needed to visit cell (i+1, j) from the cell (i,j) is op, where op is defined as the number of rotations needed to change the orientation of the pipe.

Let us try to build a graph for the same for better visualization. Our graph will consist of N \times M nodes and the construction of the graph will be as follows:

  • There exists an edge from (i, j) to its adjacent cells, if the condition of A_{ij} - op \ge X holds and the weight/cost of this edge will be op.

Once our graph is constructed, we need to find the minimum cost of any simple path from a given source node i.e (1,1) to a given destination node i.e (N,M). If the minimum cost is less than or equal to K, then we say that it is possible to transfer X liters of water to cell (N, M) by performing the operation at most K times.

The minimum cost of any simple path from a given source to destination can be found by applying Dijkstra Algorithm in the graph.

Finally, if it is possible for X liters of water to reach cell (N,M), then we fix our answer as X and iterate on the values greater than X. Otherwise, we will iterate on values less than X. This is what we employ Binary Search for, giving us the maximum liters of water that can reach to cell (N, M) by applying operation at most K times.

TIME COMPLEXITY:

O(log2(X)*E * log(V))

where,

X= capacity of source (\approx 10^9)
E = Edges (\approx 4*(N \times M))
V =N \times M

SOLUTIONS:

Setter
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#include <bits/stdc++.h>
 
using namespace std;
 
#define fi first
#define se second
#define int long long
#define mid ((start+end)/2)
 
const int li = 405;
 
char direct[li][li];
int n,m,a[li][li],k,flag,vis[li][li],val;
 
//This function is checking if we are going to outside or any prohibted cell
inline bool check(int x,int y,int z){
	if(x<=0 || y<=0 || x>n || y>m)return 0;//outside check.
	if(vis[x][y])return 0;//is the cell visited check.
	if(z<val)return 0;//looking to if the size of the cell is greater or equal to answer that we are now checking. All the size's must be greater or equal to current answer.
	return 1;
}
// This function checks that can we transfer "val" unit water to cell(n,m) from cell(1,1).
inline void sp(){
	//clear
	priority_queue<pair<int,pair<int,int>>> pq;
	while(pq.size())pq.pop();
	pq.push({k,{1,1}});
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m;j++){
			vis[i][j]=0;
		}
	}
	while(pq.size()){
		int co=pq.top().fi;// Number of change direction moves we have. (Note that bigger amount of change direction moves better than lesser amount.)
		int row=pq.top().se.fi;//Which row we are.
		int col=pq.top().se.se;//Which column we are.
		pq.pop();
		if(co<0)continue;//if we use change direction moves greater than k continue.
		if(vis[row][col])continue;
		vis[row][col]=1;
		if(row==n && col==m){flag=1;break;}
		if(direct[row][col]=='U'){//If direct is up now.
			if(check(row-1,col,a[row][col]))pq.push({co,{row-1,col}});// Go up
			if(check(row,col+1,a[row][col]-1))pq.push({co-1,{row,col+1}});// Use 1 change direction moves and go right
			if(check(row+1,col,a[row][col]-2))pq.push({co-2,{row+1,col}});// Use 2 change direction moves and go down
			if(check(row,col-1,a[row][col]-3))pq.push({co-3,{row,col-1}});// Use 3 change direction moves and go left
		}
		if(direct[row][col]=='R'){//If direct is right now.
			if(check(row-1,col,a[row][col]-3))pq.push({co-3,{row-1,col}});// Use 3 change direction moves and go up
			if(check(row,col+1,a[row][col]))pq.push({co,{row,col+1}});// Go right
			if(check(row+1,col,a[row][col]-1))pq.push({co-1,{row+1,col}});// Use 1 change direction moves and go down
			if(check(row,col-1,a[row][col]-2))pq.push({co-2,{row,col-1}});// Use 2 change direction moves and go left
		}
		if(direct[row][col]=='D'){//If direct is down now.
			if(check(row-1,col,a[row][col]-2))pq.push({co-2,{row-1,col}});// Use 2 change direction moves and go up
			if(check(row,col+1,a[row][col]-3))pq.push({co-3,{row,col+1}});// Use 3 change direction moves and go right
			if(check(row+1,col,a[row][col]))pq.push({co,{row+1,col}});// Go down
			if(check(row,col-1,a[row][col]-1))pq.push({co-1,{row,col-1}});// Use 1 change direction moves and go left
		}
		if(direct[row][col]=='L'){//If direct is left now.
			if(check(row-1,col,a[row][col]-1))pq.push({co-1,{row-1,col}});// Use 1 change direction moves and go up
			if(check(row,col+1,a[row][col]-2))pq.push({co-2,{row,col+1}});// Use 2 change direction moves and go right
			if(check(row+1,col,a[row][col]-3))pq.push({co-3,{row+1,col}});// Use 3 change direction moves and go down
			if(check(row,col-1,a[row][col]))pq.push({co,{row,col-1}});// Go left
		}
	}
}
 
int32_t main(){
	//~ freopen("15","r",stdin);
	//~ freopen("15.out","w",stdout);
	int t;
	scanf("%lld",&t);
	while(t--){
		scanf("%lld %lld %lld",&n,&m,&k);// Number of rows, columns and change direction moves.
		//~ k=0;
		for(int i=1;i<=n;i++){
			for(int j=1;j<=m;j++){
				scanf("%lld",&a[i][j]);//Size of each cell
			}
		}
		for(int i=1;i<=n;i++){
			scanf("%s",(direct[i]+1));
		}
		int start=1;
		int end=1000000000;
		//Use binary search to find the answer.
		while(start<=end){
			flag=0;
			val=mid;
			//Check that can we transfer val unit of water to cell (n,m) from cell (1,1)
			sp();
			if(flag)start=mid+1;//If we can transfer val unit water than we search for can we transfer bigger than mid
			else end=mid-1;// If we can't transfer than we search smaller units.
		}
		printf("%lld\n",end);
	}
	return 0;
}
 
 
Tester
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
typedef pair<int,int> pii;
typedef pair<double,double> pdd;
//#define double long double
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const int infi=0x3f3f3f3f;
const ll infl=0x3f3f3f3f3f3f3f3fLL;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
int powm(int a, int b) {
	int res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
 
 
long long readInt(long long l, long long r, char endd) {
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true) {
		char g=getchar();
		if(g=='-') {
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g&&g<='9') {
			x*=10;
			x+=g-'0';
			if(cnt==0) {
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
 
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd) {
			if(is_neg) {
				x=-x;
			}
			assert(l<=x&&x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l, int r, char endd) {
	string ret="";
	int cnt=0;
	while(true) {
		char g=getchar();
		assert(g!=-1);
		if(g==endd) {
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt&&cnt<=r);
	return ret;
}
long long readIntSp(long long l, long long r) {
	return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
	return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
	return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
	return readString(l,r,' ');
}
 
int a[405][405];
char b[405][405];
int dist[405*405];
vector<pair<int,pii>> gra[405*405];
int sum_nm=0;
void solve() {
//	int n=readIntSp(1,400),m=readIntSp(1,400),k=readIntLn(0,1000'000'000);
	int n,m,k;
	cin>>n>>m>>k;
	sum_nm+=n*m;
	assert(sum_nm<=160000&&n*m>=2);
	vector<pair<pii,pii>> edges;
	fr(i,0,(n+2)*(m+2))
		gra[i].clear();
	set<char> chk={'U','L','R','D'};
	fr(i,1,n)
		fr(j,1,m) {
			cin>>a[i][j];
//			if(j!=m)
//				a[i][j]=readIntSp(4,1000'000'000);
//			else
//				a[i][j]=readIntLn(4,1000'000'000);
		}
	vector<char> pp={'U','R','D','L','U','R','D','L'};
	vector<pii> disp={{-1,0},{0,1},{1,0},{0,-1},{-1,0},{0,1},{1,0},{0,-1}};
	fr(i,1,n) {
		fr(j,1,m) {
			cin>>b[i][j];
//			int temp;
//			cin>>temp;
//			b[i][j]=pp[temp-1];
//			b[i][j]=getchar();
//			assert(chk.count(b[i][j]));
		}
//		assert(getchar()=='\n');
	}
	fr(i,1,n)
		fr(j,1,m)
			for(int l=0; l<4; l++)
				if(b[i][j]==pp[l])
					for(int k=l; k<l+4; k++)
						gra[i*(m+1)+j].pb({a[i][j]-k+l,{k-l,(i+disp[k].fi)*(m+1)+j+disp[k].se}});
	int lo=0,hi=1'000'000'000,mid=(lo+hi+1)/2;
	while(lo<hi) {
//		trace(mid);
		fr(i,0,(n+2)*(m+2))
			dist[i]=infi;
		vector<vector<pii>> qu(4);
		qu[0].pb({0,(m+1)+1});
		dist[m+2]=0;
		while(qu[0].size()+qu[1].size()+qu[2].size()+qu[3].size()) {
//			trace(qu);
			while(qu[0].empty())
				rep(i,0,3)
					swap(qu[i],qu[i+1]);
			int at=qu[0].back().se;
			int dt=qu[0].back().fi;
			qu[0].pop_back();
			if(dist[at]!=dt)
				continue;
//			trace(at,dt);
			for(auto j:gra[at]) {
				if(j.fi>=mid&&dist[j.se.se]>dist[at]+j.se.fi) {
//					trace(j);
					dist[j.se.se]=dist[at]+j.se.fi;
					qu[j.se.fi].pb({dist[j.se.se],j.se.se});
				}
			}
		}
//		trace(mid,dist[(n*(m+1)+m)]);
		if(dist[(n*(m+1)+m)]<=k) {
			lo=mid;
		} else
			hi=mid-1;
//		trace(lo,hi);
		mid=(lo+hi+1)/2;
	}
	cout<<mid<<endl;
}
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(10);
//	int t=readIntLn(1,100000);
	int t;
	cin>>t;
	fr(i,1,t)
		solve();
#ifdef rd
	cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}
 
Editorialist
#include<bits/stdc++.h>
using namespace std;

#define int long long

#define p1 pair<int,pair<int,int>>

int n,m,k;
int a[405][405];
string ore[405];

bool vis[405][405];

int possible(int mid)
{
  priority_queue <p1,vector<p1>,greater<p1>> q1;

  for(int i=0;i<n;i++)
  {
    for(int j=0;j<m;j++)
      vis[i][j]=false;
  }

  q1.push({0,{0,0}});

  while(!q1.empty())
  {
    auto itr=q1.top();
    q1.pop();

    int r=itr.second.first;
    int c=itr.second.second;
    int op=itr.first;

    if(op>k)
      continue;
    if(vis[r][c])
      continue;

    vis[r][c]=true;
    if(r==n-1 && c==m-1)
      return 1;

    if(ore[r][c]=='L')
    {
      if(r-1>=0 && a[r][c]-1>=mid && !vis[r-1][c])
        q1.push({op+1,{r-1,c}});

      if(r+1<n && a[r][c]-3>=mid && !vis[r+1][c])
        q1.push({op+3,{r+1,c}});

      if(c-1>=0 && a[r][c]>=mid && !vis[r][c-1])
        q1.push({op,{r,c-1}});

      if(c+1<m && a[r][c]-2>=mid && !vis[r][c+1])
        q1.push({op+2,{r,c+1}});
    }

    if(ore[r][c]=='R')
    {
      if(r-1>=0 && a[r][c]-3>=mid && !vis[r-1][c])
        q1.push({op+3,{r-1,c}});

      if(r+1<n && a[r][c]-1>=mid && !vis[r+1][c])
        q1.push({op+1,{r+1,c}});

      if(c-1>=0 && a[r][c]-2>=mid && !vis[r][c-1])
        q1.push({op+2,{r,c-1}});

      if(c+1<m && a[r][c]>=mid && !vis[r][c+1])
        q1.push({op,{r,c+1}});
    }

    if(ore[r][c]=='U')
    {
      if(r-1>=0 && a[r][c]>=mid && !vis[r-1][c])
        q1.push({op,{r-1,c}});

      if(r+1<n && a[r][c]-2>=mid && !vis[r+1][c])
        q1.push({op+2,{r+1,c}});

      if(c-1>=0 && a[r][c]-3>=mid && !vis[r][c-1])
        q1.push({op+3,{r,c-1}});

      if(c+1<m && a[r][c]-1>=mid && !vis[r][c+1])
        q1.push({op+1,{r,c+1}});
    }

    if(ore[r][c]=='D')
    {
      if(r-1>=0 && a[r][c]-2>=mid && !vis[r-1][c])
        q1.push({op+2,{r-1,c}});

      if(r+1<n && a[r][c]>=mid && !vis[r+1][c])
        q1.push({op,{r+1,c}});

      if(c-1>=0 && a[r][c]-1>=mid && !vis[r][c-1])
        q1.push({op+1,{r,c-1}});

      if(c+1<m && a[r][c]-3>=mid && !vis[r][c+1])
        q1.push({op+3,{r,c+1}});
    }
  }

  return 0;
}

void solve()
{
  cin>>n>>m>>k;

  for(int i=0;i<n;i++)
  {
    for(int j=0;j<m;j++)
      cin>>a[i][j];
  }

  for(int i=0;i<n;i++)
  {
    cin>>ore[i];
  }

  int ans=0;

  int l=1,r=a[0][0];

  while(l<=r)
  {
    int mid=l+(r-l)/2;
    if(possible(mid))
    {
      ans=mid;
      l=mid+1;
    }
    else
      r=mid-1;
  }

  cout<<ans<<"\n";
}

int32_t main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int t;
  cin>>t;

  while(t--)
    solve();

return 0;
}

Hriday G (Neat and Clean)
/**
 >> the_hyp0cr1t3
 >> 15.03.2021 19:24:04
**/
#include <bits/stdc++.h>
using namespace std;
#define pb emplace_back
#define all(x) x.begin(), x.end()
#define sz(x) static_cast<int32_t>(x.size())
auto chmax = [](auto& A, auto&& B) { return B > A? A = B, true : false; };
auto chmin = [](auto& A, auto&& B) { return B < A? A = B, true : false; };
 
const int64_t k_II = 2e18;
const int INF = 2e9, MOD = 1e9+7;
const int N = 2e5 + 5;
 
const array dx{-1, 0, 1, 0, -1, 0, 1, 0};
const array dy{0, 1, 0, -1, 0, 1, 0, -1};
 
struct state {
    int x, y; int64_t dist;
    state(int x, int y, int64_t dist): x(x), y(y), dist(dist) {}
    bool operator<(const state& o) const { 
        return dist > o.dist; 
    }
}; 
 
int ocoiek() {
    int i, j, n, m, k;
    cin >> n >> m >> k;
    vector<string> dir(n);
    vector<vector<int>> a(n, vector<int>(m));
    for(i = 0; i < n; i++)
        for(j = 0; j < m; j++)
            cin >> a[i][j];
    for(i = 0; i < n; i++) {
        cin >> dir[i];
        for(j = 0; j < m; j++) {
            char c = dir[i][j];
            dir[i][j] = c == 'U'? 0 : c == 'R'? 1 : c == 'D'? 2 : 3;
        }
    }
 
    auto valid = [n, m](int x, int y) {
        return 0 <= x and x < n and 0 <= y and y < m;
    };
 
    auto check = [&](int x) {
        vector<vector<int64_t>> d(n, vector<int64_t>(m, k_II));
        priority_queue<state> pq;
        pq.emplace(0, 0, d[0][0] = 0);
        while(!pq.empty()) {
            state top = pq.top(); pq.pop();
            if(top.dist > d[top.x][top.y]) continue;
            for(i = 0; i < 4; i++) {
                int nx = top.x + dx[dir[top.x][top.y] + i];
                int ny = top.y + dy[dir[top.x][top.y] + i];
                if(valid(nx, ny) and a[top.x][top.y] - i >= x
                    and chmin(d[nx][ny], top.dist + i))
                        pq.emplace(nx, ny, d[nx][ny]);
            }
        } return d[n-1][m-1] <= k;
    };
 
    int lo = 0, hi = MOD;
    while(lo <= hi) {
        int mid = lo + hi >> 1;
        if(check(mid)) lo = mid + 1;
        else hi = mid - 1;
    } cout << max(0, hi) << '\n';
 
    return 0;
}
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int Q; for(cin >> Q; Q; Q--) ocoiek();
} // ~W 
6 Likes

It is possible to have a E log2(x) solution, since weights of edges are in the range of 0 to 3 only, so to transition from one node to another using weight w, we can put w dummy nodes each pointed from the previous by weight 1. And final dummy node joins to the cell with weight 0. Then we can run a 0-1 bfs on the graph.

2 Likes

Is there any other approach for solving this question, I mean can we do this problem without binary search, with only Dijkstra.

1 Like

Why is the number of edges 4 * (N + M)? Shouldn’t it be 4 * N * M?

Also, the explanation says “Our graph will consist of N + M nodes”. Are you certain it is N + M and not N * M?

1 Like

My bad !! Sorry it was typo fixed

1 Like

Am I the only one who thinks that this implementation is pretty tough?

2 Likes

https://www.codechef.com/viewsolution/44065575
I am getting TLE here , can someone suggest some optimizations for this.

1 Like

This was such a GOOD question I can’t appreciate enough!
https://www.codechef.com/viewsolution/44072308
Maybe did a little easy implementation and understandable also.

1 Like

Fixed it ! I forgot to skip precomputed nodes.
Fixed : Solution: 44074820 | CodeChef

https://www.codechef.com/viewsolution/44087424
can anyone tell me what I’m missing

I think it’s OK