Pyramid Traversal PYRAMIDMOVES Solution Codechef

Pyramid Traversal PYRAMIDMOVES Solution

You are given a pyramid of the following form with an infinite number of rows:

From a cell, you can move to either the bottom-left cell or the bottom-right cell directly in contact with the current one (For example, you can make the following moves: 1→2,1→3,6→9,6→10, while you cannot make moves 2→6 or 2→7).

You are given a starting cell s and an ending cell e. Starting at cell s, find the number of ways to reach cell e. This number can be large, so print the answer modulo 10⁹+7.

Two ways are said to be different if there exists at least one cell which was visited in one of the ways but not the other one.

Input Format

• The first line of input contains a single integer T, the number of test cases. The description of T test cases follows.
• The first and only line of each test case contains two space-separated integers s and e, denoting the starting and the ending cell respectively.

Output Format

For each test case, output a single line containing one integer: the number of ways to go from s to ee modulo 10⁹+7.

Constraints

• 1≤T≤1000
• 1≤s,e≤10⁹

Subtasks

Subtask 1(100 points): Original constraints

Sample Input 1

3
2 7
1 5
5 3

Sample Output 1

1
2
0

Explanation

In the first test case, there exists only 1 way to move from 2 to 7, which is:

• 2→4→7

In the second test case, there exist 2 ways to move from 1 to 5, which are:

• 1→2→5
• 1→3→5

In the third test case, it is not possible to move from 5 to 3.

SOLUTION

Program Python: Pyramid Traversal PYRAMIDMOVES Solution in Python

def ncr(n, r, p):
    # initialize numerator
    # and denominator
    num = den = 1
    for i in range(r):
        num = (num * (n - i)) % p
        den = (den * (i + 1)) % p
    return (num * pow(den,
            p - 2, p)) % p
def getcoord(num):
    y=int((2*num+0.25)**0.5+0.5)
    x=int(num-(y*(y-1))/2)
    if x==0:
        y-=1
        x=y
    return (x,y)
    
T=int(input())
for i in range(T):
    (s,e)=map(int,input().split())
    E=getcoord(e)
    S=getcoord(s)
    n=E[1]-S[1]
    r=E[0]-S[0]
    if n<1 or r<0 or n<r: print(0)
    else : print(ncr(n, r, 10**9 +7))

Program C++: Pyramid Traversal PYRAMIDMOVES Solution in C++

#include <iostream>
#include<cmath>
using namespace std;
typedef long long int lli;
typedef long long ll;
const lli mod7 = 1e9 + 7;
const int MAXF = 1e5;
lli fact [MAXF + 1];
lli last_elem(lli lvl)
{
    return ((lvl + 1)*lvl) / 2;
}
ll powmod(ll a, ll b, ll p){
    a %= p;
    if (a == 0) return 0;
    ll product = 1;
    while(b > 0){
        if (b&1){    // you can also use b % 2 == 1
            product *= a;
            product %= p;
            --b;
        }
        a *= a;
        a %= p;
        b /= 2;    // you can also use b >> 1
    }
    return product;
}
ll inv(ll a, ll p){
    return powmod(a, p - 2, p);
}
ll nCk(ll n, ll k, ll p){
    return ((fact[n] * inv(fact[k], p) % p) * inv(fact[n-k], p)) % p;
}
pair<lli,lli> get_lvl_idx(lli n)
{
    lli lvl =-1;
    lli idx = -1;
    
    if(n==1)
    {
        return {1,1};
    }
    lli st=2;
    lli  end = 1LL + ceil(sqrt(2*n));
    while(st<=end)
    {
        lvl= (st+end)/2;
        if(last_elem(lvl)>=n && last_elem(lvl-1)<n)
        {
            break;
        }
        else if(last_elem(lvl)>n)
        {
            end = lvl - 1;
        }
        else
        {
            st = lvl + 1;
        }
    }
    idx = n - (lvl*(lvl-1))/2;
    return {lvl,idx};
}
int main() {
	// your code goes here
	fact[0]=1;
	fact[1]=1;
	for(int i=2;i<=MAXF;i++)
	{
	    fact[i] = fact[i-1]*i % mod7;
	}
	int t;
	cin>>t;
	while(t--)
	{
	    lli s,e;
	    cin>>s>>e;
	    pair<lli, lli> res1, res2;
	    res1 = get_lvl_idx(s);
	    res2 = get_lvl_idx(e);
	    lli slvl = res1.first;
	    lli sidx = res1.second;
	    lli elvl = res2.first;
	    lli eidx = res2.second;
	    lli L = elvl - slvl;
	    lli K = eidx - sidx;
	    lli ans = -1;

	    if(L<=0 || K<0 || K>L)
	    {
	        ans=0;
	    }
	    else
	    {
	        ans = nCk(L,K,mod7);
	    }
	    cout<<ans<<endl;
	}
	return 0;
}

December Long Challenge 2021 Solution

• List of Lists LISTLIST Solution Codechef
• Valleys and Hills VANDH Solution Codechef
• Rock Paper Scissors ROPASCI Solution Codechef
• Squares Counting GRIDSQRS Solution Codechef
• Pyramid Traversal PYRAMIDMOVES Solution Codechef
• Increasing String INCREAST Solution Codechef
• Utkarsh and Placement tests UTKPLC Solution Codechef
• Check Mate CHECKMATE Solution Codechef