Contest Link: Learning Sprint-1 (Advanced Track)
Problem: Get Function Value
Problem Setter: @vok_8
Hint-1
- XOR of 2 bits is
1, when one of them is unset. - XNOR of 2 bits is
1, when both of them are equal (set or unset).
Hint-2
Special Value (Sub-Array [l,l+1]) = 2^(int(log2(max(a[l],a[l+1]))) + 1) - 1
The reason for above deduction is that, from the max(set MSB(a[l]), set MSB(a[l+1])) to LSB, all bits will become 1.
Note: [0,1] & [1,0] bit pairs will get set because of XOR operation and [1,1] & [0,0] bit pairs will get set because of XNOR operation.
Hint-3
Special Value (Sub-Array [l,r]) = 2^(int(log2(max(a[l],...,a[r]))) + 1) - 1
Hint-4
Think of finding maximum value in a sub-array efficiently, for multiple queries.
Hint: Use of Segment Tree or Sparse Table (since there are no update queries), to find maximum value in a sub-array.
Tutorial
Special Value (Sub-Array [l,r]) = 2^(int(log2(max(a[l],...,a[r]))) + 1) - 1
Use Segment Tree to find maximum value in the queried sub-array efficiently.
You can also use Sparse Table, instead of Segment Tree, since there are no updates in the array.
Check out hints, for more detailed description/explanation.
-
Time Complexity:
O((n+q)*log(n)) -
Space Complexity:
O(n)
Problem Setter's Code (C++)
#include <bits/stdc++.h>
using namespace std;
const int mxN=int(1e5)+100;
int treee[mxN*4];
int arr[mxN];
int build(int sl, int sr, int ind) //Build the Segment Tree for Max. Value in a Subarray
{
if(sl==sr)
{
treee[ind]=arr[sl];
return treee[ind];
}
int mid=(sl+sr)/2;
treee[ind]=max(build(sl,mid,ind*2+1),build(mid+1,sr,ind*2+2));
return treee[ind];
}
int query(int l, int r, int sl, int sr, int ind) //Query for Max. Value in Subarray [l,r] using Segment Tree
{
if(l<=sl && r>=sr)
{
return treee[ind];
}
if(sr<l || sl>r)
{
return -1;
}
int mid=(sl+sr)/2;
return max(query(l,r,sl,mid,ind*2+1),query(l,r,mid+1,sr,ind*2+2));
}
int main()
{
int n;
cin>>n;
for(int i=0; i<n; i++)
{
cin>>arr[i];
}
build(0,n-1,0); //build the segment tree
int q;
cin>>q;
while(q--)
{
int l,r;
cin>>l>>r;
int max_value=query(l,r,0,n-1,0); //get max. value in the subarray [l,r] using built Segment Tree
int ans=pow(2,int(log2(max_value))+1)-1; //get the ans.
cout<<ans<<"\n";
}
return 0;
}
Problem: Check Repeat
Problem Setter: @vok_8
Hint-1
For an element to have frequency 1 in the given array, the previous occurrence of this element in the array has to be strictly less than l and next occurrence of the element has be to strictly greater than r, for a particular query.
Hint-2
Think of using Merge Sort Tree, for doing what is described in Hint-1.
Tutorial
Key Note: For an element to have frequency 1 in the given array, the previous occurrence of this element in the array has to be strictly less than l and next occurrence of the element has be to strictly greater than r, for a particular query.
- Store the previous occurrence and next occurrence of every i’th element in the array as a pair.
- Build the merge sort tree and merge nodes in them according to the previous occurrence, of the element.
- At each node of merge sort tree, maintain prefix maximum on the next occurrence because we need as smallest possible previous occurrence and as big next occurrence of some element.
- For answering the query, we need node with previous occurrence strictly less than
l. - For the element in the merge sort tree with the previous occurrence less than
l, find the maximum next occurrence and check if next occurrence is greater thanr, for the current query, then there is an element present in the subarray with frequency 1.
-
Time Complexity:
O((n+(q*log(n))*log(n)) -
Space Complexity:
O(n)
Problem Setter's Code (C++)
#include <bits/stdc++.h>
using namespace std;
const int mxN=int(1e5)+100;
vector<pair<int,int>> treee[4*mxN]; //Merge Sort Tree
vector<pair<int,int>> occurrences(mxN); //To store occurrences
vector<set<int>> pos(mxN); //To store indexes of all elements
int n;
void build(int node=0, int l=0, int r=n-1) //Build the Merge Sort Tree
{
if(l==r)
{
treee[node].push_back(occurrences[l]);
return;
}
int mid=(l+r)/2;
build(2*node+1,l,mid);
build(2*node+2,mid+1,r);
//Merge Left and Right Child Nodes
merge(treee[2*node+1].begin(),treee[2*node+1].end(),treee[2*node+2].begin(),treee[2*node+2].end(),back_inserter(treee[node]));
int maxi=0;
for(auto &occ:treee[node])
{
maxi=max(maxi,occ.second); //Update maximum next occurrence
occ.second=maxi; //Update the next occurrence with max. of all next occurrences of elements
}
}
bool query(int x, int y, int node=0, int l=0, int r=n-1) //Function to query for subarray [x,y]
{
if(l>y || r<x || x>y) //out of range
{
return false;
}
if(x<=l && r<=y) //fully in range
{
//Find the first node with previous occurrence >=x
auto it=lower_bound(treee[node].begin(),treee[node].end(),make_pair(x,-1));
//No element in this range with previous occurrence less than 'x'
if(it==treee[node].begin())
{
return false;
}
else //there is an element with previous occurrence less than 'x'
{
it--;
if((*it).second<=y) //check if max. next occurrence is less than or equal to 'y' or not
{
return false;
}
return true;
}
}
int mid=(l+r)/2;
return (query(x,y,2*node+1,l,mid) | query(x,y,2*node+2,mid+1,r)); //query for left and right children
}
void preprocess(int arr[]) //Pre-process the Array
{
for(int i=0; i<n; i++)
{
pos[arr[i]].insert(i);
}
for(int i=0; i<n; i++)
{
//Find the previous and next occurrences
auto it=pos[arr[i]].find(i);
if(it==pos[arr[i]].begin()) //If there is no previous occurrence
{
occurrences[i].first=INT_MIN;
}
else
{
occurrences[i].first=*prev(it);
}
if(next(it)==pos[arr[i]].end()) //If there is no next occurrence
{
occurrences[i].second=INT_MAX;
}
else
{
occurrences[i].second=*next(it);
}
}
}
int main()
{
cin>>n;
int arr[n];
for(int i=0; i<n; i++) //input the array
{
cin>>arr[i];
}
int q;
cin>>q;
preprocess(arr); //Pre-process the array and the occurrences of array elements
build(); //Build the Merge-Sort Tree
while(q--) //process and answer the queries
{
int l,r;
cin>>l>>r;
l--, r--; //Convert l & r to 0-indexing
if(query(l,r)) //If the subarray [l,r] has an element with exactly 1 occurrence
{
cout<<"Yes"<<"\n";
}
else
{
cout<<"No"<<"\n";
}
}
}
Problem: Modified Jenga
Problem Setter: @vok_8
Hint-1
Think of using Fenwick Tree or Segment Tree.
Hint-2
Suppose n=5 and q=2.
Make an integer array of (n+q) size and initialise first q integers as 0 and next n integers as 1.
Empty q spaces are provided at the start of the array, to be used for the q moves, to be made.
Also, maintain current indices of all n blocks.
curr_indices = [3,4,5,6,7] (1-indexing)
array = [0,0,1,1,1,1,1]
Suppose, in the 1st query, x=3.
So, move block with value=3 from it’s current position to position-q.
So,
ans (blocks above x=3) = prefix_sum till curr_indices[q+3] - 1 = 2
curr_indices = [3,4,2,6,7] (1-indexing)
array = [0,1,1,1,0,1,1]
Suppose, in the 2nd query, x=2.
So, move block with value=2 from it’s current position to position-q-1.
So,
ans (blocks above x=2) = prefix_sum till curr_indices[q+2] - 1 = 2
curr_indices = [3,1,2,6,7] (1-indexing)
array = [1,1,1,0,0,1,1]
Tutorial
Make a Fenwick Tree of size n+q+1 (for 1-indexing).
Currently, fill the Fenwick Tree with first q+1 positions being 0 and last n positions being 1.
Also, maintain current index of every block in Fenwick Tree Array, using a map/vector/array. (At the starting of the game, the index of the i'th block in Fenwick Tree Array will be i+q).
For each query,
- The answer will be
prefix_sum(0,current_index[x])-1. - Move the block
xfrom its current index/position to positionq-(queries answered), and update its current position toq-(queries answered).
The above calculations and results are according to 1-indexing.
-
Time Complexity:
O((n+q) * log(n+q)) -
Space Complexity:
O(n+q)
Problem Setter's Code (C++)
#include <bits/stdc++.h>
using namespace std;
struct FenwickTree
{
vector<int> bit; //binary indexed tree
int n;
FenwickTree(int n)
{
this->n=n;
bit.assign(n,0);
}
int sum(int r)
{
int ret=0;
for(; r>=0; r=(r&(r+1))-1)
{
ret+=bit[r];
}
return ret;
}
void add(int idx, int delta)
{
for(; idx<n; idx=idx|(idx+1))
{
bit[idx]+=delta;
}
}
};
int main()
{
int n,q;
cin>>n>>q;
FenwickTree f(n+q+10); //create a Fenwick Tree
vector<int> curr_ind(n+1,-1); //array/vector to store current position of 'i'th block in Fenwick Tree Array
for(int i=1; i<=n; i++)
{
f.add(i+q,1);
curr_ind[i]=i+q; //give empty space in the front of fenwick tree array of 'q' queries, for 'q' moves
}
int curr_top=q; //using right-most empty space
while(q--)
{
int x;
cin>>x;
int ans=f.sum(curr_ind[x])-1; //since f.sum(curr_ind(x)) will give the blocks above x'th block, including itself, so we will subtract 1
cout<<ans<<" ";
f.add(curr_ind[x],-1); //remove from current position
curr_ind[x]=curr_top; //update curr_ind[x]
f.add(curr_ind[x],1); //move it to curr_top
curr_top--; //decrement curr_top (used this space -> move to left)
}
cout<<"\n";
return 0;
}
Feel free to ask your queries/doubts and share your ideas in the comment section.