Intuition
Any path from MESH(0, 0) to MESH(N, N) can be broken down into paths from (0, 0) → (x, N − x) and (x, N − x) → (N, N). This is because point P(x, N − x) is a point on the main diagonal having x as its y coordinate. Now with this thing in mind let's look at the approach towards the problem.
For each point, P : (x, N − x) which is reachable from (0,0) (i.e., does not lie inside the hole).
The number of paths from MESH(0, 0) to MESH(N, N), which passes through P, is the same as the product of the number of paths from MESH(0, 0) → P and the number of paths from P → MESH(N, N).
The number of paths from MESH(0, 0) → MESH(x, N − x) is the same as
N! / (N - x)! (
)
The number of paths from P(X, N − X) →T(N, N) is the same as
N! / (N - x)! ()
Hence the number of paths from S to T passing through P is () ^ 2. We can add the values for all such reachable P to get the final answer.
Code
#include <bits/stdc++.h>
#define mod 1000000007
#define ll long long
using namespace std;
/* This function is used to calculate the value of Ncr. */
int NcR(int n, int r)
{
long long p = 1, k = 1;
if (n - r < r)
r = n - r;
if (r != 0)
{
while (r)
{
p *= n;
k *= r;
long long m = __gcd(p, k);
p /= m;
k /= m;
n--;
r--;
}
}
else
p = 1;
return p;
}
int main()
{
int n, m;
cin >> n >> m;
bool vis[100005] = { 0 };
int last = 1;
/* Taking the input for holes.*/
int i = 0;
while (i <= m)
{
int x, l;
cin >> x >> l;
int j = x + 1;
while (j < x + l)
{
vis[j] = 1;
j++;
}
last = x + l;
i++;
}
ll ans = 0;
for (int i = 0; i <= n; i++)
{
/* If it's not visited. */
if (!vis[i])
{
ll val = NcR(n, i);
/* Using mod as the answer can be very large. */
ans += (val *val) % mod;
ans %= mod;
}
}
cout << ans << endl;
return 0;
}
Input
10 2
1 2
5 3
Output
124231
Complexities
Time Complexity
O(N * N * log(N) ,
Reason: NcR function costs us R * log(N) time. In the worst case, it would cost us O(N * log(N)) time. As we are looping through N elements, the overall time complexity to O(N) * O(N * log(N)) ~ O(N * N * log(N)).
Space Complexity
O(1)
Reason: We are not using any external space.
Optimizing the above approach
Now we will see how we can further reduce the complexity of this program by reducing the time complexity of NcR function. Precomputing the inverse of factorials is an efficient way to reduce a better technique to an efficient one. In O(n) time, compute the inverse of the factorial, and then answer requests in O(1) time. The modular multiplicative inverse can compute the inverse of 1 to N natural numbers in O(n) time.
Efficient Code
#include <bits/stdc++.h>
#define mod 1000000007
#define ll long long
using namespace std;
ll fact[100005];
/* This is used to return inversePower. */
ll inversePower(ll x)
{
ll res = 1;
ll y = mod - 2;
while (y)
{
if ((y) &1) res = (res *x) % mod;
x = (x *x) % mod;
(y) >>= 1;
}
return res;
}
/* This function will return NcR for given N and R. */
ll NcR(ll n, ll r)
{
return (fact[n] *(inversePower((fact[r] *fact[n - r]) % mod))) % mod;
}
/* This function is used to calculate the value of Ncr. */
int NcR(int n, int r)
{
long long p = 1, k = 1;
if (n - r < r)
r = n - r;
if (r != 0)
{
while (r)
{
p *= n;
k *= r;
long long m = __gcd(p, k);
p /= m;
k /= m;
n--;
r--;
}
}
else
p = 1;
return p;
}
int main()
{
int n, m;
cin >> n >> m;
fact[0] = 1;
for (ll i = 1; i <= n; i++)
{
fact[i] = (fact[i - 1] *i) % mod;
}
bool vis[100005] = { 0 };
int last = 1;
/* Taking the input for holes.*/
int i = 0;
while (i <= m)
{
int x, l;
cin >> x >> l;
int j = x + 1;
while (j < x + l)
{
vis[j] = 1;
j++;
}
last = x + l;
i++;
}
ll ans = 0;
for (int i = 0; i <= n; i++)
{
/* If it's not visited. */
if (!vis[i])
{
ll val = NcR(n, i);
/* Using mod as the answer can be very large. */
ans += (val *val) % mod;
ans %= mod;
}
}
cout << ans << endl;
return 0;
}
Input
10 2
1 2
5 3
Output
124231
Complexities
Time Complexity
O(N)
Reason: In the worst case, NcR function would cost us O(1) time. As we are looping through N elements, the overall time complexity to O(N) * O(1) ~ O(N).
Space Complexity
O(1)
Reason: We are not using any external space.
FAQs
-
To what extent should I learn combinatorics?
Combinatorics is a vast mathematical topic and has loads of things in it. From the programming point of view, basics like NcR, Permutations, Combinations are enough.
-
What is meant by permutations and combinations?
A collection of items can be represented in two ways: permutation and combination. Both are distinct. We term it as a combination when the order of the elements doesn't matter. We have a permutation if the order does matter. A permutation is also known as an ordered combination.
-
What is the difference between linear arrangements and cyclic arrangements of objects?
In the linear arrangements, we have a starting point and endpoint. But, in the case of a cyclic arrangement, we have a reference position, and we identify all other positions uniquely by their distance and direction from the reference point.
-
Where are the combinations used?
We usually use combinations at places where we have to select a group of objects without considering their order of arrangements otherwise we use permutations.
-
What is the best way to find out the value of NcR?
Precomputing the inverse of factorials is an efficient way to reduce a better technique to an efficient one. In O(n) time, compute the inverse of the factorial, and then answer requests in O(1) time. The modular multiplicative inverse can compute the inverse of 1 to N natural numbers in O(n) time.
Key Takeaways
We saw how we solved the problem 'Bee Mesh' using combinatorics. Some other problems that can be solved using combinatorics are the Count Number of Valid Parentheses, the Number of ways you can always stay either above or below the main diagonal, etc. Now don't waste any more time and head over to our practice platform Coding Ninjas Studio to practice top problems on every topic, interview experiences, and many more. Till then, Happy Coding!
38+ registered 