MAGICSTONE - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: Lavish Gupta
Testers: Satyam, Abhinav Sharma
Editorialist: Nishank Suresh

DIFFICULTY:

To be calculated

PREREQUISITES:

Computing binomial coefficients modulo a prime

PROBLEM:

There is a stone of mass 2^N, initially lying at the origin. For the next N seconds, each stone of mass M at position X splits into one stone of mass \frac{M}{2} going to position X-1 and another of mass \frac{M}{2} going to position X+1.

Given L and R, find for each position i such that L \leq i \leq R how many stones lie at position i at the end of the process.

EXPLANATION:

Hint

Think of the stone of mass 2^N as being 2^N separate stones of mass 1. Encode the movement of each stone as a binary string of length N, distinct stones receiving distinct strings. Now relate this encoding to the final position.

Full solution

Instead of stones halving in mass, it becomes a bit easier to think of the problem as involving 2^N stones, each of mass 1. The given operation then essentially says that at each position, half the stones present there move left and the other half move right.

Now note that the movement of any given stone can be represented by a binary string of length N — the i-th character of the string is 1 if this stone moved right on the i-th move, and 0 if it moved left.

Under this setup, it’s easy to see that no two stones will receive the same binary string, i.e, no two stones have the exact same movement pattern.

Proof

This can be proved by induction on N. If N = 1 the result is trivial, since there are 2 stones, one moving left and the other moving right on the only move made.

For N > 1, after the first move there are 2^{N-1} stones on -1 and 2^{N-1} on +1. Clearly, any pair consisting of a stone at -1 and a stone at +1 has different binary strings, since the very first character differs.

Now, consider only those stones at -1. They correspond to the process with N-1 and hence any two within this pile will also differ eventually, by the inductive hypothesis. Similarly, any two stones at +1 will also differ eventually.

With 2^N stones and 2^N binary strings, it’s easy to see that there is a bijective mapping between stones and binary strings.

Now, we use this information to actually solve the problem at hand.
Consider a stone such that its binary string has x ones and y zeros.
It made x steps right and y steps left, which means it ended up at position x - y.

Let’s turn that around. Suppose we fix a position k. How many stones ended up at position k?

Well, we know that if a stone made x steps right and y steps left and then ended up at k, we must have x - y = k.
On the other hand, clearly we also have x + y = N, the total number of moves made.

Note that these equations give us a unique solution for the pair (x, y) — namely, x = \frac{k + N}{2} and y = \frac{N - k}{2}. Of course, x and y do need to be integers, so if k and N have different parities then no stone can end up at position k.

Now, say we fix position k and calculate x and y. How many stones have binary strings corresponding to this x and y?
As established earlier, each binary string corresponds to a single stone and vice versa, which means that all we need to do is to compute the number of binary strings of length N consisting of x ones and y zeros!

A simple combinatorial argument shows that this number is just \binom{x+y}{x} = \binom{N}{x} — choose which x of the N positions are ones, and the others are automatically fixed to contain zeros.

Note that the binomial coefficient needs to be calculated modulo 10^9 + 7, so if you don’t know how to do that a tutorial has been linked above.

TIME COMPLEXITY:

\mathcal{O}(N\log MOD) or \mathcal{O}(N) per test.

CODE:

Setter (C++)
#define ll long long
#define dd long double
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define mp make_pair
#define mt make_tuple
#define fo(i , n) for(ll i = 0 ; i < n ; i++)
#define tll tuple<ll ,ll , ll> 
#define pll pair<ll ,ll> 
#include<bits/stdc++.h>
/*#include<iomanip>   
#include<cmath>
#include<cstdio>
#include<utility>
#include<iostream>
#include<vector>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<set>
#include<stack>
#include<bitset>*/
dd pi = acos(-1) ;
ll z =  1000000007 ;
ll inf = 10000000000000 ;
ll p1 = 37 ;
ll p2 = 53 ;
ll mod1 =  202976689 ;
ll mod2 =  203034253 ;
ll fact[1000005] ;
ll gdp(ll a , ll b){return (a - (a%b)) ;}
ll ld(ll a , ll b){if(a < 0) return -1*gdp(abs(a) , b) ; if(a%b == 0) return a ; return (a + (b - a%b)) ;} // least number >=a divisible by b
ll gd(ll a , ll b){if(a < 0) return(-1 * ld(abs(a) , b)) ;    return (a - (a%b)) ;} // greatest number <= a divisible by b
ll gcd(ll a , ll b){ if(b > a) return gcd(b , a) ; if(b == 0) return a ; return gcd(b , a%b) ;}
ll e_gcd(ll a , ll b , ll &x , ll &y){ if(b > a) return e_gcd(b , a , y , x) ; if(b == 0){x = 1 ; y = 0 ; return a ;}
ll x1 , y1 , g; g = e_gcd(b , a%b , x1 , y1) ; x = y1 ; y = (x1 - ((a/b) * y1)) ; return g ;}
ll power(ll a ,ll b , ll p){if(b == 0) return 1 ; ll c = power(a , b/2 , p) ; if(b%2 == 0) return ((c*c)%p) ; else return ((((c*c)%p)*a)%p) ;}
ll inverse(ll a ,ll n){return power(a , n-2 , n) ;}
ll max(ll a , ll b){if(a > b) return a ; return b ;}
ll min(ll a , ll b){if(a < b) return a ; return b ;}
ll left(ll i){return ((2*i)+1) ;}
ll right(ll i){return ((2*i) + 2) ;}
ll ncr(ll n , ll r){if(n < r|| (n < 0) || (r < 0)) return 0 ; return ((((fact[n] * inverse(fact[r] , z)) % z) * inverse(fact[n-r] , z)) % z);}
void swap(ll&a , ll&b){ll c = a ; a = b ; b = c ; return ;}
//ios_base::sync_with_stdio(0);
//cin.tie(0); cout.tie(0);
using namespace std ;
#include <ext/pb_ds/assoc_container.hpp> 
#include <ext/pb_ds/tree_policy.hpp> 
using namespace __gnu_pbds; 
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(val)  no. of elements strictly less than val
// s.find_by_order(i)  itertor to ith element (0 indexed)
//__builtin_popcount(n) -> returns number of set bits in n
ll seed;
mt19937 rnd(seed=chrono::steady_clock::now().time_since_epoch().count()); // include bits

void initialize()
{
    fact[0] = 1 ;
    for(ll i = 1 ; i < 1000005 ; i++)
        fact[i] = (fact[i-1]*i)%z ;
    return ;
}

ll get_ans(ll n, ll x)
{
    ll one = n+x ;
    if(one%2 == 1)
        return 0 ;
    one /= 2 ;

    ll min_one = n - one ;

    return ncr(n , one) ;
}
 
void solve()
{
    ll n, l, r ;
    cin >> n >> l >> r ;
    for(ll i = l ; i <= r ; i++)
    {
        ll ans = get_ans(n , i) ;
        if(i == l)
            cout << ans ;
        else
            cout << ' ' << ans ;
    }
    cout << endl ;
    return ;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("inputf.txt" , "r" , stdin) ;
    freopen("outputf.txt" , "w" , stdout) ;
    freopen("error.txt" , "w" , stderr) ;
    #endif

    initialize() ;
    
    int t ;
    cin >> t ;
    while(t--)
        solve() ;
    
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
 
    return 0;
}
Tester (C++)
#include <bits/stdc++.h>
using namespace std;
 
 
/*
------------------------Input Checker----------------------------------
*/
 
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
 
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }
 
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }
 
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
 
 
/*
------------------------Main code starts here----------------------------------
*/
 
const int MAX_T = 1e5;
const int MAX_N = 1e5;
const int MAX_SUM_LEN = 1e5;
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define mp make_pair
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
#define pb push_back
 
int sum_n = 0, sum_m = 0, sum = 0;
int max_n = 0, max_m = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;
ll mod = 1000000007;

using ii = pair<ll,ll>;

ll po(ll x, ll n ){ 
    ll ans=1;
     while(n>0){
        if(n&1) ans=(ans*x)%mod;
        x=(x*x)%mod;
        n/=2;
     }
     return ans;
}


const ll MX=2000000;
ll fac[MX], ifac[MX];

void pre(){
 fac[0]=1;
 rep_a(i,1,MX) fac[i]= (i*fac[i-1])%mod;
 rep(i,MX) ifac[i]= po(fac[i], mod-2);
}

ll ncr(ll n, ll r){
 if(r>n || r<0 || n<0) return 0;
 return (fac[n]*((ifac[r]*ifac[n-r])%mod))%mod; 
}

void solve()
{   
   
    int n = readIntSp(1,1e6);
    int l = readIntSp(-n,n);
    int r = readIntLn(-n,n);
    assert(l<=r);

    sum_n+=(r-l+1);

    l+=n;
    r+=n;
    if(l&1){
        cout<<0<<" ";
        l++;
    }
    int f = 0;
    if(r&1) f=1;

    l/=2;
    r/=2;

    rep_a(i,l,r) cout<<ncr(n,i)<<" 0 ";
    cout<<ncr(n,r)<<" ";
    if(f) cout<<'0';
    cout<<'\n';

}
 
signed main()
{

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r" , stdin);
    freopen("output.txt", "w" , stdout);
    #endif
    fast;
    
    int t = 1;
    
    t = readIntLn(1,100);
    pre();
    for(int i=1;i<=t;i++)
    {    
       solve();
    }
   
    assert(getchar() == -1);
    assert(sum_m<=1e5);
 
    cerr<<"SUCCESS\n";
    cerr<<"Tests : " << t << '\n';
    // cerr<<"Sum of lengths : " << sum_m <<'\n';
    // cerr<<"Maximum length : " << max_n <<'\n';
    // // cerr<<"Total operations : " << total_ops << '\n';
    // cerr<<"Answered yes : " << yess << '\n';
    // cerr<<"Answered no : " << nos << '\n';

    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}
Editorialist (Python)
MAXN = 10**6 + 10
mod = 10**9 + 7

fac = [i for i in range(MAXN)]
fac[0] = 1
for i in range(1, MAXN):
	fac[i] *= fac[i-1]
	fac[i] %= mod

ifac = [0 for i in range(MAXN)]
ifac[-1] = pow(fac[-1], mod-2, mod)
for i in range(MAXN-2, -1, -1):
	ifac[i] = (i+1)*ifac[i+1]
	ifac[i] %= mod

def C(n, r):
	if n < 0 or r < 0 or r > n:
		return 0
	return (fac[n] * ifac[r] * ifac[n-r])%mod

for _ in range(int(input())):
	n, L, R = map(int, input().split())
	for i in range(L, R+1):
		if (n + i)%2 == 0:
			x = (n + i)//2
			print(C(n, x), end = ' ')
		else:
			print('0 ', end = '')
	print('')
1 Like

This is the same as Pascal’s triangle, right?
Working on small test cases should reveal that. Pretty much not suitable for long challenges, I feel.

2 Likes

I had the idea of Pascal’s triangle as well, but it doesn’t seem to be working, even on the last sample.
Solution: 64421147 | CodeChef
Can anyone please guide as to why this is failing?

When working modulo some number M, you cannot simply divide using the / operator because (for the most part) it makes no sense (unlike addition, subtraction, and multiplication which do make sense).

For example, 4 \equiv 9 \pmod 5, but 9 is divisible by 3 and 4 isn’t, so what does dividing by 3 mean in this case? You might also notice that ignoring this issue and simply dividing gives you \left \lfloor \frac{4}{3} \right \rfloor = 1 and \frac{9}{3} = 3, which aren’t equal modulo 5.

Modulo M, the concept of division is instead emulated by modular multiplicative inverses. Here is a very brief introduction to the concept, including how to compute them when they exist. The article I linked in the prerequisites section of the editorial also details how to apply this to compute binomial coefficients in general, which I recommend going through if the concept is new.

1 Like