Pyramid Traversal PYRAMIDMOVES Solution Codechef

Page Contents

Pyramid Traversal PYRAMIDMOVES Solution

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

2 3

4 5 6

7 8 9 10

………………….

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→101→2,1→3,6→9,6→10, while you cannot make moves 2→62→6 or 2→72→7).

You are given a starting cell ss and an ending cell ee. Starting at cell ss, find the number of ways to reach cell ee. This number can be large, so print the answer modulo 109+7109+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 TT, the number of test cases. The description of TT test cases follows.
The first and only line of each test case contains two space-separated integers ss and ee, 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 ss to ee modulo 109+7109+7.

Constraints

1≤T≤10001≤T≤1000
1≤s,e≤1091≤s,e≤109

Subtasks

Subtask 1(100 points): Original constraints

Sample Input 1

Sample Output 1

1
2
0

Explanation

In the first test case, there exists only 11 way to move from 22 to 77, which is:

2→4→72→4→7

In the second test case, there exist 22 ways to move from 11 to 55, which are:

1→2→51→2→5
1→3→51→3→5

In the third test case, it is not possible to move from 55 to 33.

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;
}