LMINE Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Dung
Tester: Nishank Suresh, Utkarsh Gupta
Editorialist: Pratiyush Mishra

DIFFICULTY:

3044

PREREQUISITES:

Dynamic Programming , Permutations and Combinations.

PROBLEM:

You are given an integer array A of size N and a positive integer M. This array contains a hidden message which can be decoded by the following algorithm:

int ox[N+1], oy[N+1];
for(int i = 1; i ≤ N; i++) {
    ox[i] = A[i] / M;
    oy[i] = A[i] % M;
}

There are N landmines on the xy-plane, such that the i^{th} landmine (1\le i \le N) is located at (ox_i,oy_i).

Initially, you are at point (0,0) and you must go to point (X,Y). At each step, you can either move to the right by 1 unit or move up by 1 unit.
Formally, if you are standing at (x,y), then you can either move to (x+1,y) or to (x,y+1).

A path is called safe if there aren’t any landmines on that path. Count the number of safe paths which you can take to reach the destination. As the answer can be quite large, output it modulo 10^9+7.

EXPLANATION:

Suppose there are no obstacles then number of ways to move from point (0,0) to say point (x,y) will be \binom{x+y}{x}. You can read more about it here.

Thus we know the total number of ways to reach point (x,y) which is \binom{x+y}{x}. Now we will subtract all the invalid ways, i.e ways that go through a landmine.

To calculate number of invalid ways we go through each cell having a landmine and calculate number of ways to reach at that cell and multiply it with number of ways to reach (x,y) from that cell which would give all the number of ways to reach (x,y) passing through that mined cell. We would add all the invalid ways for each such cells to get the total number of invalid paths. We would simply subtract this from total number of paths to get our answer.

Now in order to calculate number of ways to reach a mined cell, we can use dp[i][j], which tells us the number of ways to reach point (i,j) without stepping on any landmine.

dp[i][j] = (dp[i-1][j] + dp[i][j-1])\;\%\;mod

Now if there is a landmine on point (i,j), then

invalids \;+=\; (dp[i][j] \times \binom{x-i+y-j}{x-i})\;\%\;mod \\ dp[i][j] = 0

Thus finally our answer would be:

\binom{x+y}{x} - invalids

TIME COMPLEXITY:

O(Mlog(X+Y)),

W=max(A[i] / M)+1,\; 1 \leq i \leq N
H=max(A[i] \;mod\; M)+1,\; 1 \leq i \leq N
So the following inequality is always true :
W ≤ (1000000+M)/M and H ≤ M
which gives
W \times H ≤ 1000000+M

SOLUTION:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

Can anyone tell why my solution is giving wrong answer?
Solution