1.
Introduction
2.
Understanding the Problem
3.
Intuition
3.1.
Code
3.1.1.
Input
3.1.2.
Output
3.2.
Complexities
3.2.1.
Time Complexity
3.2.2.
Space Complexity
4.
Optimizing the above approach
5.
Efficient Code
5.1.
Input
5.2.
Output
6.
Complexities
6.1.
Time Complexity
6.2.
Space Complexity
7.
FAQs
8.
Key Takeaways
Last Updated: Mar 27, 2024

# Bee Mesh

Saksham Gupta
0 upvote

## Introduction

Maths is a very fun subject to study, and so is programming, but what happens when these two are combined together? Today, we will discuss one such problem, i.e., Bee Mesh, where your concepts related to programming and maths would be judged. Now let's see the problem statement in detail.

## Understanding the Problem

We have been given a square Bee mesh 'MESH' of size N * N, which is used to cover a particular window. We are also told that there are 'M' holes in this mesh. Holes in this mesh refer to an L * L square. The centers of the holes lie on the main diagonal of the window.

Now our Ninja bee is at MESH(0, 0) and wants to go till MESH(N, N). In a single step, our bee can either right or up. i.e., if the bee is at a point, let's say MESH(x,y), then it can only go to MESH(x + 1, y) and MESH(x, y + 1), but it is not allowed to go inside any hole or outside of the mesh. Our task is to count the number of distinct paths that the bee can take to reach its destination.

Also see, Euclid GCD Algorithm

## 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

1. 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.

2. 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.

3. 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.

4. 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.

5. 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!

Live masterclass