PROBLEM LINK:
Authors: Piyush Mehrotra
Testers: Vaibhav Daga
Editorialist: Piyush Mehrotra
DIFFICULTY:
Medium
PREREQUISITES:
Basic know of Queue Data-Structure, Sweg
PROBLEM:
There is a string of length L consisting of 2 kinds of characters, namely X and O on which we perform update operation of 2 types on sub-string[l,r]. Either we change all the characters of the sub-string to X or O.
After the update operations, we have to output the minimum number of toggles required in order to transform the string such that all the X if they occur, occur in the beginning .
EXPLANATION:
First, I will explain the second part of the problem, that is, to output the minimum number of toggles to transform the string(Assuming that all the updates are done). I will explain how to do the updates in the latter part of the explanation.
We have to transform the string in such a way such that all the X if they occur, occur in the beginning.
Lets take some ‘i’ in [0,L] (L denotes the length of string). Suppose that till ‘i’th index all the characters preceding it are X. So the number of toggles to transform the string will be sum of the number of O appearing at index j in [1,i] and number of X appearing at index j in [i+1,L]. We have to calculate the minimum of the sum for all i in [0,L].
This can be implemented in O(L) as follows
sum_O = 0;// number of ‘O’ before i
sum_X = 0;// number of ‘X’ after i
for(int i = 1; i<=len; i++)
{
if(GirlFriends[i]==‘X’)
sum_X++;
}
ans = sum_X;// for i = 0
for(int i = 1; i<=len; i++)
{
if(GirlFriends[i]==‘O’) sum_O++;
if(GirlFriends[i]==‘X’) sum_X—;
ans = min(ans, sum_X + sum_O);
}
printf("%d\n", ans);
Now coming to the update part of the question, it can be easily be seen that for some ‘i’th element, if it comes in many a, l, r updates, then only the last update operation decides the final value of the element. So if we are able to get the highest index of the update query for every ‘i’th element, then we can easily find the final string.
We can do that using segment-tree with lazy propagation or using priority-queue in O(L*log(k)). We can also do this using queue and apply binary-search on it. Here, I will explain the solution with priority-queue so that even those who don’t know segment-tree can understand it.
We will store all the queries and their indices of type 1 and 2 separately(I have done that using vector array).
const int SIZE = 100005;
vector<int> type_1[SIZE][2];
vector<int> type_2[SIZE][2];
for(int i = 1; i<=k; i++)
{
scanf("%d%d%d", &type , &l , &r );
if(type==1)
{
type_1[l][0].push_back(i);
type_1[r+1][1].push_back(i);
}
else if(type==2)
{
type_2[l][0].push_back(i);
type_2[r+1][1].push_back(i);
}
}
Then we traverse this array and push the indices of the queries in the priority-queue for which ‘i’ belongs to [l,r] and pop those indices for which i>r or i<l. I have done that by maintaining a boolean array (initially all true) as to mark all those indices ‘false’ whose ‘r’ is less than the present index i that we are on. The priority-queue will sort the elements in it as we push the indices in the queue. The top element gives the highest index of the query of that type that covers that element. We will store all the highest index in an array(initially all elements are zero). Thus we can get the maximum index of the update due to change has taken place for all i in [1,L].
The following code is for type-1 query.
priority_queue <int> q;
int final_type1[SIZE];
// this array is storing the highest index of update query for every ‘i’
//initialise all the elements by zero
bool check_type1[SIZE];// initially all true
for(int i = 1; i<=L; i++)
{
for(int j = 0; j<type_1[i][1].size(); j++)
{
check_type1[type_1[i][1][j]] = false;
}
for(int j = 0; j<type_1[i][0].size(); j++)
{
q.push(type_1[i][0][j]);
}
if(!q.empty())
{
while(!q.empty() && !check_type1[q.top()])
{
q.pop();
}
if(!q.empty())
{
final_type1[i] = q.top();
}
}
}
Similarly we can do that for both the type of updates. Finally we can update our string in linear time O(L) just by traversing the string and changing it to
X-> highest index of ith element for type-1 queries > highest index of ith element for type-2 queries
i.e. If final_type1[i]>final_type2[i] then ‘i’th element of string is X
O-> highest index of ith element for type-2 queries > highest index of ith element for type-1 queries
i.e. If final_type1[i]<final_type2[i] then ‘i’th element of string is O
Remains same-> If both of the ith elements for type-1 queries and type-2 queries are zero
for(int i = 1; i<=L; i++)
{
if(final_type1[i]>final_type2[i])
{
GirlFriends[i] = X;
}
else if(final_type1[i]<final_type2[i])
{
GirlFriends[i] = O;
}
}
After the updates, we can find the minimum number of toggles as explained initially.
Time Complexity:
O(L + L*log(k))
My priority-queue solution takes more space but is faster than my segment-tree solution.