PROBLEM LINK: Time Travel
Author: Pankaj Sharma
Tester: Abhishek Jugdar
Editorialist: Abhishek Jugdar
DIFFICULTY:
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.