COPYPUSH-Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setters: Nishank Suresh, TheScrasse
Tester: Manan Grover, Abhinav Sharma
Editorialist: Devendra Singh

DIFFICULTY:

1595

PREREQUISITES:

None

PROBLEM:

Anton loves creating strings!

Anton now wants to create a string S following some specific rules. They are as follows:

Initially, S is empty. Then, Anton can perform two types of operations on S:

  1. Choose a lowercase Latin character (an element of \{a, b, c, \ldots, z\}) and append it to S. For example, if currently S = \texttt{clap}, Anton can turn it into one of \{\texttt{clapa}, \texttt{clapb}, \ldots, \texttt{clapz}\}.
  2. Append a copy of S to itself. For example, if currently S = \texttt{clap}, Anton can turn it into \texttt{clapclap}.

However, Anton doesn’t want to perform operation 1 twice in a row.

You are given a string A consisting of the lowercase Latin alphabet. Is it possible for Anton to create A using his operations any number of times?

EXPLANATION:

Observation: The operation of first type can only be applied when the length of the string is even.
First type of operation can be applied when the string is empty or immediately after an operation of second type has been performed on the string. After every operation of second type the length of the resulting string is even (2 \cdot length of original string). Therefore the operation of first type can only be applied when the length of the string is even and finally resulting in an odd length string.
This means if the length of the string is even then the last operation performed on it has to be of second type otherwise if the length of the string is odd the last operation performed on it has to be of first type.

Start with the given string and keep on moving until the string becomes empty:

  • If the size of the present string is odd, simply remove the last character of the string (operation of first type).
  • If the size of the present string is even, Check whether this string is the copy of two equal strings(operation of second type) and reduce the size of the string by half. If the present string can’t be obtained by a single operation of second type then stop iterating.

If the string is empty at the end then it can be constructed using these operations otherwise it cannot be constructed using these operations.

TIME COMPLEXITY:

O(N) for each test case.

SOLUTION:

Setter's solution(Python)
for _ in range(int(input())):
	n = int(input())
	s = input()
	while len(s) > 0:
		if len(s)%2 == 1:
			s = s[:-1]
		else:
			k = len(s)//2
			if s[:k] == s[k:]:
				s = s[:k]
			else:
				break
	print('YES' if len(s) == 0 else 'NO')
Editorialist's Solution
#include "bits/stdc++.h"
using namespace std;
#define ll long long
#define pb push_back
#define all(_obj) _obj.begin(), _obj.end()
#define F first
#define S second
#define pll pair<ll, ll>
#define vll vector<ll>
ll INF = 1e18;
const int N = 1e5 + 11, mod = 1e9 + 7;
ll max(ll a, ll b) { return ((a > b) ? a : b); }
ll min(ll a, ll b) { return ((a > b) ? b : a); }
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
void sol(void)
{
    int n;
    cin >> n;
    string s;
    cin >> s;
    while (s.size())
    {
        if (s.size() % 2)
            s.pop_back();
        else
        {
            if (s.substr(0, s.size() / 2) != s.substr(s.size() / 2, s.size() / 2))
            {
                cout << "NO\n";
                return;
            }
            s = s.substr(0, s.size() / 2);
        }
    }
    cout << "YES\n";
    return;
}
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);
    int test = 1;
    cin >> test;
    while (test--)
        sol();
}
3 Likes

What’s wrong with the following code?

void solve(){
    int n;
    cin >> n;
    string s;
    cin >> s;
    string temp;
    bool fine = true;
    bool iso = true;
    for(int i=0; i<n;) {
        if(iso){
            iso = false;
            temp += s[i];
            i++;
        } else {
            iso= true;
            int tl = temp.length();
            if(tl > n - i) {
                fine = false;
                break;
            }
            int j,k;
            for(k=0,j=i; k < tl; ++j, k++) {
                if(s[j] != temp[k]){
                    fine = false;
                    break;
                }
                temp += s[j];
            }
            if(!fine) break;
            i = j;
        }
    }
    if(fine) cout << "YES\n";
    else cout << "NO\n";
}

It passed only 2 test cases.

Approach:
I have tried to construct the given string. Starting with inserting the first character the given two operations have been performed alternatively …for the odd index a for loop is run to check whether a copy of the string built so far lies next to the current index of the original string. If at any given index it fails return false otherwise continue till the end and return true.

@devendra7700
How does the complexity of Editorial Solution O(n)? s.substr takes O(N) right?
I know the size of the string is reduced by half.

Sir, will you please explain the time complexity of O(N) ?

2 Likes

Operation 1 cannot be performed twice in a row but Operation 2 can be performed more than once in a row.
example : aabaabaabaab
In above example seq of operation is : op1, op2, op1,op2,op2

Your code gives no while ans is yes.

1 Like

Thanks! I limited both operations to be performed once.

1 Like

Yeah, I made the same mistake at first.

First kind of operation can happen at most log_2(N) times as every time it is performed we remove the last character in O(1) time and the next operation is performed which reduces the string size by half.

Now talking about the handling of second kind of operation, initially it takes 2*N iterations after that 2*N/2 iterations then 2*N/4 iterations which is 2*(N+N/2+N/4+N/8.....) which is less than or equal to 4*N
Hence overall it is O(N+log(N)) which is O(N)

3 Likes

Thank you :smile:

my this submission CodeChef: Practical coding for everyone was giving wrong answer on three test case but (CodeChef: Practical coding for everyone) it was accepted can anyone tell why is it happening . my approach is same in both submissions .

the test case which is not passing in submission 1 is abcabcz can anyone tell me why it is not passing ?

def add(string,letter):
return string+letter
def duplicate(string):
return string+string

t = int(input())
for i in range(0,t):
x = int(input())
y = input()

string = y[0]
while(True):
    if(string != y[0:len(string)]):
        print("NO")
        break
    elif(string==y):
        print("YES")
        break
        
    string = duplicate(string)
    while((string + string) == y[0:len(string)*2]):
        string = duplicate(string)
    
    if(string != y[0:len(string)]):
        print("NO")
        break
    elif(string==y):
        print("YES")
        break

    string = add(string,y[len(string)])

whats wrong with this code? 3 test cases didnt pass

You have to do return check( r/2 , s ) instead of check( r/2 , s ) in your check function.

1 Like

bool solve(string s1, string s2,bool f)
{
if(s1[s2.size()-1] != s2[s2.size()-1])return false;
if(s1.size()<= s2.size())
return s1==s2;
if(f)
{
s2 = s2+s2;
return solve(s1,s2,true) || solve(s1,s2,false);
}
else
{
string tem = s2+s2;
string tem2 = s2+s1[s2.size()];
return solve(s1,tem,true) || solve(s1,tem,false) || solve(s1,tem2,true);
}
}

can anyone help me to solve this using recursion in more optimise way , I try but got 2 TLE test cases

We don’t need to care about operation 1 or modify the string - just repeatedly divide N by 2 (as integer), and check that the first two consecutive substrings of length N are equal.

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

char s[1000001];

int main() {
    int n;
    for(scanf("%*d"); ~scanf("%d%s", &n, s);) {
        char const* r = "YES";
        while(n >>= 1) {
            if(memcmp(s, s + n, n)) {
                r = "NO";
                break;
            }
        }
        puts(r);
    }
    return 0;
}

Hi. In the editorialist’s solution. It’s given
if (s.substr(0, s.size() / 2) != s.substr(s.size() / 2, s.size() / 2))

Isn’t it supposed to be if (s.substr(0, s.size() / 2) != s.substr(s.size() / 2, s.size())) ?

No, we are comparing first half of string with second half of string. So we use s.substr( index, length) function to find substring of length s.length()/2 starting from index 0 and substring of same length from index s.length()/2.

Can anyone please tell me whts wrong in this code?
3 test cases are giving WA.

#include <bits/stdc++.h>
using namespace std;
#define vi vector<int>
#define vvi vector<vi>
#define vp vector<pair<int,int>>
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define T true
#define F false
#define sz size()
#define mahadev ios_base::sync_with_stdio(false); cin.tie(NULL); 
#define full_line(s) getline(cin, s)
#define in(n) int n;cin >> n
#define in2(a, b) int a,b;cin >> a >> b
#define pn(p) cout<<p<<endl
#define pt(p) cout<<p<<" "
#define pt2(p,q) cout<<p<<" "<<q<<endl
#define pt3(p,q,r) cout<<p<<" "<<q<<" "<<r<<endl
#define pt4(p,q,r,s) cout<<p<<" "<<q<<" "<<r<<" "<<s<<endl
#define vfor(v) for (auto itr =v.begin() ; itr!=v.end(); itr++)
#define vbfor(v) for (auto itr =v.rbegin() ; itr!=v.rend(); itr++)
#define ffor(i, a, b) for (int i = a; i < b; i++)
#define bfor(i, a, b) for (int i = a - 1; i >= b; i--)
#define all(v) v.begin(),v.end()
#define Y "YES" 
#define N "NO" 
/*------------------------------------begin------------------------------------*/
string s;
bool isSecondOperationApplicable(int i){
    int len=i;
    if(len*2>s.size())return false;
    string f=s.substr(0,len);
    string sec=s.substr(i,len);
    return (sec==f);
}
void solve()
{
    in(n);
    cin>>s;
    bool isFirstOperationUsable=F;
    int i=1;
    while(i<n){
        if(isSecondOperationApplicable(i)){
            i=i<<1;
            isFirstOperationUsable=T;
            continue;
        }
        if(isFirstOperationUsable){
            i++;
            isFirstOperationUsable=F;
        }else{pn(N);return;}
    }
    pn(Y);
}

/*-------------------------------------end-------------------------------------*/
signed main()
{
    mahadev;
    int t;
    cin>>t;
    
    while(t--)
    {
        solve();
    }
    
    return 0;
}

or you can see it here : CodeChef: Practical coding for everyone

if anyone is wondering how to solve this problem using recursion and memoization.
https://www.codechef.com/viewsolution/92186039