Hey,

In this blog, I will explain my own method on how to solve this problem from this contest.

So what I did in my code was I checked two cases, 1. Maximum, 2. Minimum. In case 1, I checked that If s[i-1] & s[i+1] are equal to '1'. If they were, I made s[i] = '1'. And after the loop, I made a var called maximum which had the count of 1's in the modified string.

In case 2, I checked if s[i-1] and s[i+1] are equal to '1'. If they were, I made s[i] = '0'. Now after the loop, I made a var called minimum which had the count of '1' in the string modified in the loop. Now at the end I printed Minimum and maximum.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
int main() {
    int t;
    cin >> t;
    while(t--) {
        int n;
        string s;
        cin >> n >> s;
        for(int i=0;i<n;i++) {
            if(s[i-1]=='1' && s[i+1]=='1') {
                s[i]='1';
            }
        }
        int maxi= count(s.begin(), s.end(), '1');
 
        for(int i=0;i<n;i++) {
            if(s[i-1]=='1' && s[i+1]=='1') {
                s[i]='0';
            }
        }
        int mini= count(s.begin(), s.end(), '1');
 
        cout << mini << " " << maxi << endl;
    }
  return 0;
}

No one still answered my question.. "why wasn't it a dijkstra?"

Hope the blog helped