Editorial: Programming Contest #1 (Chapter 'Ramayan')


Problem: Raavan and Sub-Array
Problem Setter: @pallove_227

Logic (Explanation)

Bitwise-XOR of any number, X with 0 is equal to the number itself (X).

So, if we set the first element of the Array A as X, and the next K-1 elements as 0, then we will have the XOR of first sub-array of length K, equal to X, which is required.

XOR(A[0],...,A[K-1]) = X

Now, if we set A[K] as A[0], then we will have XOR(A[1],...,A[K]) = X

Similarly, if we set A[K+1] as A[1], then we will have XOR(A[2],...,A[K+1]) = X

And continuing so, we can observe that the general formula can be described as below:

A[i] = X, when i%K==0 and 0<=i<=N-1

A[i] = 0, when i%K!=0 and 0<=i<=N-1

  • Time Complexity: O(N), per test case.

  • Space Complexity: O(K), per test case.

Problem Setter's Code
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--)
    {
        ll n,k,_xor;
        cin >> n >> k >> _xor;
        vector<ll> ans(k,0);
        ans[0]=_xor;
        for(int i=0;i<n;++i)
        	cout << ans[i%k] << " ";
        cout << '\n';
    }
    return 0;
}

Problem: Laxman and Maths
Problem Setter: @pallove_227

Logic (Explanation)

We know that:

So, one of the best ways to create the array A of length n, is:

A[i]=i, where 1<=i<=n.

  • Time Complexity: O(n), per test case.

  • Space Complexity: O(1), per test case.

Problem Setter's Code
#include<bits/stdc++.h>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        for(int i=1;i<=n;++i)
        	cout << i << " ";
        cout << '\n';
    }
    return 0;
}

Problem: Hanuman and Tree
Problem Setter: @pallove_227

Logic (Explanation)

Let’s create the two-dimensional array dis[node][deg], which stores the ancestor of node at distance 2deg.

If we fill this dis array, we can answer every query in lg(n) time, using Binary Lifting.

dis[node][0] = parent(node), for every node (except root)

dis[root][0] = -1, for root node.

So, now for deg from 1 to lg(n) and for each node,

dis[node][deg] = dis[dis[node][deg-1]][deg-1].

So, now, for each query node d, convert d into its binary representation and for every set bit in this binary representation, we replace node to dis[node][set-bit position from right], till the value of node doesn’t become -1 or till all the set-bits of d are iterated.

  • Time Complexity: O((n+q)*(lg n))

  • Space Complexity: O(n*(lg n))

Problem Setter's Code
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define endl '\n'
vector<vector<int>> adj;
vector<vector<int>> dis;
void bfs()
{
    queue<int> q;
    q.push(0);
    dis[0][0]=-1;
    while(!q.empty())
    {
        int temp=q.front();
        q.pop();
        for(int u:adj[temp])
        {
            if(u!=dis[temp][0])
            {
                dis[u][0]=temp;
                q.push(u);
            }
        }
    }
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,q;
    cin >> n >> q;
    adj = vector<vector<int>>(n);
    for(int i=0;i<n-1;++i)
    {
        int x,y;
        cin >> x >> y;
        --x;
        --y;
        adj[x].push_back(y);
        adj[y].push_back(x);
    }
    int logn = log2(n) + 1;
    dis = vector<vector<int>>(n,vector<int>(logn+1));
    bfs();
    for(int i=1; i<=logn; ++i)
    {
        for(int node=0; node<n; ++node)
        {
            if(dis[node][i-1]!=-1)
                dis[node][i]=dis[dis[node][i-1]][i-1];
            else
                dis[node][i]=-1;
        }
    }
    vector<int> po(logn+1);
    int temp=1;
    for(int i=0;i<=logn;++i)
    {
        po[i]=temp;
        temp=2*temp;
    }
    while(q--)
    {
        int node,d;
        cin >> node >> d;
        --node;
        for(int i=logn; i>=0; --i)
        {
            if(d>=po[i])
            {
                d-=po[i];
                node=dis[node][i];
            }
            if(node==-1)
                break;
        }
        if(node==-1)
            cout << -1 << endl;
        else
            cout << node+1 << endl;
    }
    return 0;
}

Problem: Bharat and Possibilities
Problem Setter: @pallove_227

Logic (Explanation)

Let DP[i][j] denote the number of possible arrays, where i denotes the Last (Smallest) number in the Array, and j denotes the Size of the Array.

If the size of the array is 1, no matter whatever is the value of i, the following equation will always be true:

DP[i][1] = 1

Observe here that, the last (smallest) element of array of size j will always be less than or equal to last (smallest) element of array of size `j-1 .

Using this observation, we can generalise the DP table as follows:

where 1<=i<=N and 2<=j<=K.

The above equation takes O(N*N*K) time, for calculating the whole DP Table.

So, we will use Suffix Sums, to calculate the DP Table, using the above formula, in O(N*K) time.

  • Time Complexity: O(N*K)

  • Space Complexity: O(N*K)

Problem Setter's Code
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
#define endl '\n'
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int n,k;
    cin >> n >> k;
    vector<vector<int>> dp(n+1,vector<int>(k+1));
    for(int i=1;i<=n;++i)
    {
    	dp[i][1]=1;
    }
    for(int i=n;i>=1;--i)
    {
        for(int j=2;j<=k;++j)
        {
            if(i==n)
                dp[i][j]=dp[i][j-1];
            else
                dp[i][j]=dp[i][j-1]+dp[i+1][j];
            dp[i][j]%=1000000007;
        }
    }
    ll ans=0;
    for(int i=1;i<=n;++i)
    {
        ans+=dp[i][k];
        ans%=1000000007;
    }  
    cout << ans << endl;
    return 0;
}

Problem: Lord Ram and XorOrXorOr Power
Problem Setter: @vok_8

Logic (Explanation)

We will work using the “Binary (Bit) Representation” of all the variables.

Since, we need to find the minimum value of c, so, we will derive some conditions, for a particular bit position to be set (1) or reset (0) in the bit (binary) representation of c.

The conditions (For a particular bit position) are:

  1. The bit position of a xor b is reset (0). (The bit position of a & b is same)
  2. The bit position of d is reset (0).
  3. The bit position of e is reset (0).

When all the above three conditions hold for a particular bit position, only then, that particular bit position of c will be set (1).

Hence, we derived the “Binary Representation” of required value of c, which will give the maximum value of the equation ((((a^b)|c)^d)|e).

So, just convert it into its Integer Representation, and that will be the required minimum value of c, for which the value of the equation ((((a^b)|c)^d)|e), will be maximum.

  • Time Complexity: O(1), per test case.

  • Space Complexity: O(1), per test case.

Problem Setter's Code
#pragma GCC optimize("O3")
#pragma GCC optimize("O1")
#pragma GCC optimize("O2")
#pragma GCC optimize("Os")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);
#define FO cout.tie(NULL);
#define FI cin.tie(NULL);
#define IN cin>>
#define OUT cout<<
#define loop(i,a,n) for(ll i=a; i<n; i++)
#define rloop(i,a,n) for(int i=a; i>=n; i--)
#define endl "\n";
#define pb push_back
#define mp make_pair
#define set_bits(a) __builtin_popcountll(a)
#define ll long long int
#define ld long double
#define vll vector<long long int>
#define pll pair<long long int, long long int>
#define mod 1000000007
#define M 998244353
using namespace std;
void vok()
{
    FAST
    FO
    FI
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
}
int main()
{
    vok();
    int t;
    IN t;
    while(t--)
    {
        ll a,b,d,e;
        IN a>>b>>d>>e;
        ll axb=a^b;
        bitset<60> be(e), ans(0), bd(d), a_xor_b(axb);
        bitset<60> a_xor_b_or_c(0);
        loop(i,0,60)
        {
            if(!be[i] && !bd[i]) //Bit Position of 'e' and 'd' is Reset.
            {
                a_xor_b_or_c[i]=1; //We will want a_xor_b_or_c's Bit Position to be 1.
            } 
        }
        loop(i,0,60)
        {
            if(a_xor_b_or_c[i] && !a_xor_b[i])
            {
                ans[i]=1; //Set the c's bit position to 1
            }
        }
        ll c=ans.to_ulong();
        OUT c<<endl
    }
    return 0;
}

Problem Link: Luv Kush and FX Sequence
Problem Setter: @vok_8

Logic (Explanation)
  • Case-1: (n=0 or n=1)

You can directly find the nth term of the FX Sequence in O(1), using the given values of starting terms of the sequences, MFS and XS.

  • Case-2: (n>=2)

The nth term of the MFS Sequence can be found using Matrix Exponentiation.

We have: MFS(x)= e*MFS(x-1) + f*(MFS(x-2)

In the form of Matrices, it can be written as:

Hence,

So, using Matrix Exponentiation, we will find the (n-1)th Power of the Matrix (which we call, Matrix-B), in O(lg(n-1)) time.

After that, we just have to multiply this Matrix-B with Matrix-C, to get Matrix-A.

At the end, the first term of Matrix-A (A[0][0]) will be the n’th (required) term of the MFS Sequence.

Writing the first 5-7 terms of the XS sequence, in terms of c and d, we get:

c, d, c^d, d^(c^d), d^(c^d)^(c^d), …

which is nothing but,

c, d, c^d, c, d, c^d, …

Hence, we can see that the sequence repeats itself, after every 3 terms.

Thus, the n’th term of this sequence can be found in O(1) time.

  1. When n%3==0, then XS(n) = c
  2. When n%3==1, then XS(n) = d
  3. When n%3==2, then XS(n) = c^d

Now, we found the n’th terms of both the sequences, MFS and XS, so, now, we can find the n’th term of the FX Sequence in O(1) time.

  • Time Complexity: O(lg(n)), per test case.

  • Space Complexity: O(1), per test case.

Problem Setter's Code
#pragma GCC optimize("O3")
#pragma GCC optimize("O1")
#pragma GCC optimize("O2")
#pragma GCC optimize("Os")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);
#define FO cout.tie(NULL);
#define FI cin.tie(NULL);
#define IN cin>>
#define OUT cout<<
#define loop(i,a,n) for(ll i=a; i<n; i++)
#define rloop(i,a,n) for(int i=a; i>=n; i--)
#define endl "\n";
#define pb push_back
#define mp make_pair
#define set_bits(a) __builtin_popcountll(a)
#define ll long long int
#define ld long double
#define vll vector<long long int>
#define pll pair<long long int, long long int>
#define mod 1000000007
#define M 998244353
using namespace std;
void vok()
{
    FAST
    FO
    FI
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
}
ll n,a,b,c,d,e,f;
void multiply(ll m1[2][2], ll m2[2][2]) 
{ 
    ll res[2][2]; 
    loop(i,0,2)
    { 
        loop(j,0,2)
        { 
            res[i][j]=0; 
            loop(k,0,2)
            {
                res[i][j]+=((m1[i][k]%M)*(m2[k][j]%M)); 
                res[i][j]%=M;
            }
        } 
    } 
    loop(i,0,2)
    {
        loop(j,0,2)
        {
            m1[i][j]=res[i][j];
        }
    }
} 
ll power(ll fib[2][2], ll n)
{
    if(n==1)
    {
        return (((b*fib[0][0])%M)+((a*fib[0][1])%M))%M;
    }
    ll mul[2][2]={{e,f},{1,0}};
    power(fib,n/2);
    multiply(fib,fib);
    if(n%2)
    {
        multiply(fib,mul);
    }
    return (((b*fib[0][0])%M)+((a*fib[0][1])%M))%M;
}
ll n_th(ll n)
{
    ll fib[2][2]={{e,f},{1,0}};
    return power(fib,n-1);
}
int main()
{
    vok();
    int t;
    IN t;
    while(t--)
    {
        IN n>>a>>b>>c>>d>>e>>f;
        a%=M;
        b%=M;
        e%=M;
        f%=M;
        if(n==0)
        {
            ll mfs=a;
            ll xs=c%M;
            ll fx=mfs*xs;
            fx%=M;
            fx+=mfs;
            fx%=M;
            fx-=xs;
            fx+=M;
            fx%=M;
            OUT fx<<endl
        }
        else if(n==1)
        {
            ll mfs=b;
            ll xs=d%M;
            ll fx=mfs*xs;
            fx%=M;
            fx+=mfs;
            fx%=M;
            fx-=xs;
            fx+=M;
            fx%=M;
            OUT fx<<endl
        }
        else
        {
            ll xs;
            if(n%3==0)
            {
                xs=c%M;
            }
            else if(n%3==1)
            {
                xs=d%M;
            }
            else
            {
                xs=(c^d)%M;
            }
            ll mfs=n_th(n); //Calculate n'th term of the MFS Seq.
            ll fx=mfs*xs;
            fx%=M;
            fx+=mfs;
            fx%=M;
            fx-=xs;
            fx+=M;
            fx%=M;
            OUT fx<<endl
        }
    }
    return 0;
}

Problem Link: Sita Mata and Time Machine
Problem Setter: @vok_8

Logic (Explanation)

This question is based on Markov Chains. So, for this question, we have to first find the Transition Probability Matrix , from the Given Matrix.

Let’s denote this Transition Probability Matrix as Matrix-P, and the given matrix as Matrix-A, where:

P[i,j] = A[i][j] / Sum(Row-i)

Using Markov Chain’s Finite State Transition Formula, we get that, the probability of going from Time State-i to Time State-j in exactly k steps (state changes) can be defined as: Pk[i][j].

Since we have queries upto 105, and k is also upto 105. So, it is clear that the Brute-Force solution will give TLE.

So, basically, we will get the input of all the queries first, and then sort them in increasing order, with respect to the value of k.

While calculating the powers of the Matrix-P, we will save the answer for all the queries with k = Current Power of the Matrix.

At the end, we can print the saved answer (probability) for each query.

  • Time Complexity: O(max(k)*(n^3) + q)

  • Space Complexity: O(n^2)

Some links, to learn more about Markov Chains:

  1. Markov Chains explained visually
  2. Markov chain - Wikipedia
  3. https://towardsdatascience.com/introduction-to-markov-chains-50da3645a50d
  4. Absorbing Markov Chains | Brilliant Math & Science Wiki
  5. https://math.dartmouth.edu/archive/m20x06/public_html/Lecture14.pdf
Problem Setter's Code
#pragma GCC optimize("O3")
#pragma GCC optimize("O1")
#pragma GCC optimize("O2")
#pragma GCC optimize("Os")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>
#define FAST ios_base::sync_with_stdio(false);
#define FO cout.tie(NULL);
#define FI cin.tie(NULL);
#define IN cin>>
#define OUT cout<<
#define loop(i,a,n) for(ll i=a; i<n; i++)
#define rloop(i,a,n) for(int i=a; i>=n; i--)
#define endl "\n";
#define pb push_back
#define mp make_pair
#define set_bits(a) __builtin_popcountll(a)
#define ll long long int
#define ld long double
#define vll vector<long long int>
#define pll pair<long long int, long long int>
#define mod 1000000007
#define M 998244353
using namespace std;
void vok()
{
    FAST
    FO
    FI
    #ifndef ONLINE_JUDGE
        freopen("input.txt","r",stdin);
        freopen("output.txt","w",stdout);
    #endif
}
bool comp(const array<int,4> &a, const array<int,4> &b)
{
    return a[0]<b[0];
}
int main()
{
    vok();
    int n;
    IN n;
    OUT fixed<<setprecision(8);
    ld a[n][n];
    ld rowsum[n];
    memset(rowsum,0.0,sizeof(rowsum));
    loop(i,0,n)
    {
        loop(j,0,n)
        {
            IN a[i][j];
            rowsum[i]+=a[i][j];
        }
    }
    ld probability_mat[n][n], tprobability_mat[n][n];
    loop(i,0,n)
    {
        loop(j,0,n)
        {
            probability_mat[i][j]=a[i][j]/rowsum[i];
            tprobability_mat[i][j]=a[i][j]/rowsum[i];
        }
    }
    int q;
    IN q;
    vector<array<int,4>> queries(q);
    //queries[i][0] -> k
    //queries[i][1] -> x
    //queries[i][2] -> y
    //queries[i][3] -> index of the query (i)
    int max_power_required=0;
    loop(i,0,q)
    {
        IN queries[i][1]>>queries[i][2]>>queries[i][0];
        queries[i][1]--, queries[i][2]--;
        queries[i][3]=i;
        max_power_required=max(max_power_required,queries[i][0]);
    }
    sort(queries.begin(),queries.end(),comp);
    int curr_power=1;
    int curr_ind=0;
    ld ans[q];
    while(curr_power<=max_power_required && curr_ind<q)
    {
        //Save the answer for queries, having k=curr_power
        while(curr_ind<q && curr_power==queries[curr_ind][0])
        {
            ans[queries[curr_ind][3]]=probability_mat[queries[curr_ind][1]][queries[curr_ind][2]];
            curr_ind++;
        }

        //Calculate P^(curr_power + 1)
        ld temp[n][n];
        loop(i,0,n)
        {
            loop(j,0,n)
            {
                temp[i][j]=0.0;
                loop(k,0,n)
                {
                    temp[i][j]+=(probability_mat[i][k]*tprobability_mat[k][j]);
                }
            }
        }
        loop(i,0,n)
        {
            loop(j,0,n)
            {
                probability_mat[i][j]=temp[i][j];
            }
        }
        curr_power++;
    }

    //Answer all the queries
    loop(i,0,q)
    {
        OUT ans[i]<<endl
    }
    return 0;
}

Congratulations to the Contest Winners!

  1. @uwi
  2. @rahul_g
  3. @nishant403

Please share your valuable Feedback, about the Contest. (Link)

4 Likes

We can also solve Bharat and Possibilities by the concept of non negative integral solution.

For example if k = 10(length of array) and n = 3([1,3] — values can be used in array).
Let c1 = count of 1 in the array,
c2 = count of 2 in the array,
c3 = count of 3 in the array,
then c1 + c2 + c3 = 10

Irrespective of count of 1,2,3, whatever 10 elements we will select, needs no arrangement as only the reversed sorted one will be non-increasing.

So for the solution we need to find non negative integral solutions for c1 + c2 + c3 = 10 => (10+3-1)C(3-1) or (10+3-1)C(10)

In general we will get,
c1 + c2 + … + cn = k => (k+n-1)C(k) or (k+n-1)C(n-1)

Overall enjoyed the contest, kudos to setters :slight_smile:

5 Likes

why this code is giving WA for problem Luv Kush and FX Sequence based on matrix exponentiation.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define nl "\n"
#define ff first
#define ss second
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define pp pop_back
#define bs binary_search
#define pll pair<ll,ll>
#define ppll pair<ll,pll>
#define sll stack<ll>
#define qll queue<ll>
#define vll vector<ll>
#define vpll vector<pll>
#define vc vector <char>
#define matrix vector<vector<ll>>
#define all(x) x.begin(),x.end()
#define loop(i,s,n) for(ll i=s;i<n;i++)
#define test ll t ; cin>>t; while(t--)
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);
ll mod = 1000000007;  double pi = 3.1415926535;

ll K = 2;                //* 1-> CHOOSE K
ll n, a, b, c, d, e, f, MOD = 998244353;

// computes A * B
matrix mul(matrix A, matrix B)
{
	matrix C(K + 1, vector<ll>(K + 1));
	loop(i, 1, K + 1)       loop(j, 1, K + 1)     loop(k, 1, K + 1)     C[i][j] = (C[i][j] + (A[i][k] % MOD) * (B[k][j] % MOD)) % MOD;
	return C;
}

// computes A ^ p
matrix pow(matrix A, ll p)
{
	if (p == 1)     return A;
	if (p % 2)      return mul(A, pow(A, p - 1));
	matrix X = pow(A, p / 2);
	return mul(X, X);
}

// returns the N-th term of recurring sequence
ll mat_expo(ll n)
{
	//* 2-> create vector F1
	ll F1[K + 1];
	F1[1] = b;
	F1[2] = a;

	//* 3-> fill matrix T (TRANSFORMATION MATRIX)
	matrix T(K + 1, vector<ll>(K + 1));
	T[1][1] = e, T[1][2] = f;
	T[2][1] = 1, T[2][2] = 0;

	// raise T to the (N-1)th power
	if (n == 0)     return a;
    if (n == 1)	    return b;
	T = pow(T, n - 1);  

	// the answer is the (first row of T) * F1
	ll res = 0;
	loop(i, 1, K + 1)
	{
		res = (res  + ((T[1][i] * F1[i])%MOD)) % MOD;
	}
	
	return res;
}

void solve()
{
	cin >> n >> a >> b >> c >> d >> e >> f;
	a %= MOD;	b %= MOD;	c %= MOD;	d %= MOD;	e %= MOD;	f %= MOD;
	
	ll mfs = mat_expo(n), xs;
	
	if (n % 3 == 0)		xs = c;
	else if (n % 3 == 1)		xs = d;
	else		xs = (c ^ d) % MOD;
	
	ll ans = ((mfs * xs) % MOD) + (((mfs-xs)%MOD+MOD)%MOD) ;
	cout << ans%MOD << nl;
}

int main() {
	fast_io;
#ifndef ONLINE_JUDGE
	freopen("input1.txt", "r", stdin);
	freopen("output1.txt", "w", stdout);
#endif

	test{
		solve();
	}
	return 0;
}

IT WILL BE REALLY HELPFUL IF SOMEONE CAN HELP
:pray:

Hey, try to use a “2D Array”, instead of “Vector”. Because, the accessing and updating is faster in “2D Array”, as compared to “Vector”, when large number of operations are to be performed.

1 Like

Yes I used array instaed of vector but now it gave WA with runtime of 0.95 sec.
It will be very kind of you if you can tell what may be the reason for this WA now. :pray: :pray:
Thnx for reply

It will give WA as you can’t take MOD of c and d, before doing c^d, because after you take MOD of c and d, you will different (wrong) value of c^d. So, better MOD c and d, in the 3 conditions as follows (and not before that):

if (n % 3 == 0)		xs = c % MOD;
else if (n % 3 == 1)		xs = d % MOD;;
else		xs = (c ^ d) % MOD;
1 Like

thnx for the help.I totally missed it.
thnx :pray: :pray:

1 Like