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.
#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;
}
0 Comments