[Hackerearth] Palindrome Split

 

Problem Link    : Palindrome Split
Category        : Add Hoc
Contest         : January Circuits '24

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = true; string FILE = "in.txt";
    if (FILEIO and fopen(FILE.c_str(), "r")) {
        freopen(FILE.c_str(), "r", stdin);
    }
 
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++) {
        string s;
        cin >> s;
        int ans = 0;
        for (char ch = 'a'; ch <= 'z'; ch++) {
            int cnt = count(s.begin(), s.end(), ch);
            ans += cnt / 2;
        }
        cout << ans << endl;
    }
}

[Hackerearth] Make Palindrome

 

Problem Link    : Make Palindrome
Category        : Add Hoc
Contest         : DSA Coding Contest - January '24

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = 1;
    if (FILEIO and fopen("in.txt", "r")) {
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
    }
 
    int tc;
    cin >> tc;
    for (int tcase = 1; tcase <= tc; tcase++) {
        int n; string s;
        cin >> n >> s;
        vector<int> counters(26);
        for (char ch : s) {
            counters[ ch - 'a' ]++;
        }
        int odds = 0;
        for (int x : counters) {
            odds += x % 2;
        }
        cout << max(0LL, odds - 1) << endl;
    }
}

[Hackerearth] Farthest Coprime

Problem Link    : Farthest Coprime
Category        : Add Hoc
Contest         : January Easy '24

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
const int maxn = 1e3 + 5;
 
using pii = pair<int, int>;
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = 1;
    if (FILEIO and fopen("in.txt", "r")) {
        freopen("c2.txt", "r", stdin);
        freopen("c2-out.txt", "w", stdout);
    }
 
    int n, q;
    cin >> n >> q;
    vector<int> arr(n + 1);
    map<int, vector<int>> cache;
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        cache[ arr[i] ].push_back(i);
    }
    vector<vector<pii>> queries(maxn);
    vector<int> ans(q, -1);
    for (int i = 0; i < q; i++) {
        int pos;
        cin >> pos;
        queries[ arr[pos] ].push_back({pos, i});
    }
    for (int i = 1; i < maxn; i++) {
        if (queries[i].size() == 0) {
            continue;
        }
        int minPos = n + 1;
        int maxPos = -1;
        for (auto it : cache) {
            if (__gcd(i, it.first) > 1) {
                continue;
            }
            minPos = min(minPos, it.second[0]);
            maxPos = max(maxPos, it.second.back());
        }
        if (maxPos != -1) {
            for (pii p : queries[i]) {
                int diff = max(abs(p.first - minPos), abs(p.first - maxPos));
                if (abs(p.first - minPos) > abs(p.first - maxPos)) {
                    ans[p.second] = minPos;
                } else if (abs(p.first - maxPos) > abs(p.first - minPos)) {
                    ans[p.second] = maxPos;
                } else {
                    ans[p.second] = min(minPos, maxPos);
                }
            }
        }
    }
    for (int i = 0; i < q; i++) {
        cout << ans[i] << " ";
    }
}

[Hackerearth] Hamming Sort

 

Problem Link    : Hamming Sort 
Category        : Add Hoc
Contest         : January Easy '24

#include<bits/stdc++.h>
using namespace std;
vector<int> solve (vector<int> arr, int k) {
   int n = arr.size();
   vector<int> marr;
   for (int i = 1; i < n; i++) {
        marr.push_back(arr[i]);
   }
   marr.push_back(k);
   k = arr[0];
   vector<pair<int, int>> cache;
   for (int i = 0; i < marr.size(); i++) {
        int val = marr[i];
        int xors = val ^ k;
        int bits = __builtin_popcount(xors);
        cache.push_back({bits, val}); 
   }
   sort(cache.begin(), cache.end());
   vector<int> ans;
   for (int i = 0; i < cache.size(); i++) {
        ans.push_back(cache[i].second);
   }
   return ans;
}
 
int main() {
 
    ios::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    for(int t_i = 0; t_i < T; t_i++)
    {
        int N;
        cin >> N;
        vector<int> arr(N);
        for(int i_arr = 0; i_arr < N; i_arr++)
        {
        	cin >> arr[i_arr];
        }
        int K;
        cin >> K;
 
        vector<int> out_;
        out_ = solve(arr, K);
        cout << out_[0];
        for(int i_out_ = 1; i_out_ < out_.size(); i_out_++)
        {
        	cout << " " << out_[i_out_];
        }
        cout << "\n";
    }
}

[Hackerearth] Text Wrap

 

Problem Link    : Text Wrap
Category        : Add Hoc
Contest         : January Easy '24

#include "bits/stdc++.h"
using namespace std;
#define int     long long int
#define endl    '\n'
 
signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);
    cout.precision(12);
 
    bool FILEIO = 1;
    if (FILEIO and fopen("d3.txt", "r")) {
        freopen("d3.txt", "r", stdin);
    }
 
    int n, m;
    cin >> n >> m;
    deque<int> lines(n);
    for (int &line : lines) {
        cin >> line;
    }
    int lo = 0;
    int hi = 1e16;
    int ans = 0;
    while (lo <= hi) {
        int mid = lo + hi >> 1;
        int linesRequired = 0;
        deque<int> tmp = lines;
        while (tmp.size()) {
            int sum = tmp.front(); tmp.pop_front();
            if (sum > mid) {
                linesRequired = m + 1;
                break;
            }
            linesRequired++;
            while (tmp.size() and sum + 1 + tmp.front() <= mid) {
                sum += 1 + tmp.front();
                tmp.pop_front();
            }
        }
        if (linesRequired <= m) {
            ans = mid;
            hi = mid - 1;
        } else {
            lo = mid + 1;
        }
    }
    cout << ans << endl;
}

[Gym] 102021F - Fighting Monsters

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : 102021F - Fighting Monsters
Source            : Codeforces Gym
Category          : Finding Pattern
Algorithm         : Fibonacci Series
Verdict           : Accepted

#include "bits/stdc++.h"  
  
using namespace std;  
  
#define ll       long long int  
  
static const int maxn = 1e6 + 6;  
  
int fibo[maxn];  
int FIBO[maxn];  
int kototomo[maxn];  
int index[maxn];  
int arr[maxn];  
  
void calcFibo()  
{  
    int ptr = 0;  
    fibo[1] = 1;  
    kototomo[1] = ++ptr;  
    FIBO[ptr] = 1;  
    fibo[2] = 1;  
    for (int i = 3; ; i++)  
    {  
        ll fib = (ll)fibo[i-1] + (ll)fibo[i-2];  
        if (fib > 1000000) break;  
        fibo[i] = (int)fib;  
        kototomo[ fibo[i] ] = ++ptr;  
        FIBO[ptr] = fibo[i];   
    }  
}  
  
int main()  
{  
//    freopen("in.txt", "r", stdin);  
  
    calcFibo();  
  
    int n;  
    cin >> n;  
    for (int i = 1; i <= n; i++)  
    {  
        cin >> arr[i];  
        if (arr[i] == 1)  
        {  
            if (index[1] > 0)  
            {  
                cout << index[1] << " " << i << endl;  
                exit(0);  
            }  
        }  
        if (kototomo[ arr[i] ] > 0)  
        {  
            int l = FIBO[ kototomo[ arr[i] ] - 1 ];  
            int r = FIBO[ kototomo[ arr[i] ] ];  
            if (index[l] > 0)  
            {  
                cout << index[l] << " " << i << endl;  
                exit(0);  
            }  
        }  
        index[ arr[i] ] = i;  
    }  
    fill(begin(index), end(index), 0);  
    for (int i = n; i >= 1; i--)  
    {  
        if (arr[i] == 1)  
        {  
            if (index[1] > 0)  
            {  
                cout << index[1] << " " << i << endl;  
                exit(0);  
            }  
        }  
        if (kototomo[ arr[i] ] > 0)  
        {  
            int l = FIBO[ kototomo[ arr[i] ] - 1 ];  
            int r = FIBO[ kototomo[ arr[i] ] ];  
            if (index[l] > 0)  
            {  
                cout << index[l] << " " << i << endl;  
                exit(0);  
            }  
        }  
        index[ arr[i] ] = i;  
    }  
    cout << "impossible\n";  
}