- Contest Link: 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:
- The bit position of
a xor bisreset (0). (The bit position ofa&bis same) - The bit position of
disreset (0). - The bit position of
eisreset (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.
- When
n%3==0, thenXS(n) = c - When
n%3==1, thenXS(n) = d - When
n%3==2, thenXS(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:
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!
Please share your valuable Feedback, about the Contest. (Link)
