 # 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,...,A[K-1]) = X`

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

Similarly, if we set A[K+1] as A, then we will have `XOR(A,...,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=_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 `2``deg`.

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

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

`dis[root] = -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>> dis;
void bfs()
{
queue<int> q;
q.push(0);
dis=-1;
while(!q.empty())
{
int temp=q.front();
q.pop();
{
if(u!=dis[temp])
{
dis[u]=temp;
q.push(u);
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n,q;
cin >> n >> q;
for(int i=0;i<n-1;++i)
{
int x,y;
cin >> x >> y;
--x;
--y;
}
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`

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;
}
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`) 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, ll m2)
{
ll res;
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, ll n)
{
if(n==1)
{
return (((b*fib)%M)+((a*fib)%M))%M;
}
ll mul={{e,f},{1,0}};
power(fib,n/2);
multiply(fib,fib);
if(n%2)
{
multiply(fib,mul);
}
return (((b*fib)%M)+((a*fib)%M))%M;
}
ll n_th(ll n)
{
ll fib={{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: `P``k``[i][j]`.

Since we have queries upto `10``5`, and `k` is also upto `10``5`. 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)`

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<b;
}
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] -> k
//queries[i] -> x
//queries[i] -> y
//queries[i] -> index of the query (i)
int max_power_required=0;
loop(i,0,q)
{
IN queries[i]>>queries[i]>>queries[i];
queries[i]--, queries[i]--;
queries[i]=i;
max_power_required=max(max_power_required,queries[i]);
}
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])
{
ans[queries[curr_ind]]=probability_mat[queries[curr_ind]][queries[curr_ind]];
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++;
}

loop(i,0,q)
{
OUT ans[i]<<endl
}
return 0;
}
``````

Congratulations to the Contest Winners!

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 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 = b;
F1 = a;

//* 3-> fill matrix T (TRANSFORMATION MATRIX)
matrix T(K + 1, vector<ll>(K + 1));
T = e, T = f;
T = 1, T = 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[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 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.  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;
thnx  