LT12-Editorial

editorial
, , , , ,
1

Problem Link

Loop Through

Author:pskalbhav1

Difficulty

MEDIUM

Prerequisites

Divide and Conquer, Strings, Sortings

Problem Statement

In a retro game, the winner wins if the two strings a and b of equal length are called equivalent. They should satisfy either of the two conditions:
1] They are the same.
2] If we split both the strings into two equals halves, then one of the following is correct:
a) a1 is equivalent to b1, and a2 is equivalent to b2
b) a1 is equivalent to b2, and a2 is equivalent to b1

You need to determine if they are equivalent.

Approach

Let us note that "equivalant" described in the statements is actually equivalence relation, it is reflexively, symmetrical and transitive. Let's find lexicographic minimal strings what is equivalent to first and to second given string. And then check if its are equals.

It is remain find the lexicographic minimal strings what is equivalent to given. For instance we can do it such a way:

String smallest(String s) {
    if (s.length() % 2 == 1) return s;
    String s1 = smallest(s.substring(0, s.length()/2));
    String s2 = smallest(s.substring(s.length()/2), s.length());
    if (s1 < s2) return s1 + s2;
    else return s2 + s1;
}

Every recursive call time works is O(n) and string split by two twice smaller strings. Therefore time of work this function is O(nlog(n)), where n is length of strings.

Solution

 #include <bits/stdc++.h>
 using namespace std;
 string dac(string s){
    if(s.size()%2)return s;
    string a = dac(s.substr(0,s.size()/2));
    string b = dac(s.substr(s.size()/2));
    if(a < b) return a+b;
    return b + a;
 }
 int main()
{
    string s, t;
    cin>>s>>t;
    cout << ((dac(s) == dac(t)) ? "YES" : "NO");
    return 0;
 }