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:
- 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}\}.
- 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();
}