An undirected graph is called a ring if all its nodes have degree two. For a ring of size n, find the number of ways to color it using three colors Red, Green or Blue such that no two adjacent nodes have the same color.

Constraint — n < 2e5

We are given a sequence A = {a1, a2, ... , an} which is index wise sum of two sequences B = {b1, b2, ... , bn} and C = {c1, c2, ... ,cn}.

i.e. a1 = b1 + c1, a2 = b2 + c2 , ... , an = bn + cn

B is non decreasing and C is non increasing.

Find the minimum possible value of abs(b1) + abs(b2) + ... + abs(bn) + abs(c1) + abs(c2) + ... + abs(cn).

Constraint — array size <= 2e5, -1e8 < a[i] < 1e8.

for (s[pos += n] = val; pos /= 2;){
      // code
}

saw this in a segment tree implementation. How does this work ?

I didn't notice that as per the question statement, we can only switch adjacent characters to reach the original string.

If this wasn't the case and we could switch any characters of the string, how would you solve it.

I wrote a greedy solution: complete as many possible cycles of A -> N -> T -> O -> A until we exhaust the least frequent character. Followed by smaller and smaller cycles.

by completing cycles A -> N -> O -> A, I mean swap 'A' and 'N', swap 'N' and 'O' and so on.

code

#include "bits/stdc++.h"
#define int long long
using namespace std;

void solve(int _case){

    string s;
    cin >> s;
    int n = s.length();

    map<char, vector<int>> pos;
    for(int i{}; i < n; ++i){
        pos[s[i]].push_back(i);
    }

    int upto = -1;

    string res(n, 'x');

    while(pos.size() > 1){
        size_t mn = 1e9;
        for(auto &P: pos)
            mn = min(mn, P.second.size());

        for(auto it{pos.begin()}; it != pos.end(); ++it){
            char nxt = (next(it) != pos.end()? next(it) -> first: pos.begin() -> first);
            for(int j{upto + 1}; j < mn; ++j){
                res[pos[it -> first][j]] = nxt;
            }
        }

        upto = mn;
        for(auto it{pos.begin()}; it != pos.end();){
            if(mn == it -> second.size())
                it = pos.erase(it);
            else
                ++it;
        }
    }
    for(int i{}; i < n; ++i){
        if(res[i] == 'x')
            res[i] = s[i];
    }
    cout << res << '\n';
}
signed main(){  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);

    int t;
    cin>>t;
    for(int _case{1}; _case <= t; ++_case){
        solve(_case);
    }

    return 0;
}

Link to Problem

I sincerely need help, I've tried everything to not get a TLE.

problem

my solution

Thanks in advance