Header Ad

HackerEarth Two types of queries problem solution

In this HackerEarth Two types of queries problem solution you are given a string str. It costs one unit of a coin to change a character at an index. Your task is to convert it into a palindrome with minimum coins. Also, you are given  number of queries. The queries are of the following types:
  • 1 A B
  • 2
After solving the first type of query, you can convert character A into character B without any cost and vice versa. In the second type of query, you are required to answer the minimum cost that is required to convert the given string into a palindrome.


HackerEarth Two types of queries problem solution


HackerEarth Two types of queries problem solution.

#include <bits/stdc++.h>
#define ll long long
#define int ll
#define mod 1000000007
#define mod2 998244353
#define MAXN 200000 + 5
#define MAXM 100000 + 5
#define MAXV 1000000 + 5
#define LOGN 18
using namespace std;

#define pb push_back
#define mp make_pair
#define ff first
#define ss second
#define all(arr) arr.begin() , arr.end()
#define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
#define rep(i , a , n) for(ll i = a ; i < n ; i++)
#define s(arr) sort(all(arr))
#define r(arr) reverse(all(arr))
#define rs(arr) s(arr) ; r(arr)
#define con continue

//debug
#define trace1(x) cerr<<#x<<": "<<x<<endl
#define trace2(x, y) cerr<<#x<<": "<<x<<" | "<<#y<<": "<<y<<endl
#define trace3(x, y, z) cerr<<#x<<":" <<x<<" | "<<#y<<": "<<y<<" | "<<#z<<": "<<z<<endl
#define trace4(a, b, c, d) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<endl
#define trace5(a, b, c, d, e) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<endl
#define trace6(a, b, c, d, e, f) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<<f<<endl
#define trace7(a, b, c, d, e, f , g) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<< f << " | "<< #g <<": "<<g<<endl
#define trace8(a, b, c, d, e, f , g , h) cerr<<#a<<": "<<a<<" | "<<#b<<": "<<b<<" | "<<#c<<": "<<c<<" | "<<#d<<": "<<d<<" | "<<#e<< ": "<<e<<" | "<<#f<<": "<< f << " | " << #g <<": "<< g <<" | "<<#h<< ": " << h << endl

// mod helpers function
ll sum_mod(ll a , ll b , ll m = mod2){
return (a + b) % m;
}

ll minus_mod(ll a , ll b , ll m = mod2){
return ((a - b) % m + m) % m;
}

ll mul_mod(ll a , ll b , ll m = mod2){
return (a * b) % m;
}

ll modexpo(ll a , ll b){
ll res = 1;
while(b){
if (b % 2 == 1)
res = mul_mod(res , a);
a = mul_mod(a , a);
b /= 2;
}
return res;
}

struct DSU{
int size;
vector<int> id;
vector<int> si;
vector< vector < int > > adj;
DSU(int x)
{
size = x;
id.resize(x + 1);
si.resize(x + 1);
for (int i = 1 ; i <= x ; i++)
{
id[i] = i , si[i] = 1;
}
}

int getRoot(int a)
{
while(a != id[a])
a = id[a];
return a;
}
void merge(int a , int b)
{
if (si[a] < si[b])
{
swap(a , b);
}
si[a] += si[b];
id[b] = id[a];
}

void fun(int a , int b)
{
int x = getRoot(a);
int y = getRoot(b);
if (x == y)
return;
merge(x , y);
}
};

void solve() {
int n;
cin >> n;
string str;
cin >> str;
struct DSU temp(26);
int q;
cin >> q;
int prevans = 0;
map < pair < int , int > , int > ma;
for (int i = 0 ; i < n / 2 ; i++){
if (str[i] != str[n - 1 - i]){
prevans++;
int val1 = str[i] - 'a';
int val2 = str[n - 1 - i] - 'a';
if (val1 > val2)
swap(val1 , val2);
ma[mp(temp.getRoot(val1) , temp.getRoot(val2))]++;
}
}
while(q--){
int type;
cin >> type;
if (type == 1){
char a , b;
cin >> a >> b;
int val1 = a - 'a';
int val2 = b - 'a';
if (temp.getRoot(val1) == temp.getRoot(val2))
con;
temp.fun(a - 'a' , b - 'a');
map < pair < int , int > , int > ma1;
for (auto it : ma) {
int val1 = it.ff.ff;
int val2 = it.ff.ss;
int val1Root = temp.getRoot(val1);
int val2Root = temp.getRoot(val2);
if (val1Root == val2Root)
prevans -= it.ss;
else {
if (val1Root > val2Root)
swap(val1Root , val2Root);
ma1[{val1Root , val2Root}]+= it.ss;
}
}
ma = ma1;
}
else {
cout << prevans << endl;
}
}
}

signed main(){
FAST;
int t = 1;
while(t--){
solve();
}
return 0;
}

Second solution

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int maxn = 2e5 + 14, z = 26;
bool ok[z][z];
int n, q;
string s;
int get(){
int ans = 0;
for(int i = 0; i < n / 2; i++)
ans += !ok[s[i] - 'a'][s[n - i - 1] - 'a'];
return ans;
}
int main(){
ios::sync_with_stdio(0), cin.tie(0);
for(int i = 0; i < z; i++)
ok[i][i] = 1;
cin >> n >> s >> q;
int ans = get();
while(q--){
int t;
cin >> t;
if(t == 2)
cout << ans << '\n';
else{
char a, b;
cin >> a >> b;
a -= 'a', b -= 'a';
if(!ok[a][b]){
for(int i = 0; i < z; i++)
for(int j = 0; j < z; j++)
ok[i][j] |= ok[i][a] && ok[b][j] || ok[i][b] && ok[a][j];
ans = get();
}
}
}
}

Post a Comment

0 Comments