STQRS - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Chef Dynasty

Author and Editorialist: Krish Rustagi
Testers: Prakhar Kochar, Aditi Sahu

DIFFICULTY:

MEDIUM

PREREQUISITES:

Data Structures, Implementation

PROBLEM:

Perform 3 types of queries on a string s of length of N.

  • Type 1: replace the character at position x with a given character c in the original string.

  • Type 2: compare the string in the range [l_1, r_1] (l_1 and r_1 included) with the string in the range [l_2, r_2] (l_2 and r_2 included) (l_1 ≤ r_1 < l_2 ≤ r_2), lexicographically.
    1. If they are equal, print 0.
    2. If the string in the first range is lexicographically smaller than the second range print -1.
    3. Otherwise print 1.
    Now if the two strings are not equal, then do the changes as per the following:

    • If the length of the first range is greater than the length of the second range, replace the contents of the first range with the content of the second range.
    • If the length of the second range is greater than the length of the first range, replace the contents of the second range with the content of the first range.
    • If the lengths are equal, then swap the contents of the two ranges.

  • Type 3: a number l is provided:

    • If l is strictly greater than the half of the size of the string, l > \frac {|s|} {2}, then print “DEL” (without quotes) and remove all the characters till the end starting from position l (including l^{th} character).
    • Otherwise, print “INS” (without quotes) and add the first l characters of the string to the end of the string (including l^{th} character).

After all the operations print the final string.

EXPLANATION:

The Naïve solution is to use string for all the tasks. But this will give TLE.

So, the efficient solution is to use Rope data Structure instead of string. Rope (data structure) are a scalable string implementation: they are designed for efficient operation that involve the string as a whole.

A rope is a binary tree where each leaf (end node) holds a string and a length (also known as a “weight”), and each node further up the tree holds the sum of the lengths of all the leaves in its left subtree. A node with two children thus divides the whole string into two parts: the left subtree stores the first part of the string, the right subtree stores the second part of the string, and a node’s weight is the length of the first part.

For rope operations, the strings stored in nodes are assumed to be constant immutable objects in the typical nondestructive case, allowing for some copy-on-write behavior. Leaf nodes are usually implemented as with a reference count attached for deallocation when no longer needed, although other garbage collection methods can be used as well.

C++ language includes rope header file with the name “rope.h”.

Let’s declare a rope with the name v.

rope<char> v; // crope: crope is rope<char>

For task 1:
for ropes there is a replace() function which is similar to s[x] = c, where s is a string. But this function takes O(log n) time complexity while in string it takes O(1) to do so.

v.replace(x, c); // where x is the position and c is the character

For task 2:
We will compare two the two sub-ropes lying between [l_1, r_1] and [l_2, r_2].
“substr” function in ropes takes O(log n) time complexity which is better than that of strings which has O(n) time complexity for slicing.
But for comparison of ropes it takes O(n) time complexity to compare the subropes. That’s why it was mentioned that “it will take not more than 1000 comparable characters”

crope c1 = v.substr(l1, r1 - l1 + 1); // crope 1 -> [l1, r1]
crope c2 = v.substr(l2, r2 - l2 + 1); // crope 2 -> [l2, r2]

// comparing two ropes
int p = c1.compare(c2); // same as string comparison
if(p != 0)
{
	p /= abs(p);
}

Now if the two strings are not equal, then

// comparing the sizes of the two different subropes
if(r1 - l1 < r2 - l2)
{
	crope x1 = v.substr(1, l2);
	crope x2 = v.substr(r2, v.size() - r2+1);
	v = x1 + c1 + x2; // concatenation takes O(log n) or O(1) time complexity
}
// similar for r1 - l1 > r2 - l2
else if(r1 - l1 > r2 - l2)
{ .... } 
else
{
	crope x1 = v.substr(1, l1);
	crope x2 = v.substr(r1, v.size() - r1 + 1);
	v = x1 + c2 + x2;
	x1 = v.substr(1, l2);
	x2 = v.substr(r2 + 1, v.size() - r2 + 1);
	v = x1 + c1 + x2;
}

For task 3:
here we will use erase() function to erase from the ropes. In ropes it takes O(log n) time while in strings it takes O(n) time. For inserting at the end, we will simply concatenate with the substring.

if(l > v.size() / 2)
{
	v.erase(l, v.size()-l); // erasing the last l character from the rope
}
else
{
	crope x = v.substr(1, l);
	v.append(x); // appending with the first l characters of the rope
}

TIME COMPLEXITY:

O(Q*(log N))

SOLUTIONS:

Solution 
/*
    Author: mr_cruise/krishrustagi
    
    Rules:
    1. Check for the corner cases.
*/
#include <bits/stdc++.h> 
#include<ext/rope>
using namespace std;
using namespace __gnu_cxx;
 
void solve()
{
	int n, q;
	cin >> n >> q;
	crope rop;
	for (int i = 0; i < n; ++i)
	{
		char c;
	 	cin >> c;
	 	rop.push_back(c);
	}
	for (int i = 0; i < q; ++i)
	{
		int type;
		cin >> type;
		if (type == 1)
		{
			int x;
			char c;
			cin >> x >> c;
			rop.replace(x-1, c); // s[x - 1] = c; O(log n)
		}
		else if (type == 2)
		{
			int l1, r1, l2, r2;
			cin >> l1 >> r1;
			cin >> l2 >> r2;
			l1--;r1--;l2--;r2--;
			crope rop1 = rop.substr(l1, r1-l1+1);
			crope rop2 = rop.substr(l2, r2-l2+1);


            int p = rop1.compare(rop2);
			if(p != 0)
            {
                p/=abs(p);
            }
            cout << p << endl;
			
            if(p == 0)
                continue;
 
			// If the two subropes are not equal
			if(rop1.size() > rop2.size())
			{
				rop = rop.substr(0, l1)+rop2+rop.substr(r1+1, rop.size()-r1); // O(1)
			}
			else if(rop1.size() < rop2.size())
			{
				rop = rop.substr(0, l2)+rop1+rop.substr(r2+1, rop.size()-r2);
			}
			else
			{
				rop = rop.substr(0, l1)+rop2+rop.substr(r1+1, rop.size()-r1);
				rop = rop.substr(0, l2)+rop1+rop.substr(r2+1, rop.size()-r2);
			}
		}
		else
		{
			int l;
			cin >> l;
			
			if(rop.size()/2.0 < l)
			{
				l--;
				cout << "DEL" << endl;
				rop.erase(rop.mutable_begin()+l, rop.mutable_end()); // erasing takes O(log n) time in ropes
			}
			else
			{
				l--;
				cout << "INS" << endl;
				rop = rop.append(rop.substr(0, l+1)); // rop += rop.substr(0, l+1);
			}
		}
	}
	cout << rop << endl;
}

int main()
{
    ios_base::sync_with_stdio(false); 
    cin.tie(NULL); 
    cout.tie(NULL);
 
    int t = 1;
    // cin >> t;
    for (int i = 0; i < t; ++i)
    {
    	solve();
    }
    return 0;
}

Feel free to share your approach! Suggestions are welcomed!!
Thanks.:slightly_smiling_face:

5 Likes