In this HackerEarth Mancunian in Palindromia problem solution Mancunian lives in the magical far-away land of Palindromic. Due to his patriotic nature, he wants each and every one of his friends' names to be a palindrome. Note that Mancunian's patriotism does not extend towards his own name.
To please him, each of his friends decides to change their name so that it becomes a palindrome. They can do that by choosing at most two non-overlapping substrings of their own name and reversing them.
Given a list of Mancunian's friends' names which consist only of lowercase letters, count the total number of friends who will be successful.


HackerEarth Mancunian in Palindromia problem solution


HackerEarth Mancunian in Palindromia problem solution.

#include <iostream>
#include <algorithm>
#include <stack>
#include <vector>
#include <cassert>
#include <queue>
#include <cmath>
#define ff first
#define ss second
#define pb push_back
#define MOD (1000000007LL)
#define LEFT(n) (2*(n))
#define RIGHT(n) (2*(n)+1)

using namespace std;
typedef long long ll;
typedef pair<ll, ll> ii;
typedef pair<ll, ii> iii;

ll pwr(ll base, ll p, ll mod = MOD){
ll ans = 1;while(p){if(p&1)ans=(ans*base)%mod;base=(base*base)%mod;p/=2;}return ans;
}


bool is_palindrome(string str){
    string temp = str;
    reverse(temp.begin(), temp.end());
    return (str == temp);
}


int main(){

    ios_base::sync_with_stdio(0);

    int t, len, ans = 0;
    cin>>t>>len;
    assert(t <= 10);
    assert(len <= 50);
    while(t--){

        string str;
        cin>>str;

        int n = str.length();
        assert(n <= len);

        bool yes = false;
        if(is_palindrome(str))  yes = true;

        for(int l1=0;l1<n;l1++)
        for(int r1=l1;r1<n;r1++){
            string temp = str;
            reverse(temp.begin()+l1, temp.begin()+r1+1);
            if(is_palindrome(temp)){
                yes = true;
            }
        }

        for(int l1=0;l1<n;l1++)
        for(int r1=l1;r1<n;r1++)
            for(int l2=r1+1;l2<n;l2++)
            for(int r2=l2;r2<n;r2++){
                string temp = str;
                reverse(temp.begin()+l1, temp.begin()+r1+1);
                reverse(temp.begin()+l2, temp.begin()+r2+1);
                if(is_palindrome(temp))
                    yes = true;
            }

        if(yes){
            ans++;
        }
        else{
        }
    }

    cout<<ans;
    return 0;
}

Second solution

#include <string>
#include <vector>
#include <map>
#include <list>
#include <iterator>
#include <cassert>
#include <set>
#include <queue>
#include <iostream>
#include <sstream>
#include <stack>
#include <deque>
#include <cmath>
#include <memory.h>
#include <cstdlib>
#include <cstdio>
#include <cctype>
#include <algorithm>
#include <utility>
#include <time.h>
#include <complex>
using namespace std;

#define FOR(i, a, b) for(int i=(a);i<(b);i++)
#define RFOR(i, b, a) for(int i=(b)-1;i>=(a);--i)
#define FILL(A,value) memset(A,value,sizeof(A))

#define ALL(V) V.begin(), V.end()
#define SZ(V) (int)V.size()
#define PB push_back
#define MP make_pair
#define Pi 3.14159265358979
#define x0 ikjnrmthklmnt
#define y0 lkrjhkltr
#define y1 ewrgrg

typedef long long Int;
typedef unsigned long long UInt;
typedef vector<int> VI;
typedef pair<int, int> PII;
typedef pair<Int, Int> PLL;
typedef pair<double, double> PDD;
typedef complex<double> base;

const int INF = 1000000000;
const int BASE = 1000000007;
const int MAX = 100007;
const int ADD = 1000000;
const int MOD = 1000000007;
const int CNT = 800;

int main()
{

  int res = 0;
  int n , l;
  cin >> n >> l;

  assert(n >= 1 && n <= 10);

  FOR(test,0,n)
  {
    string s;
    cin >> s;

    assert(SZ(s) >= 1 && SZ(s) <= l);

    bool ok = 0;
    int n = SZ(s);

    FOR(l1,0,n)
      FOR(r1,l1,n)
        FOR(l2,r1 + 1 , n)
          FOR(r2 , l2 , n)
          {
            string t = s;
            reverse(t.begin() + l1 , t.begin() + r1 + 1);
            reverse(t.begin() + l2 , t.begin() + r2 + 1);
            string tt = t;
            reverse(ALL(tt));
            if (tt == t)
              ok = 1;
          }

    res += ok;

  }

  cout << res << endl;

    return 0;
}