Balaji's Blind Guess

Idea & Solution : Balaji_31

Prepared By : knishanthreddy

Required Knowledge : Basic Math

Time Complexity : $\mathcal{O}(N)$

Editorialist : Balaji_31

Approach

The core of this problem relies on counting the frequencies of each digit in Balaji's guess and comparing them to the fixed frequencies of a valid Supreme Sequence.

Let $n = \text{length}(s) / 3$. In a valid password, the digits $0$, $1$, and $2$ each appear exactly $n$ times. Let $c_0, c_1$, and $c_2$ be the actual counts of $0$, $1$, and $2$ in Balaji's guess string $s$.

Best Case (Maximum Matches):

To maximize matches, pair up identical digits. For any digit, the most you can successfully match is bounded by its frequency in the guess ($c$) or its fixed frequency in the password ($n$).

Formula: $\min(c_0, n) + \min(c_1, n) + \min(c_2, n)$

Worst Case (Minimum Matches):

To minimize matches, place the password's digits in non-matching spots. For any digit, there are $2n$ spots where it won't match the guess. A match is only "forced" if a digit's count in $s$ exceeds those $2n$ safe spots.

Formula: $\max(0, c_0 - 2n) + \max(0, c_1 - 2n) + \max(0, c_2 - 2n)$

Setter's Code

// Author:J.Balaji

#include<bits/stdc++.h>
#define ll          long long
#define pb          push_back
#define pob         pop_back
#define ye          cout << "YES\n"
#define no          cout << "NO\n"
#define fr(i,a,b)   for(int i=a;i<b;i++)
#define rfr(i,a,b)  for(int i=a;i>=b;i--)
#define trav(i,a)   for(auto &i : a)
#define frin        fr(i,0,n)
#define fi          first
#define se          second
#define vi          vector < int >
#define vli         vector <long long int >
#define vc          vector < char >
#define vpi         vector < pair < int, int >>
#define pi          pair < int, int >
#define mi          map < int, int >
#define mli         map < ll , ll >
#define mlc         map<char,int>
#define miv         map < int, vector < int >>
#define mae(v)      * max_element(v.begin(), v.end())
#define mie(v)      * min_element(v.begin(), v.end())
#define sv(v)       sort(v.begin(), v.end())
#define rsv(v)      sort(v.rbegin(), v.rend())
#define rv(v)       reverse(v.begin(), v.end())
#define vs(v)       accumulate(v.begin(), v.end(), 0)
#define vls(v)      accumulate(v.begin(),v.end(),(ll)0)
#define take(v,n)   for(int j=0;j<n;j++) cin>>v[j];
#define give(v,n)   for(int j=0;j<n;j++) cout<<v[j]<<' ';
#define lb          lower_bound
#define ub          upper_bound
#define bpc(x)      __builtin_popcountll(x) 
#define btz(x)      __builtin_ctzll(x)

const int MOD = 1e9 + 7;
const int inf = LLONG_MAX;
const int minf = LLONG_MIN;
using namespace std;

void solved(){
    int n;
    cin>>n;
    string s;
    cin>>s;
    int a=0,b=0,c=0;
    trav(x,s) {
        if(x=='0') a++;
        else if(x=='1') b++;
        else c++;
    }
    int mn=max(0,a-2*n)+max(0,b-2*n)+max(0,c-2*n);
    int mx=min(a,n)+min(b,n)+min(c,n);
    cout<<mn<<" "<<mx<<"\n";
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t = 1;
    cin >> t;
    while (t--)
    {
        solved();
    }
}

Tester's Code

import sys 

input = sys.stdin.readline

def solve():
    n = int(input())
    s = input().strip()
    
    mp = {}
    for ch in s:
        mp[ch] = mp.get(ch, 0) + 1
    
    maxi = 3 * n
    mini = 0
    
    for v in mp.values():
        if v > n:
            maxi -= (v - n)
        if v > 2 * n:
            mini += (v - 2 * n)
    
    print(mini, maxi)

t = int(input())
for _ in range(t):
    solve()