# PROBLEM LINK: Time Travel

Author: Pankaj Sharma
Tester: Abhishek Jugdar
Editorialist: Abhishek Jugdar

MEDIUM-HARD

# PREREQUISITES:

Math, Combinatorics, Sorting

# PROBLEM:

Find the number of paths from (X_{initial},Y_{initial}) to (X_{final},Y_{final}) such that it always passes through all the given S coordinates and avoids all the given K coordinates.

# EXPLANATION:

Building some base to approach the solution

Sort all the S points according to x-coordinate first and then by y-coordinate.
Append (X_{initial},Y_{initial}) to start the array and append (X_{final},Y_{final}) to end of the array. Lets name the array Points.

Preliminary case of no paths

If all Points cells cannot be traversed, in the present order, then answer will directly be -1. But, even if this condition is satisfied, the answer can be -1 even later on.
To check for this case - traverse the array and check the following condition :
The x and y coordinates should be non-decreasing respectively throughout the array. If not answer will -1, since we can’t return back, due to restriction of only moving forward in both x and y

Solution for all other cases

Now start traversing the points in the above order. Let ways[0] be no. of ways of reaching Points[1] from Points[0], ways[1] be no. of ways of reaching Points[2] from Points[1]. The final answer will be multiplication of all waysi for all i = 0 to Points.size() - 1.

So now we have reduced the problems to solving for sub-grids. So basically, we now have to find no. of paths in a grid such that x cells are blocked. We will show how to do it for 1 such sub-grid.
Consider s (s.x, s.y) as the starting point of that sub-grid and e (e.x, e.y) as the end point.

The blocked cell at (x,y) will only affect all cells, which have both coordinates greater than or equal to (x,y). We will now propose a method to calculate the no. of paths to reach end point e.

How to solve for a sub-grid?
Some basic info

No. of paths from (x1, y1) to (x2, y2) are \frac{(x2 - x1+ y2-y1)!}{(x2 - x1)!(y2-y1)!}. How? Try to figure it out, try for eg, (1,1) to (N,M).

Approach

Find all the blocked cells which lie within our sub-grid. Sort the blocked cells according to x first, then by y. Append the end point e to this set of points. Lets denote this set of points as w.

Maintain an array res, where res[i] denotes no. of ways to reach point w[i] from starting point s. Following code snippet will make it clear as to how we calculate the required answer, by subtracting contributions from the blocked cells. Sorting is essential as to subtract the contributions in correct order.

Code snippet

calc(x1, y1, x2, y2) calculates the no. of paths from (x1,y1) to (x2,y2) if there were no blocked cells. How does calc work ? See basic info section.

    for(int j = 0; j < w.size() - 1; j++) {
for(int l = j + 1; l < w.size(); l++) {
if(w[j].f <= w[l].f && w[j].s <= w[l].s) // Acc to above mentioned approach, w[j] affects w[l] if it follows this condition. Subtract its contribution from res[l].
res[l] -= res[j] * calc(w[j].f, w[j].s, w[l].f, w[l].s)));
}
}


In this manner we have calculated way[i] which will be equal to res[w.size() - 1]. After the way[i] has been calculated, all you need to do is multiply ans by way[i], i.e ans *= way[i].

Calculate the answer for each sub-grid and multiply them to get the final result.

Time Complexity

Time complexity - O(K2)

Things to look out for
• Even after we have checked for the preliminary no-path case, its still possible that ans comes out to be 0. The output is going to be -1 for such a case.
• Since the output is modulo 1e9 + 7, be careful of any overflows in between computations.

# SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(x) (x).begin(), (x).end()
#define MOD                 1000000007
#define modA(a,b)           (((a%MOD)+(b%MOD))%MOD)
#define modS(a,b)           (((((a%MOD)-(b%MOD))%MOD)<0)?(ll)(MOD+((a%MOD)-(b%MOD))%MOD):(ll)(((a%MOD)-(b%MOD))%MOD))
#define modM(a,b)           (ll)((((ll)(a%MOD))*((ll)(b%MOD)))%MOD)
ll max(ll a, ll b) {return (a > b ? a : b);}
ll min(ll a, ll b) {return (a < b ? a : b);}
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1) { cerr << name << " : " << arg1 << '\n'; }
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args) {
const char* comma = strchr(names + 1, ',');
cerr.write(names, comma - names) << " = " << arg1 << " | "; __f(comma + 1, args...);
}

const int N = 2e5 + 5;
ll fac[N];
ll power(ll x, ll y, ll p)
{
ll res = 1;
x = x % p;

while (y > 0)
{
if (y & 1)
res = (res * x) % p;

y = y >> 1;
x = (x * x) % p;
}
return res;
}

ll modInverse(ll n, ll p)
{
return power(n, p - 2, p);
}
// function to calculate ncr%p
ll nCr(ll n, ll r, ll p)
{
if (r == 0)
return 1;
return (fac[n] * modInverse(fac[r], p) % p *
modInverse(fac[n - r], p) % p) % p;
}
// F will give no of possible paths from x1,y1 to x2,y2
ll F(ll x1, ll y1, ll x2, ll y2)
{
ll p = 1e9 + 7;
ll x = x2 - x1  ;
ll y = y2 - y1  ;
ll n = x + y, r = y;
ll ans = nCr(n, r, p);
return ans;
}
// calculating no of paths between start and end having some blocked coordinates.
//
ll  calculate(vector<pair<ll, ll>> &points)
{
ll p = 1e9 + 7;
int n = points.size();
vector<int> ans(n, 1);
for (int i = 1; i < n; i++)
{
ll x = F(points[0].first, points[0].second, points[i].first, points[i].second);
ans[i] = x;

}

for (int i = 1; i < n - 1; i++)
{
for (int j = i + 1; j < n; j++)
{
if (points[j].first < points[i].first || points[j].second < points[i].second)
{
continue;
}
// substracting invalid paths of i to j
ll value = F(points[i].first, points[i].second, points[j].first, points[j].second);
ans[j] = modS(ans[j], modM(ans[i] , value));
}
}

return ans[n - 1];

}
void solve()
{

ll n;
ll st_x, end_x, st_y, end_y;
cin >> st_x >> st_y >> end_x >> end_y;
ll s, k;
cin >> s >> k;
vector<pair<pair<ll, ll>, ll>> points;
points.push_back({{st_x, st_y}, 1});
ll ans = 1;
// we will mark all safe points infinity stone one ,start ,end as 1 and rest as 0
for (int i = 0; i < s + k; i++)
{
ll u, v;
cin >> u >> v;
if (i < s)
points.push_back({{u, v}, 1});
else
points.push_back({{u, v}, 0});

}
points.push_back({{end_x, end_y}, 1});
sort(all(points));
ll prev = -1, now = -1;
vector<pair<ll, ll>> temp;
n = points.size();
// we are calculating no of possible paths between two infinity stones /start / end
//
for (int i = 0; i < n; i++)
{
if (points[i].second == 1)
{
if (prev == -1)
{
prev = i;
}
else
{
temp.push_back({points[i].first.first, points[i].first.second});

ll u = calculate(temp);
ans = modM(ans, u);
if (ans == 0)
break;
prev = i;
temp.clear();
}
}

if (prev != -1)
temp.push_back({points[i].first.first, points[i].first.second});

}
if (ans == 0)
ans = -1;
cout << ans << "\n";
}
int main()
{

ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
fac[0] = 1;
ll p = 1e9 + 7;
for (ll i = 1 ; i <= N - 1; i++)
fac[i] = (fac[i - 1] * i) % p;

int t;
cin >> t;
while (t--)
solve();
return 0;
}

Tester's Solution
#include <bits/stdc++.h>
#define ll long long int
#define ld long double
#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define mk make_pair
#define mt make_tuple
#define MOD 1000000007
#define fo(i,a,b) for(i=a;i<b;i++)
#define foe(i,a,b) for(i=a;i<=b;i++)
#define all(x) x.begin(), x.end()
#define vi vector<int>
#define vl vector <long long int>
#define pii pair <int,int>
#define pll pair <long long int, long long int>
#define vpii vector< pair<int,int> >
#define vpll vector < pair <long long int,long long int> >
#define boost ios::sync_with_stdio(false); cin.tie(0)
using namespace std;
const int inf = 1e9 + 5;
const ll inf64 = 1e18 + 5;

ll add(ll x, ll y) {ll res=x+y; return(res>=MOD?res-MOD:res);}
ll mul(ll x, ll y) {ll res=x*y; return(res>=MOD?res%MOD:res);}
ll sub(ll x, ll y) {ll res=x-y; return(res<0?res+MOD:res);}
ll lcm(ll x, ll y) {ll res=(x*y)/__gcd(x,y); return res;}
ll power(ll x, ll y) {ll res=1; x%=MOD; while(y){if(y&1)res=mul(res,x); y>>=1; x=mul(x,x);} return res;}

const int MAX = 2e5 + 5;
ll fact[MAX], invf[MAX];
ll nCr(ll n, ll r){if(n<r||n<0||r<0)return 0; return mul(fact[n],mul(invf[n - r],invf[r]));}
void preprocess()
{
fact[0] = 1;
invf[0] = 1;
for(ll i = 1; i < MAX; i++){
fact[i] = mul(fact[i - 1], i);
invf[i] = power(fact[i], MOD - 2);
}
}
ll calc(int x1, int y1, int x2, int y2)
{
int x = x2 - x1 + 1, y = y2 - y1 + 1;
ll num = fact[x + y - 2];
ll den = mul(fact[x - 1], fact[y - 1]);
ll res = mul(num, power(den, MOD - 2));
return res;
}
int main()
{
boost;
preprocess();
int t, s, k, i;
cin >> t;
while(t--)
{
int x1, y1, x2, y2;
cin >> x1 >> y1 >> x2 >> y2;
cin >> s >> k;

vector <pii> v;
vector <pii> b;

fo(i, 0, s) {
int x, y;
cin >> x >> y;
v.pb({x, y});
}
fo(i, 0, k) {
int x, y;
cin >> x >> y;
b.pb({x, y});
}

sort(all(v), [&](const pii &p1, const pii &p2){if(p1.f == p2.f) return p1.s < p2.s; return p1.f <  p2.f;});

v.pb({x2, y2});
reverse(all(v));
v.pb({x1, y1});
reverse(all(v));

bool ok = 1;
for(int i = 0; i + 1 < v.size(); i++) {
if(v[i].f > v[i + 1].f || v[i].s > v[i + 1].s) {
ok = 0;
break;
}
}
if(!ok) cout << -1 << '\n';
else {
ll ans = 1;
for(int i = 0; i + 1 < v.size(); i++) {
pii st = v[i], en = v[i + 1];

vector <pii> w;
for(int j = 0; j < b.size(); j++) {
if(st.f <= b[j].f && b[j].f <= en.f && st.s <= b[j].s && b[j].s <= en.s)
w.pb(b[j]);
}
sort(all(w), [&](const pii &p1, const pii &p2){if(p1.f == p2.f) return p1.s < p2.s; return p1.f < p2.f;});
w.pb(en);

int sz = w.size();
ll res[sz];

for(int j = 0; j < sz; j++)
res[j] = calc(st.f, st.s, w[j].f, w[j].s);

for(int j = 0; j < sz - 1; j++) {
for(int l = j + 1; l < sz; l++) {
if(w[j].f <= w[l].f && w[j].s <= w[l].s)
res[l] = sub(res[l], mul(res[j], calc(w[j].f, w[j].s, w[l].f, w[l].s)));
}
}
ans = mul(ans, res[sz - 1]);
}
cout << (ans == 0 ? -1 : ans) << '\n';
}
}
}


If you have any doubts regarding the explanation, feel free to ask them below.

2 Likes

Can you move the problems to Practice Section?

@abhi2402 Can it is possible that number of paths comes out to be a multiple of 1e9+7. In this case answer should be 0 but we will print -1.

1 Like

We have mailed CC regarding moving the problems to practice. Hopefully it will be done soon.

Wow, thanks for pointing that out! I am myself curious whether such a case will occur, and i believe it may occur, cause we are using modular subtraction, and it may become 0. I will try to investigate more about this, and it would be highly appreciable if someone could actually suggest such a test!

1 Like

Hi @samarth2017 . All the problems have been moved to practice section. You can make a submission now!

1 Like