VAIMIN - Editorial

PROBLEM LINK:

Div1, Div2
Practice

Author: Vaibhav Gupta
Tester: Misha Chorniy
Editorialist: Vaibhav Gupta

DIFFICULTY:

MEDIUM-HARD

PREREQUISITES:

Dynamic Programming, Combinatorics

PROBLEM:

The problem can be reduced to the following grid world scenario.
Chef is at coordinate (0,0) in a 2-D grid and has to reach point (p,q). From any point (x,y) he can move only in increasing direction: either UP(to the point (x, y+1)) or RIGHT(to the point (x+1, y)). Here, UP & RIGHT correspond to a bad & good deed respectively. But he can move UP if he is strictly below the line x = y + c. M points are blocked in the grid(he can’t visit a blocked point), whose coordinates are given.
You have to count number of such paths possible. Two ways are same if and only if path taken is exactly same in both ways. Print the required answer modulo 10^9 + 7.

QUICK EXPLANATION:

The problem can be broken down in 2 parts.

  1. Make a function that finds the number of ways to reach point (x2,y2) from point (x1,y1) with subject to the constraint that we can’t cross line x = y + c.
  2. The number of ways of reaching any blocked point (i,j) is independent of any blocked cell having larger x or y coordinates. If we sort the blocked cells on basis of x,y in increasing order - the number of ways to reach a cell in ith index of the array is independent of any cell after it in the array. So we can find the number of ways reaching any blocked cell by using m^2 DP approach.

The overall complexity is O(M^2 + p +q).

GENERAL SUGGESTION:

This editorial will have some hand exercises. It’s highly suggested that you yourself try to figure out the solution to those before proceeding further.

EXPLANATION:

Part 1: Find number of ways to reach point Q(x2, y2) from point P(x1, y1) if x2 >= x1 and y2 >= y1 without crossing the line x = y + c and ignoring the blocked cells:
Consider the following figure.

Here we want to go from P to Q without crossing the line(black line). We will call it L1.
Consider all possible paths from P to Q. There can be 2 types of paths:

  1. Paths from P to Q without crossing the line L1. We call such a path a good path. NOTE A path is good as long as it doesn’t cross L1. Although, it can it touch it any number of times.
  2. Paths that cross the line L1. We call such a path a bad path.

In the figure the blue path is a good path whereas the orange path is a bad path.
Now the sum of all good paths and bad paths gives us the total number of paths from P to Q.

Ex1: Find total number of paths from point P(x1, y1) to point Q(x2, y2) where x2 >= x1 and y2 >= y1.

Let x2 - x1 = x and y2 - y1 = y. The total steps needed to be taken is x + y. Also, it’s fixed that each path will have exactly x RIGHT steps and exactly y UP steps. Different paths can be generated by permuting the UP and RIGHT steps amongst them. The total number of ways to permute x + y items such that x and y of them are identical respectively is given by: (x+y)!/(x!y!) where n! denotes n factorial.
Now, we have found the total number of paths from P to Q. But our aim was to find the total number of good paths from P to Q. We can first find the total number of bad paths and then subtract is from the total number of paths. This will give us the total number of good paths from P to Q.
For a path B to be bad, it has to cross L1 at atleast 1 point. Now, if it touches the line L1 at point (a,b) after crossing L1, it will reach point (a,b+1).

Any general point on L1 is x = y + c , so any general point that a bad path reaches on crossing L1 is given by x = y + c - 1 . Let this line be L2(black dotted line). So we can say that any path B that touches L2 atleast once is a bad path.
Let the first point where B touches L2 is X’. Now take reflection of the segment of B from P till X’ about the line L2 as shown in the figure in green color. Consider a new path B’ : formed by the reflected segment of B and the rest of the unreflected segment of B from X’ to Q i.e. the path from P’ to X’ + the path from X’ to Q.

Now there are 2 important observations about the path B’

  1. Starting point of B’ is always point P’ i.e. reflection of P in L2.
  2. B’ is a path from P’ to Q that always touches the line L2 atleast at one point.

Now, we easily prove by construction that for every bad path B, that touches the line L2 for the first time at X’, we can construct a corresponding path B’ from P’ to Q by : concatenating the reflected segment of B from P to X’ and the segment of B from X’ to Q.
Also, by similar argument, for every path B’ from P’ to Q we can construct a bad path B by again concatenating the reflected segment of B’ from P’ to X’ and the segment of B’ from X’ to Q. So there is a bijection between bad paths B and the paths B from P’ to Q.
Now, to find the number of bad paths we just have to calculate the total number of paths from P’ to Q. So all we are left to do is to find the reflection of P in L2.

 Ex2: Find the reflection of P in L2. 

Figure 3

The above formula can be looked through in any high school book. Using it, reflection of P(x1,y1) in L2: x = y + c - 1 is (y1 + (c - 1), x1 - (c - 1)). Now number of paths from (y1 + (c - 1), x1 - (c - 1)) to Q(x2,y2) can be found using the formula above.
Now, by subtracting it from the total number of paths from P to Q we can get the total number of good paths from P to Q as was required. Let F(x1, y1, x2, y2) gives us this number.
So the final expression for number of paths from P(x1,y1) to Q(x2,y2) without crossing L1: x = y + c is given by
Ways = (x1-x2 + y1-y2)C(x1-x2) - (x1-x2 + y1-y2)C(x1-x2 + (c-1)) .

Now, we have the solution to the first part. But wait! there is one more small exercise for you.

Ex3: How to calculate C(N,K) for N, K <= 4 * 10^6? 

Sol: We can pre-compute and store all the factorials and inverse-factorials for 1 <= i <= 4e6. Now to compute C(N,K) all we have to do is 2 elementary operations:

long long findnCk(N, K) {
    ll nCk = fact[N];
    nCk = (nCk * inv[K]) % MOD;          //where inv[K] is modular inverse of K
    nCk = (nCk * inv[N-K]) % MOD;
    return nCk;
}

But how to compute factorials and inverse-factorials of very large numbers?
Finding factorial for very N can be done in O(N) by simply using the factorial of previous index

fact[i] = (i * fact[i-1]) % MOD;      //where fact[0] = 1 

Now, we have to efficiently find the inverse-factorial. We can this too, using the inverse-factorial of next index as follows.

inv[i] = (inv[i+1]*(i+1))%MOD;   //where inv[4e6] is modular-inverse of fact[4e6]

So the complexity of this pre-computation is O(N) or O(p + q). These are some relevant links: Modular multiplicative inverse
,Fast Exponentiation ,A small intution of the approach.
Now let’s, put P(x1,y1) = (0,0), Q(x2,y2) = (n,n) and making L1: x = y i.e. c = 0 in the above formula, we get 2nCn - 2nC(n-1) which is the expression for nth catalan number(sequence of natural numbers occurring in various counting problems).

Awesome! This just shows how the catalan numbers can be derived. Now, you are good to go with all catalan related problems. :slight_smile:

 Ex4: What is the number of full binary trees with n internal vertices? 

Part 2: Find number of ways to reach point Q(x2, y2) from point P(x1, y1) without going to blocked cells.

The naive way to incorporate the blocked cells is using Inclusion-Exclusion Principle. Let (x,y) be the starting point. The number of ways to get from (x,y) to (m,n) while avoiding the one restricted point at (a,b) is given by the number of ways to get to (m,n) with no restrictions, minus the number of ways to get to (m,n) that go through (a,b).
F(x,y,m,n) - F(x,y,a,b) * F(a,b,m,n)
Generalising, it we can get the total number of ways to reach (m,n) without going to the blocked point.

 Ex5: How? This exercise is left for the user. 

But, such a solution will take 2^m time where m = 10^3. Hence, not feasible. We need to improve.

It is subtle observation that the number of ways of reaching any blocked point (i,j) is independent of any blocked point having larger x or y coordinates. So we can sort the blocked cells on basis of the pair (x,y) in increasing order so that the number of ways to reach a cell in ith index of the array is independent of any cell after it in the array. So we have broken the given bigger problem into smaller subproblems.
Nice enough? Uhhh! wait we also have an optimal substructure in the problem. Let the point P_i at ith index is (x_i, y_i). Actual number of ways to reach

P_i = (ways To Reach P_i Ignoring The Blocked Cells) - (Σ(ways To Reach From P_i To P_j) * (ways To Reach P_j Ignoring The Blocked Cells)).

Hurrah! Now we have a straightforward M^2 dynamic programming solution.

Let’s say our set S = {all Blocked Cells + cell(p,q)}. Sort S on increasing basis of x coordinate and then increasing on y. Also let’s assume dp[i] = F(x,y,x_i,y_i) where (x,y) is the starting point of the path. Pseudo code for it is given below:


for(i = 0; i < S.size(); ++i) 
	for(j = i-1; j >= 0; --j) 
		if(S[i].x >= S[j].x && S[i].y >= S[j].y) 
		     dp[i] -= (dp[j] * F(S[j].x, S[j].y, S[i].x, S[i].y));

The overall complexity is O(M^2 + p + q)

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s /Editorialist’s
Tester

RELATED PROBLEMS:

Part 1
UVA - 932 Safe Salutations
Hackerrank - devu and cool graphs
Codechef - Hand Shake
Codechef - Mock Turtle
Part 2
Codeforces - Count Ways
Codeforces - Research Rover

8 Likes

The dynamic programming part of the problem is almost same of this famous problem

I thought the number points without crossing the line would be a number from catylan triangle and hence was getting WA :frowning:

You did a good job nonetheless. Practice more and get it next time :slight_smile:

1 Like

Can someone please explain how this relation is working? A proof maybe fine. Thank you!!

inv[i] = (inv[i+1](i+1))%MOD;*

What i know is that from extended euclidean algorithm we can do something like this.

inv[1]=1;
for(int i=2;i<=n;i++) 
    inv[i] =  (-(MOD/i)*inv[MOD%i])%MOD + MOD;

Why was I getting TLE in 3 task, @vijju123?..I was solving using 2D dp…


[1]


  [1]: https://www.codechef.com/viewsolution/18308225

I am as clueless as you because i just read the problem and did minor corrects for formatting xD. @vaibhav18197 can help you here :slight_smile:

@vaibhav18197, can u please check my code!!

Can anyone suggest a good fast way to be good at combinatories and counting?

I mean should we study it from some math book,or solve more problems?

3 Likes

Yes. I need tips as well :frowning:

Another related problem: Chef and Big Matrix :slight_smile:

If I am not wrong, the problem doesn’t mention about paths and grid cells anywhere but in the above editorial i am seeing all about grids.

xD . Reduce the problem to path and grids then from the superficial storyline.

2 Likes

D. Knuth will help you! 4 parts of “The Art of programming” is a bible for an algorithmic programmer. You can start with “Concrete Math”(Knuth and Patashnik). https://www.csie.ntu.edu.tw/~r97002/temp/Concrete%20Mathematics%202e.pdf

7 Likes

And here comes the one and only…@mgch xD xD xD xD xD

2 Likes

Thank u sooo much @mgch,u really are an inspiration for us :slight_smile:

This was one hell of a good question. I really suck at these kind of 2D optimization problems. Kudos to the setter :smiley:

Earlier query answer -

In modular maths -

This relation is working because.

(inv[k]*fac[k])\%MOD=1;

\implies (inv[k+1]*fac[k+1])\%MOD=1;

multiply both sides by inv[k]\%MOD;

\implies (inv[k+1]*fac[k+1]*inv[k])\%MOD=inv[k]\%MOD;

\implies (inv[k+1]*(k+1)*fac[k]*inv[k])\%MOD=inv[k]\%MOD;

from (1)

\implies (inv[k+1]*(k+1)*1)\%MOD=inv[k]\%MOD

3 Likes

Thank You very much Sir! I got it.

1 Like

Abra-Kadabra- and we’re done. Have a check for your comment @aryanc403 and tell if any correction is needed.

1 Like

Your code has complexity of pqM. (p*q for the dp and M for find operation in each recursive call)
Constrains for third task were: p,q < 2000 and M < 3000
So it would even exceed 10^9, hence the TLE.

Also, your code was missing the following condition check:
if(good > p or bad > q) return 0;
Hence, your previous submission were getting RE(SIGSEGV). Since it may happen good ~ p + q = 4000 -> that would exceed your array limits.

I incorporated the above mentioned changes in your code & got this code pass 1st subtask.

Hope that helps. :slight_smile:

2 Likes