Header Ad

HackerEarth Swapping positions problem solution

In this HackerEarth Swapping positions problem solution you are given two strings S and t of length n. You can select any two positions (can be from the same or different strings) and swap the characters at those two positions. You have to perform this operation exactly once in such a way that there exists a maximum of one position i (1 <= i <= n)  such that Si != ti. Determine whether it is possible to perform the operation such that the given condition holds or not.


HackerEarth Swapping positions problem solution


HackerEarth Swapping positions problem solution.

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define MP make_pair
#define ff first
#define ss second
#define FOR(i,x,y) for(LL i = (x) ; i <= (y) ; ++i)
#define CLR(x,y) memset(x,y,sizeof(x))
#define ALL(x) (x).begin(),(x).end()
#define SZ(x) ((LL)(x).size())
#define POPCOUNT __builtin_popcountll
#define ODD(x) (((x)&1)==0?(0):(1))
#define Set(N,p) N=((N)|((1LL)<<(p)))
#define Reset(N,p) N=((N)&(~((1LL)<<(p))))
#define Check(N,p) (!(((N)&((1LL)<<(p)))==(0)))
#define LL long long
#define LLU long long unsigned int

int N;
string a, b;

int miscnt(string a, string b){
int cnt = 0;
FOR(i,0,N-1){
if(a[i] != b[i]) cnt++;
}
return cnt;
}

bool okay(int i, int j){
string s1, s2;
s1 = a, s2 = b;
swap(s1[i], s1[j]);
if(miscnt(s1, s2)<=1) return true;
s1 = a, s2 = b;
swap(s1[i], s2[j]);
if(miscnt(s1, s2)<=1) return true;
return false;
}

bool possible(){
vector<int> List;
FOR(i,0,N-1){
if(a[i] != b[i]) List.pb(i);
}
if(SZ(List)<=1) return true;
if(SZ(List) <= 3){
FOR(i,0,SZ(List)-1){
FOR(j,i+1,SZ(List)-1){
if(okay(List[i], List[j])) return true;
}
}
}
return false;
}

int main() {
int t;
cin>>t;
FOR(cs,1,t){
cin>>N>>a>>b;
if(possible()) printf("YES\n");
else printf("NO\n");
}
return 0;
}


Second solution

#include<bits/stdc++.h>

typedef unsigned int uint;
typedef long long ll;
typedef unsigned long long ull;
typedef double lf;
typedef long double llf;
typedef std::pair<int,int> pii;

#define xx first
#define yy second

template<typename T> inline T max(T a,T b){return a>b?a:b;}
template<typename T> inline T min(T a,T b){return a<b?a:b;}
template<typename T> inline T abs(T a){return a>0?a:-a;}
template<typename T> inline bool repr(T &a,T b){return a<b?a=b,1:0;}
template<typename T> inline bool repl(T &a,T b){return a>b?a=b,1:0;}
template<typename T> inline T gcd(T a,T b){T t;if(a<b){while(a){t=a;a=b%a;b=t;}return b;}else{while(b){t=b;b=a%b;a=t;}return a;}}
template<typename T> inline T sqr(T x){return x*x;}
#define mp(a,b) std::make_pair(a,b)
#define pb push_back
#define I __attribute__((always_inline))inline
#define mset(a,b) memset(a,b,sizeof(a))
#define mcpy(a,b) memcpy(a,b,sizeof(a))

#define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++)
#define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++)
#define fo(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define fd0(i,n) for(int i=(n)-1;~i;i--)
#define fd1(i,n) for(int i=n;i;i--)
#define fd(i,a,b) for(int i=a,i##end=b;i>=i##end;i--)
#define foe(i,x)for(__typeof((x).end())i=(x).begin();i!=(x).end();++i)
#define fre(i,x)for(__typeof((x).rend())i=(x).rbegin();i!=(x).rend();++i)

struct Cg{I char operator()(){return getchar();}};
struct Cp{I void operator()(char x){putchar(x);}};
#define OP operator
#define RT return *this;
#define UC unsigned char
#define RX x=0;UC t=P();while((t<'0'||t>'9')&&t!='-')t=P();bool f=0;\
if(t=='-')t=P(),f=1;x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0'
#define RL if(t=='.'){lf u=0.1;for(t=P();t>='0'&&t<='9';t=P(),u*=0.1)x+=u*(t-'0');}if(f)x=-x
#define RU x=0;UC t=P();while(t<'0'||t>'9')t=P();x=t-'0';for(t=P();t>='0'&&t<='9';t=P())x=x*10+t-'0'
#define TR *this,x;return x;
I bool IS(char x){return x==10||x==13||x==' ';}template<typename T>struct Fr{T P;I Fr&OP,(int&x)
{RX;if(f)x=-x;RT}I OP int(){int x;TR}I Fr&OP,(ll &x){RX;if(f)x=-x;RT}I OP ll(){ll x;TR}I Fr&OP,(char&x)
{for(x=P();IS(x);x=P());RT}I OP char(){char x;TR}I Fr&OP,(char*x){char t=P();for(;IS(t);t=P());if(~t){for(;!IS
(t)&&~t;t=P())*x++=t;}*x++=0;RT}I Fr&OP,(lf&x){RX;RL;RT}I OP lf(){lf x;TR}I Fr&OP,(llf&x){RX;RL;RT}I OP llf()
{llf x;TR}I Fr&OP,(uint&x){RU;RT}I OP uint(){uint x;TR}I Fr&OP,(ull&x){RU;RT}I OP ull(){ull x;TR}};Fr<Cg>in;
#define WI(S) if(x){if(x<0)P('-'),x=-x;UC s[S],c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0')
#define WL if(y){lf t=0.5;for(int i=y;i--;)t*=0.1;if(x>=0)x+=t;else x-=t,P('-');*this,(ll)(abs(x));P('.');if(x<0)\
x=-x;while(y--){x*=10;x-=floor(x*0.1)*10;P(((int)x)%10+'0');}}else if(x>=0)*this,(ll)(x+0.5);else *this,(ll)(x-0.5);
#define WU(S) if(x){UC s[S],c=0;while(x)s[c++]=x%10+'0',x/=10;while(c--)P(s[c]);}else P('0')
template<typename T>struct Fw{T P;I Fw&OP,(int x){WI(10);RT}I Fw&OP()(int x){WI(10);RT}I Fw&OP,(uint x){WU(10);RT}
I Fw&OP()(uint x){WU(10);RT}I Fw&OP,(ll x){WI(19);RT}I Fw&OP()(ll x){WI(19);RT}I Fw&OP,(ull x){WU(20);RT}I Fw&OP()
(ull x){WU(20);RT}I Fw&OP,(char x){P(x);RT}I Fw&OP()(char x){P(x);RT}I Fw&OP,(const char*x){while(*x)P(*x++);RT}
I Fw&OP()(const char*x){while(*x)P(*x++);RT}I Fw&OP()(lf x,int y){WL;RT}I Fw&OP()(llf x,int y){WL;RT}};Fw<Cp>out;

const int N=1005;

char a[N],b[N];

int main()
{
for(int T=in;T--;)
{
int n=in;
in,a,b;
std::vector<pii>u;
fo0(i,n)if(a[i]!=b[i])u.pb(mp(a[i],b[i]));
if(u.size()>=4)out,"NO\n";
else if(u.size()<=1)out,"YES\n";
else
{
bool ans=0;
fo0(i,u.size())fo0(a,2)fo0(j,i)fo0(b,2)
{
std::vector<pii>t=u;
if(a)std::swap(t[i].xx,t[i].yy);
if(b)std::swap(t[j].xx,t[j].yy);
std::swap(t[i].xx,t[j].xx);
int c=0;
fo0(k,t.size())if(t[k].xx!=t[k].yy)c++;
if(c<=1)ans=1;
}
out,ans?"YES":"NO",'\n';
}
}
}

Post a Comment

0 Comments