Problem Link : CodeChef: Practical coding for everyone
Difficulty : Hard
Problem : Queries to find the length of the shortest contiguous subarray in which all elements from 1 to K are present.
Explanation :
We will make a tree in such a way
findMinSubArr(L) :
Left : Left Half of the array L
Right : Right Half of the array L
A : findMinSubArr(Left)
B : findMinSubArr(Right)
C : minimum length of the subarray that contains all the numbers from 1 to K, made up of suffix of Left and prefix of R
return min( A, B, C)
Now, the main algo left to calculate the value of C in best time complexity.
First we will need to understand these things:
-
As the value of K <= 50 so we can represent each number as a bitmask.
(You can also make a hash array, but it will cost a lot of memory space) -
By bit masking we can easily check if a sequence_1 is a subset of sequence_2.
Example : let seq_1 = [1, 3],
We can represent every element of seq_1 by bit masking i.e. 1<<(element)
seq_1 = [(1) << (1) , 1 << 3]
Similarly seq_2 = [1,4,2,3] = [1 << 1, 1 << 4, 1 << 2, 1 << 3]
Taking OR of every element of seq, we get
OR1 (in binary) = 01010
OR2 (in binary) = 11110
if( OR1 & OR2 == OR1 ) then seq_1 is a subset of seq_2 -
If the OR of the sequence == 2^K - 1, then we have found all the elements from 1 to K.
For each node of the tree, we will calculate the suffix of Left and prefix of Right in the form of bit masks. Now checking for which minimum length, the OR of the bitmask is 2^K -1.
Example :
Array = [1,2,3,1]
Left = [1,2] = {0110, 0100} // making the suffix array i.e each element stores the elements that come to the right of it. 0110 → 1 and 2 are visited
Right = [3, 1] = {0110, 0110} // making the prefix array i.e. each element of this array store the presence of the element to the left.
Now in process of making the tree is of time complexity : (K^2)Nlog(N):
For each suffix in left ( m ) we will check the the nearest prefix ( n ) to get the shortest length of the subarray, such that (m OR n) == (2^K - 1), which shows that all the elements from 1 to K are present in that subarray.
So the time complexity of building such a tree is (K^2)Nlog(N).
With some tricks this complexity can even be reduced to KNlog(N).
Now, have to process M queries
We will construct a Heap Tree where each node store the sets of bit masks for prefixes and suffixes of its interval and the length of the shortest subarray containing all the elements from 1 to K. Each query takes O(1) time.
Code :
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define INF 1000000000
#define MAXN 262144
#define offset 131072
// described in the description
inline bool subset(ll mask1, ll mask2)
{
return (mask1 & mask2) == mask1;
}
ll n, k, q;
class Heap
{
private:
struct node
{
ll len;
// make two arrays that store the suffix and prefix of the node
// max array length is K = 50
pair<ll, ll> pref[50];
pair<ll, ll> suff[50];
// stores the length of the minimum subarray containing all the elem
// from 1 to K
ll ans;
// blank node
node()
{
ans = INF;
len = 0;
}
node(int t, int v)
{
len = 1;
// bit masking the value
// very important part
pref[0] = suff[0] = pair<ll, ll>(1LL << v, t);
ans = INF;
}
};
node tree[MAXN];
// merging of the left and right into the main tree
void merge(node &t, node &l, node &r)
{
ll pref_len, suff_len;
pref_len = 0;
// the first part maintain the prefix array
// maximum length of any segment can be 50 , as we are not pushing any value
// if it is the subset of already made value
for (int i = 0; i < l.len; ++i)
t.pref[pref_len++] = l.pref[i];
for (int i = 0; i < r.len; ++i){
// if the right part is the subset of the prefix till now
// then no need to inclde
// by this way , the size of array in any node doex not exceed 50
if (pref_len == 0 || !subset(r.pref[i].first, t.pref[pref_len - 1].first))
{
t.pref[pref_len] = r.pref[i];
if (pref_len > 0)
t.pref[pref_len].first |= t.pref[pref_len - 1].first;
++pref_len;
}
}
suff_len = 0;
// same is the process of making the suffix array
for (int i = 0; i < r.len; ++i)
t.suff[suff_len++] = r.suff[i];
for (int i = 0; i < l.len; ++i)
if (suff_len == 0 || !subset(l.suff[i].first, t.suff[suff_len - 1].first))
{
t.suff[suff_len] = l.suff[i];
if (suff_len > 0)
t.suff[suff_len].first |= t.suff[suff_len - 1].first;
++suff_len;
}
t.len = pref_len;
t.ans = INF;
ll pref_pos = 0;
// now the part that is k^2
// which we can reduced to K
// in this part we are checking
// the minimum length of the subarray which contain all the elem
// from 1 to K
for (int suff_pos = l.len - 1; suff_pos >= 0; --suff_pos)
{
while (pref_pos < r.len && (l.suff[suff_pos].first | r.pref[pref_pos].first) != (1LL << k) - 1)
++pref_pos;
if (pref_pos < r.len)
{
ll curr_mask = l.suff[suff_pos].first | r.pref[pref_pos].first;
// if current mask = 2^k - 1 , then it means
// all the elements from 1 to K are founded
if (curr_mask == (1LL << k) - 1)
t.ans = min(t.ans, r.pref[pref_pos].second - l.suff[suff_pos].second + 1);
}
}
// calculating the minimum ans for the node
t.ans = min(t.ans, min(l.ans, r.ans));
}
public:
// base constructor
Heap() {}
// update function
// this is used for updating the left tree and right tree
// and then merging them to the main tree
// movement is : bottom to top
void update(ll t, ll v)
{
// as the movement is from bottom to top
// so we make a offset that describe the position relative to the tree
// let total nodes are 100
// and length of the array is 10
// then offset would be 90, because we are moving from bottom to top
ll index = t + offset;
// making the node in the tree
tree[index] = node(t, v);
// merging the left and the right tree into the parent node
for (index /= 2; index > 0; index /= 2){
merge(tree[index], tree[2 * index], tree[2 * index + 1]);
}
}
// the top of the tree will contain the length of the min sub array
// just like min or max heaps
ll query(void)
{
return tree[1].ans;
}
};
// making a Heap tree
Heap T;
int main(void)
{
cin >> n >> k >> q;
for(int i = 0; i < n; i++){
ll v;
cin >> v;
// updating or inserting the values in the tree
T.update(i, v - 1);
}
while(q--)
{
ll type;
cin >> type;
if (type == 1)
{
ll x, v;
cin >> x >> v;
T.update(x - 1, v - 1);
}
else
{
ll ans = T.query();
if( ans == INF){
cout << -1 << endl;
}else{
cout << ans << endl;
}
}
}
return 0;
}