Codeforces Diverse Garland

help
1

Problem link: Problem - 1108D - Codeforces

I’m trying to solve this problem with dp. I think my states and transitions are correct. Basically I’m doing dp[n][3] - minimum number of moves for the i-th character to be ARE, G, or B - 0, 1 and 2 respectively.

The issue I’m facing is that I need to print the changes I’ve made. Is there a way to do this without using a lot of if and else conditions?

Code:

#include <bits/stdc++.h>

#define FAST_IO ios_base::sync_with_stdio(false), cin.tie(nullptr)
#define FILE_IO freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
using namespace std;


signed main() {
    FAST_IO;
    FILE_IO;

    int n;
    string s;
    cin >> n >> s;
    int dp[n][3];
    map<char, int> code;
    code['R'] = 0, code['G'] = 1, code['B'] = 2;
    for (int i = 0; i < 3; i++) dp[0][i] = 1;
    dp[0][code[s[0]]] = 0;
    for (int i = 1; i < n; i++) {
        dp[i][0] = 1 + min(dp[i - 1][1], dp[i - 1][2]);
        dp[i][1] = 1 + min(dp[i - 1][0], dp[i - 1][2]);
        dp[i][2] = 1 + min(dp[i - 1][0], dp[i - 1][1]);
        dp[i][code[s[i]]]--;
    }
    cout << min({dp[n - 1][0], dp[n - 1][1], dp[n - 1][2]}) << "\n";
    return 0;
}
2

Go for greedy if s[i]==s[i-1] make s[i] diff from s[i-1] and s[i+1] ans++;
You can use map for those

3

I could go for greedy but I want to know if there is an easy way to reconstruct the answer from my dp array