You are not logged in. Please login at www.codechef.com to post your questions!

×

# SWEGIRL - Editorial

Authors: Piyush Mehrotra
Testers: Vaibhav Daga
Editorialist: Piyush Mehrotra

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.

# AUTHOR'S SOLUTION:

This question is marked "community wiki".

asked 16 Mar '16, 14:12

6★hm_98
2806
accept rate: 0%

19.8k350498541

 toggle preview community wiki:
Preview

### Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,683
×2,596
×1,755
×81
×32
×26
×25
×6

question asked: 16 Mar '16, 14:12

question was seen: 1,124 times

last updated: 17 Mar '16, 15:33