SWAPCW - Editorial

[lavish_adm]

PROBLEM LINK:

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

Setter: Pranav Dev
Tester: Abhinav Sharma, Aryan
Editorialist: Lavish Gupta

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Chef is working on his swap-based sorting algorithm for strings.

Given a string S of length N, he wants to know whether he can sort the string using his algorithm.

According to the algorithm, one can perform the following operation on string S any number of times:

• Choose some index i (1 \leq i \leq N) and swap the i^{th} character from the front and the i^{th} character from the back.
  More formally, choose an index i and swap S_i and S_{(N+1-i)}.

For example, \underline{\texttt{d}} \texttt{cb} \underline{\texttt{a}} can be converted to \underline{\texttt{a}} \texttt{cb} \underline{\texttt{d}} using one operation where i = 1.

Help Chef find if it is possible to sort the string using any (possibly zero) number of operations.

EXPLANATION:

Let us first find out the string that the Chef will end up with, given that he performs the swap optimally.

Let us consider the index i and j = (N+1-i). Also, let i \leq j. If S_i \leq S_j then we do not need to swap these characters (as they are in already in correct order). Otherwise, we will swap S_i and S_j.

Let us first perform the above operation by iterating over the complete string, and let us denote the final string as S'. If S' is sorted, then our answer is YES, otherwise our answer will be NO.

To check if S' is sorted, we can iterate over the string and check that S_i \leq S_{i+1} for all i such that 1 \leq i \leq N-1. Another way to check is to use the sort function which is usually present in the Standard Template Library (or similar libraries) in most of the languages.

TIME COMPLEXITY:

O(N) or O(N\cdot \log{N}) for each test case, depending on the implementation details.

SOLUTION:

Editorialist's Solution

#define ll long long
#define fo(i , n) for(ll i = 0 ; i < n ; i++)
#include<bits/stdc++.h>
using namespace std ;


void solve()
{
    ll n ;
    cin >> n ;

    string a , b ;
    cin >> a ;

    b = a ;
    sort(b.begin() , b.end()) ;

    for(int i = 0 ; i < n ; i++)
    {
        int j = (n-1-i) ;
        if(j < i)
            break ;

        if(a[i] > a[j])
            swap(a[i] , a[j]) ;
    }

    if(a == b)
        cout << "YES\n" ;
    else
        cout << "NO\n" ;
    return ;
}

 
int main()
{   
    
    ll t = 1 ;
    cin >> t ;
    while(t--)
    {
        solve() ;
    }
    
    cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
 
    return 0;
}

[d_patil_02]

#include <bits/stdc++.h>

using ll = long long;
using namespace std;

#define endl "\n"

void solveTestCase()
{
    ll N;
    cin >> N;
    string S;
    cin >> S;
    for (int i = 0; i < N / 2; i++)
    {
        if (S[i] > S[N - 1 - i])
            swap(S[i], S[N - 1 - i]);
        else
            continue;
    }

    for (int i = 1; i < N; i++)
    {
        if (S[i] < S[i - 1])
        {
            cout << "N0" << endl;
            return;
        }
    }
    cout << "YES" << endl;
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    int testCases;
    cin >> testCases;
    while (testCases--)
    {
        solveTestCase();
    }

    return 0;
}

//Whats the problem in my code ??

[nishan_adm]

Hey, in cases where the answer should be “NO”, yoy have printed “N0”, basically you have used the number 0, instead of alphabet O

[d_patil_02]

Thanks bro