Google Kickstart Round E 2021 Solutions

Date: 22/08/2021

Time: 09:00AM to 12:00PM

Duration: 3 Hours

Problem: Shuffled Anagrams

Video Solution: https://youtu.be/LUyNCtKUXgk

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
#define lld long double
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define fl(i,n) for(int i=0;i<n;i++)
#define rl(i,m,n) for(int i=n;i>=m;i--)
#define py cout<<"YES\n";
#define pn cout<<"NO\n";
#define pi 3.141592653589793238
#define vr(v) v.begin(),v.end()
#define rv(v) v.end(),v.begin()
#define fast ios_base::sync_with_stdio(false);
#define input cin.tie(NULL);
#define output cout.tie(NULL);
using namespace std;
ll gcd(ll a, ll b){if (b == 0)return a;return gcd(b, a % b);}
ll lcm(ll a, ll b){return (a/gcd(a,b)*b);}
bool sorta(const pair<int,int> &a,const pair<int,int> &b){return (a.second < b.second);}
bool sortd(const pair<int,int> &a,const pair<int,int> &b){return (a.second > b.second);}
void printarr(ll arr[], ll n){fl(i,n) cout << arr[i] << " ";cout << "\n";}
string decToBinary(int n){string s="";int i = 0;while (n > 0) {s =to_string(n % 2)+s;n = n / 2;i++;}return s;}
ll binaryToDecimal(string n){string num = n;ll dec_value = 0;int base = 1;int len = num.length();for(int i = len - 1; i >= 0; i--){if (num[i] == '1')dec_value += base;base = base * 2;}return dec_value;}
bool isPrime(int n){if(n<=1)return false;if(n<=3)return true;if(n%2==0||n%3==0)return false;for(int i=5;i*i<=n;i=i+6)if(n%i==0||n%(i+2)==0)return false;return true;}
bool isPowerOfTwo(int n){if(n==0)return false;return (ceil(log2(n)) == floor(log2(n)));}
//Code by Abhinav Awasthi
//Language C++
//Practice->Success
int isanagram(string s, string temp)
{
    int n=s.size();

    for(int i=0;i<n;i++)
    {
        if(s[i]==temp[i])
        return i;
    }
    return -1;
}
void asquare()
{
    string s;
    cin>>s;
    int n=s.size();
    map<char,int>mpp;
    for(int i=0;i<s.size();i++)
    {
        mpp[s[i]]++;
    }
    
    for(auto x:mpp)
    {
        if(x.second>n/2)
        {
            cout<<"IMPOSSIBLE";
            return;
        }
    }

    string temp=s;
    
    bool visited[n];
    memset(visited,false,n);
    for(int i=0;i<s.size();i++)
    {
        if(!visited[i])
        {
        for(int j=i+1;j<s.size();j++)
        {
            
            if(s[i]!=s[j])
            {
                visited[j]=true;
                swap(s[i],s[j]);
                break;
            }
        }
        }
    }
        while(true)
        {
        int index=isanagram(s,temp);
        if(index==-1)
        break;
        for(int i=0;i<n;i++)
        {
            if(s[i]!=s[index]&&temp[i]!=s[index])
            {
                swap(s[i],s[index]);
                break;
            }
        }
        
        
    }

    cout<<s;
 
}
int main()
{
    fast input output
    ll t;
    cin>>t;
    fl(ii,t)
    {
        cout<<"Case #"<<ii+1<<": ";
        asquare();
        cout<<"\n";
    }
    return 0;
}

Click here to visit contest page.

Subscribe our YouTube channel for solutions.

Join Telegram for Post Contest Discussions.