Qıfıl və Açar Ardıcıllığı#12236
Daxil ol

Qıfıl və Açar Ardıcıllığı (Həll təhlili)

Məsələ müəllifi:

Imran AKKI

Hazırlayan:

Imran AKKI

Redaktə edən:

Hasan Saleh (MathModel)

Həll Bizə iki bərabər son nöqtə və onların arasında müxtəlif simvol lazımdır. Başqa sözlə: l < r tapmaq lazımdır ki, s_l = s_r olsun və alt-sətir s[l+1;r-1]=s_{l+1}s_{l+2}...s_{r-1} ən azı fərqli hərf saxlasın. Bu şərti ödəyənlər arasında r-l+1 minimal olanı qaytarırıq.

Diqqət edin ki, sabit sol son nöqtə və sabit simvol c = s_l üçün, sağa doğru hərəkət etdikcə (l,r) daxilindəki fərqli hərflərin sayı azalmır. Bu monotoniya bizə hər üçün ikili axtarışdan istifadə etməyə imkan verir.

Hər bir hərfin tezliyini ilə prefix tezlik massivləri vasitəsilə hesablamaq mümkündür. Sonra hər bir hərfi üçün ki, ən azı iki dəfə çıxır:

  1. Hər çıxış indeksi üçün (sol çıxış), daha sonrakı çıxışlar arasında ikili axtarış edirik və ən kiçik tapırıq ki, s[i+1;r-1] müxtəlif hərf saxlasın.

  2. Prefix massivləri ilə həmin alt-sətrdə fərqli hərflərin sayını yoxlayırıq.

  3. Minimal uzunluğu r-i+1 və uyğun indeksləri izləyirik.

// Müəllif: Imran AKKI (imranakki)
#include <bits/stdc++.h>
#define ll long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define lp(i, a, n) for (ll i = a; i < n; i++)
#define MAXN 1000005
#define MOD (ll)(1e9 + 7)
using namespace std;

void solve()
{
    ll n, k; cin >> n >> k;
    string s; cin >> s;

    // 1-dən başlayan indeksləmə
    vector<vector<ll>> pre(26, vector<ll>(n + 2, 0));
    for(ll d = 0; d < 26; d++) {
        for(ll i = 0; i < n; i++) {
            pre[d][i + 1] = pre[d][i] + ((s[i] - 'a') == d);
        }
    }

    vector<ll> pos[26];
    for(ll i = 0; i < n; i++){
        pos[s[i] - 'a'].push_back(i);
    }

    auto can = [&](ll i, ll l) {
        if(l - i < k + 1) return false;
        ll distinct = 0;
        for(ll d = 0; d < 26; d++) {
            if(pre[d][l] - pre[d][i + 1] > 0) {
                distinct++;
                if(distinct >= k){
                    return true;
                }
            }
        }
        return false;
    };
    ll bestLen = INT_MAX;
    ll bestI = -1, bestJ = -1;
    for(ll c = 0; c < 26; c++) {
        auto &P = pos[c];
        ll m = P.size();
        if(m < 2) continue;

        for(ll x = 0; x < m - 1; x++) {
            ll i = P[x];
            ll l = x + 1, r = m - 1;
            ll best = -1;
            while(l <= r) {
                ll mid = (l + r) >> 1;
                if(can(i, P[mid])) {
                    best = mid;
                    r = mid - 1;
                }else {
                    l = mid + 1;
                }
            }
            if(best != -1  && can(i, P[best]) && P[best] - i + 1 < bestLen) {
                bestLen = min(bestLen, P[best] - i + 1);
                bestI = i;
                bestJ = P[best];
            }
        }
    }

    if(bestI != -1) {
        cout << "YES\n";
        cout << bestI + 1 << " " << bestJ + 1 << "\n";
    } else {
        cout << "NO\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t; cin >> t;
    while(t--) solve();
    return 0;
}
C++

Mürəkkəblik : \mathcal{O}(n \cdot 26 \cdot \log n)