PAWRI - EDITORIAL

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3

Author: Daanish Mahajan
Tester: Rahul Dugar
Editorialist: Nandini Kapoor

DIFFICULTY:

Cakewalk

PREREQUISITES:

Brute force, Strings

PROBLEM:

Lately, Chef has been inspired by the pawri meme. Therefore, he decided to take a string S and change each of its substrings that spell party to pawri. Find the resulting string.

QUICK EXPLANATION:

We will traverse the given string and at any instant we find the word party we shall replace it with pawri.

EXPLANATION:

We need to replace all the occurrences spelling party with pawri. To achieve this we will run a loop from the beginning of the string to 4 less than its end and at every index check for the presence of the substring party starting from that index. In other words, for every i such that 0\leq i\lt S.size()-4, we check whether S[i:i+4] spells party and if it does, we change S[i:i+4] to pawri instead. We needn’t go beyond 4 less than the length of the string because any substring starting at indices beyond that would have length less than 5 (which is the desired length to match with party). Also note that once we have found a substring matching party say from index i to i+4, we can skip checking substrings starting from i+1 to i+4 because no suffix of party is also its prefix, and thus none of the substrings starting from any of those characters would turn out to be party.

The substring S[i:i+4], on arriving at subsequent indices can be obtained (for matching) as well as replaced using functions defined by respective languages that serve the purpose (for example S.substr(i, length) in C++ for returning substring starting at index i of specified length and S.replace(i, length, Sr) for replacing it with the string S{r}). In this particular case, as the substring is small in length, individual characters can be matched and replaced easily from i to i+4 without the aid of such functions as well.

Another way to approach the problem could utilize KMP algorithm for pattern searching. But it would not significantly affect the time complexity, as no two consecutive windows will both be prefixes to the pattern. This happens because our pattern “party” consists of all different characters.

TIME COMPLEXITY:

O(N) per test case.
N being the length of the string given, T(N)=(N-4)\times 5.
Note that std::string::substr as documented has its complexity unspecified, but generally linear in the length of the returned object, which in this case is 5.

SOLUTIONS:

Setter
Tester
    #pragma GCC optimize("Ofast")
    #include <bits/stdc++.h>
    using namespace std;
    #include <ext/pb_ds/assoc_container.hpp>
    #include <ext/pb_ds/tree_policy.hpp>
    #include <ext/rope>
    using namespace __gnu_pbds;
    using namespace __gnu_cxx;
    #ifndef rd
    #define trace(...)
    #define endl '\n'
    #endif
    #define pb push_back
    #define fi first
    #define se second
    #define int long long
    typedef long long ll;
    typedef long double f80;
    typedef pair<int,int> pii;
    typedef pair<double,double> pdd;
    //#define double long double
    #define pll pair<ll,ll>
    #define sz(x) ((long long)x.size())
    #define fr(a,b,c) for(int a=b; a<=c; a++)
    #define rep(a,b,c) for(int a=b; a<c; a++)
    #define trav(a,x) for(auto &a:x)
    #define all(con) con.begin(),con.end()
    const int infi=0x3f3f3f3f;
    const ll infl=0x3f3f3f3f3f3f3f3fLL;
    //const int mod=998244353;
    const int mod=1000000007;
    typedef vector<int> vi;
    typedef vector<ll> vl;
   
    typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
    auto clk=clock();
    mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
    int rng(int lim) {
        uniform_int_distribution<int> uid(0,lim-1);
        return uid(rang);
    }
    int powm(int a, int b) {
        int res=1;
        while(b) {
            if(b&1)
                res=(res*a)%mod;
            a=(a*a)%mod;
            b>>=1;
        }
        return res;
    }
   
   
    long long readInt(long long l, long long r, char endd) {
        long long x=0;
        int cnt=0;
        int fi=-1;
        bool is_neg=false;
        while(true) {
            char g=getchar();
            if(g=='-') {
                assert(fi==-1);
                is_neg=true;
                continue;
            }
            if('0'<=g&&g<='9') {
                x*=10;
                x+=g-'0';
                if(cnt==0) {
                    fi=g-'0';
                }
                cnt++;
                assert(fi!=0 || cnt==1);
                assert(fi!=0 || is_neg==false);
   
                assert(!(cnt>19 || ( cnt==19 && fi>1) ));
            } else if(g==endd) {
                if(is_neg) {
                    x=-x;
                }
                assert(l<=x&&x<=r);
                return x;
            } else {
                assert(false);
            }
        }
    }
    string readString(int l, int r, char endd) {
        string ret="";
        int cnt=0;
        while(true) {
            char g=getchar();
            assert(g!=-1);
            if(g==endd) {
                break;
            }
            cnt++;
            ret+=g;
        }
        assert(l<=cnt&&cnt<=r);
        return ret;
    }
    long long readIntSp(long long l, long long r) {
        return readInt(l,r,' ');
    }
    long long readIntLn(long long l, long long r) {
        return readInt(l,r,'\n');
    }
    string readStringLn(int l, int r) {
        return readString(l,r,'\n');
    }
    string readStringSp(int l, int r) {
        return readString(l,r,' ');
    }
   
    void solve() {
        string s=readStringLn(1,100000);
        for(char i:s)
            assert(('a'<=i&&i<='z')||('A'<=i&&i<='Z'));
        for(int i=0; i+4<sz(s); i++) {
            if(s.substr(i, 5)=="party") {
                s[i+2]='w';
                s[i+3]='r';
                s[i+4]='i';
            }
        }
        cout<<s<<endl;
    }
    signed main() {
        ios_base::sync_with_stdio(0),cin.tie(0);
        srand(chrono::high_resolution_clock::now().time_since_epoch().count());
        cout<<fixed<<setprecision(10);
        int t=readIntLn(1,10);
    //  int t;
    //  cin>>t;
        fr(i,1,t)
            solve();
    #ifdef rd
        cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
    #endif
    }

Editorialist
    #include<bits/stdc++.h>
    using namespace std;
   
    #define _z ios_base::sync_with_stdio(false); cin.tie(NULL);
    #define int long long int
    #define endl "\n"
    #define mod 1000000007
    #define pb_ push_back
    #define mp_ make_pair
    //______________________________z_____________________________
   
    void solve()
    {
        string s;
        cin>>s;
        for(int i=0; i<s.size(); i++) {
            if(i+4<s.size() && s.substr(i, 5)=="party") {
                s[i+2]='w';
                s[i+3]='r';
                s[i+4]='i';
                i+=4;
            }
        }
        cout<<s<<endl;
    }
   
    int32_t main()
    {
        _z;
        int t=1;
        cin>>t;
        while(t--)
        {
            solve();
        }
    }

2 Likes

I used the same technique but still got a LTE error, https://www.codechef.com/viewplaintext/43991968

For C++ coders, you can refer this stackoverflow article
It uses built-in find() and replace() string functions to solve the problem

Below is my solution for reference

#include <iostream>
#include <string>

#define deb(x) cout << #x << ": " << x << endl;
#define deb2(x, y) cout << #x << ": " << x << " ~ " << #y << ": " << y << endl;
#define in(n, arr)              \
    for (int i = 0; i < n; i++) \
    cin >> arr[i]
#define out(n, arr)             \
    for (int i = 0; i < n; i++) \
    cout << arr[i]

using namespace std;

int main()
{
#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    freopen("out.txt", "w", stdout);
#endif

    int t;
    cin >> t;
    while (t--)
    {
        string ip;
        cin >> ip;

        // size_t = unsigned int
        size_t index = 0;
        while(true)
        {
            index = ip.find("party", index);

            // npos - value returned by member functions when they fail
            if(index==string::npos)
                break;

            ip.replace(index, 5, "pawri");
            index += 5;
        }

        cout << ip << "\n";
    }
}
1 Like

I applied the below technique but still got a runtime error. This being my first time with string operations i could not figure out why? can some one help which line caused the error and why?

#include<stdio.h>
#include<string.h>

int main() {
long long int testcases;
scanf("%lld",&testcases);
while(testcases–){
char s[10000];
scanf("%s",s);
long long int x = strlen(s);
for(long long int i=0;i+4<x;i++){
if(s[i]==‘p’ && s[i+1]==‘a’ && s[i+2]==‘r’ && s[i+3]==‘t’ && s[i+4]==‘y’){
s[i+2]=‘w’;
s[i+3]=‘r’;
s[i+4]=‘i’;
}
}
printf("%s\n",s);
}
}

Runtime Error : This error mostly occurs when you are illegally accessing some memory . Like if you have taken an array a[100], but the test files try to access a[102] then that will imply a SIGSEGV. Or, if your algorithm itself is trying to illegally access some memory then too, it occurs.

The constraint for the string was upto 10^5 but in your program you declared a character array upto range 10^4

char s[10000];    // this line was causing Runtime Error 

Link to your AC soln

#include
#include
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
string s;
cin>>s;
string temp=“pawry”;
int i=0;
int flag=0;

	while(s[i]!='\0'&& (i+4)<s.size())
	{  
		if(s.substr(i,5)=="party")
		{ 
		    int j=0;
		    while(j<5)
		    {
		        s[i]=temp[j];
		        i++;
		        j++;
		    }
		    continue;
		}
		
		    
		  i++; 
		                
		                 
	}
	
	cout<<s<<endl;
	
}

return 0;

}

i am not getting why it is showing WA

// Online C compiler to run C program online
#include <stdio.h>
#include<string.h>
#define ll long int

int main() {
  int t;
    scanf("%d",&t);
    while(t--)
        {
            ll doom=100001;
            char str[doom];
            scanf("%s",&str);
            
            for(ll i=0;i<strlen(str)+1;++i)
                {
                   if(str[i]=='p'&&str[i+1]=='a'&&str[i+2]=='r'&&str[i+3]=='t'&&str[i+4]=='y')
                   {
                       str[i+2]='w';
                       str[i+3]='r';
                       str[i+4]='i';
                       
                   }
                }
               
                printf("%s\n",str);
        }
    
    
    return 0;
}

This is my code guys…I do not know how but it is showing that time limit exceeded. The program is to the point and passes all the sample testcases in question and custom testcases made by me. Why it is showing TLE I do not understand. Please help me out.

Hey @iron102
Thanks for asking your doubt.

As you may know that strlen returns the length of a string in O(n). So when you are writing this in a loop :point_down:

Here for every i (0<= i <n) you are calling strlen function. so the time complexity of your code will be O(n*n).

To solve this issue, Just declare a variable that denotes the length of the string before loop.

int len =strlen(str);
for(ll i=0;i<len+1;++i)