PROBLEM LINK :
Author : Asim Krishna Prasad
Tester : Sarvesh Mahajan
DIFFICULTY :
MEDIUM-HARD
PREREQUISITES :
Dynamic Programming
PROBLEM :
Given a N x M matrix and D special cells with distinct values, you have to output the number of ways to reach (N, M)th cell from (1,1)th cell with exactly X values in your list, while following the given rules :
- When you reach a special cell, you have to add the value at the end of your list, you can't leave the value.
- At any point of time, the list that you have should be in decreasing order.
EXPLANATION :
O(NM(D^2)) Solution
Let us first try to solve the problem without worrying about the constraints.Let us assume we can traverse through the matrix. This assumption leads to a simple dynamic problem solution for the problem.
A single state would be : dp[row][column][lastValueTaken][lengthOfTheListSoFar]
This problem can now be solved using recursion - memoisation as follows :
int dx[] = {-1, 0};
int dy[] = {0, -1};
bool isOnBoard(int x, int y)
{
if(x > r || x < 1 || y > c || y < 1) return 0;
return 1;
}
int rec(int x, int y, int lastTaken, int lengthSoFar)
{
if(x == 1 && y == 1)
{
if(id[x][y] != -1 && lengthSoFar == 1 && id[x][y] < lastTaken)
return 1;
else if(id[x][y] == -1 && lengthSoFar == 0)
return 1;
return 0;
}
int &ret = dp[x][y][lastTaken][lengthSoFar];
if(ret != -1)
return ret;
ret = 0;
int i;
int X, Y;
if(id[x][y] != -1)
{
if(lengthSoFar == 0) return 0;
if(lastTaken <= id[x][y]) return 0;
lengthSoFar--;
lastTaken = id[x][y];
}
fl(i,0,2)
{
X = x + dx[i]; Y = y + dy[i];
if(isOnBoard(X, Y))
{
ret += rec(X, Y, lastTaken, lengthSoFar);
ret %= MOD;
}
}
return (ret %= MOD);
}
O((D^3) + (D^3)) Solution
From the solution above, one key observation is that to calculate this DP, we just need the number of ways to reach from some (x1, y1) to some (x2, y2) without touch any (xi, yi) such that (xi, yi) is a special cell. This is when we can go from (x1, y1) to (x2, y2), that is, value at (x1, y1) is greater than (x2, y2).The final recursion - memoisation will look something like this :
ll rec(int ind, int lastTaken, int left)
{
if(left < 0 || ind < 0) return 0;
if(discs[ind] == SOURCE)
{
if(sourceOffset == left)
return getWeight(ind, lastTaken);
return 0;
}
ll &ret = dp[ind][lastTaken];
if(ret != -1)
return ret;
ret = 0;
ret += (getWeight(ind, lastTaken) * rec(ind - 1, ind, left - 1)) % MOD;
ret %= MOD;
if(discs[ind] != DESTINATION)
{
ret += rec(ind - 1, lastTaken, left);
ret %= MOD;
}
return ret;
}
That is, once we know the number of ways to reach any (x2, y2) from (x1, y1) without touching any other special cell in between, all that we need to do is to multiply that number of ways and go to next state.
The base case is, when we reach the first cell, we check if we have got the list of required length or not.
The second part of the problem is to get number of ways to reach some special cell (x2, y2) from some special cell (x1, y1) without going through any other special cell.
This problem can be solved as follows :
First a basic formula : number of ways to reach (x2, y2) from (x1, y1) if x2 >= x1 and y2 >= y1:
Let x = x2 - x1 and y = y2 - y1
Number of ways F(x1, y1, x2, y2) = (x+y)!/(x!y!)
Now, an interesting observation is that if we block a cell at (i, j) all cells with their respective coordinates greater than or equal to i and j will be affected by it(ie. number of ways to reach them will be changed).
Let’s say our set S = {all blocked cells + cell(N, M)}. We now sort S on increasing basis of x coordinate and then increasing on y. Also I maintain an array ans where ans[i] denotes number of ways to reach cell at index i in sorted(S).
Initially ans[i] = F(1, 1, S[i].x, S[i].y).
Now, I traverse the sorted(S) in increasing order and updating the number of ways for all the cells that it affects.
Sample code to this :
ll getWays(pair<int, int> p, pair<int, int> q)
{
ll x = abs(p.first - q.first), y = abs(p.second - q.second);
return ( ( (factorial[x + y] * revFactorial[x]) % MOD ) * revFactorial[y]) % MOD;
}
vector<ll> getAllWays(pair<int, int> startingPoint, vector<pair<int, int> > blockedPoints)
{
int i, j;
int limit = blockedPoints.SZ();
vector<ll> ret;
ret.resize(limit, 0);
fl(i, 0, limit)
if(blockedPoints[i].first >= startingPoint.first && blockedPoints[i].second >= startingPoint.second)
ret[i] = getWays(startingPoint, blockedPoints[i]);
fl(i, 0, limit - 1)
{
fl(j, i + 1, limit)
{
if(blockedPoints[j].first < blockedPoints[i].first || blockedPoints[j].second < blockedPoints[i].second) continue;
ret[j] = (ret[j] - (ret[i] * getWays(blockedPoints[i], blockedPoints[j]) % MOD) + MOD) % MOD;
}
}
return ret;
}
Once we have got this value for every (x1, y1) (x2, y2) pair all that is left to use the above mentioned recursion - memoisation to get to the answer.
Cases when first cell is a special cell or last cell is the special cell should be handled carefully.