#include <bits/stdc++.h>
using namespace std;

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n, k;
        cin >> n >> k;

        string s;
        cin >> s;

        int ans = 0;
        for (int i = 0; i < n / k; i++) {
            bool has_non_nhoj_farm = false;
            for (int j = i * k; j < (i + 1) * k; j++) {
                if (s[j] == '0') has_non_nhoj_farm = true;
            }
            ans += !has_non_nhoj_farm;
        }

        cout << ans << "\n";
    }
}

Too hard

A bit on the harder side

Good difficulty

Easy

Too easy

Amazing

Good

So-so

Bad

Awful

When comparing two numbers that are initially not equal, the only way they can become equal after some number of operations is if at least one of them has an operation performed on it when it is $$$ \lt 2$$$.

If two elements are equal at some point, they'll be equal no matter how many more operations are performed. Therefore, it suffices to look at the end behavior of each element.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        
        vector<int> vec(n); for (auto &x: vec) cin >> x;
        
        int mod_4[] {0, 0, 0, 0};
        for (auto &x: vec) mod_4[x%4]++;
        cout << max({mod_4[0], mod_4[2], mod_4[1] + mod_4[3]}) << "\n";
    }
}

Too hard

A bit on the harder side

Good difficulty

Easy

Too easy

Amazing

Good

So-so

Bad

Awful

If a $$$-1$$$ is in between two $$$1$$$s, it would only hurt the answer to make it a $$$1$$$.

If a $$$-1$$$ is not in between two $$$1$$$ s, the $$$-1$$$ would only be included in a subarray satisfying the conditions if it was an endpoint.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
    
    while (t--) {
        int n;
        cin >> n;
        
        vector<int> vec(n); for (auto &x: vec) cin >> x;
        
        for (int i = 0; i < n; i++) {
            if (vec[i] == -1) vec[i] = 1;
            if (vec[i] == 1) break;
        }
        
        for (int i = n-1; i >= 0; i--) {
            if (vec[i] == -1) vec[i] = 1;
            if (vec[i] == 1) break;
        }
        
        
        for (auto &x: vec) cout << max(x, 0) << " ";
        cout << "\n";
    }
}

Too hard

A bit on the harder side

Good difficulty

Easy

Too easy

Amazing

Good

So-so

Bad

Awful

If there is only one $$$0$$$ in the array, then exactly one set will have a mex greater than zero

$$$MEX(A) = MEX(B), MEX(C) = 0$$$ satisfies the constraints.

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    int t;
    cin >> t;
 
    while (t--) {
        int n;
        cin >> n;
 
        vector<int> vec(n); for (auto &x: vec) cin >> x;
        if (count(vec.begin(), vec.end(), 0) == 1) {
            cout << "NO\n";
            continue;
        }
        cout << "YES\n";
        bool seen_zero = false;
        for (int i = 0; i < n; i++) {
            if (vec[i] != 0) cout << 'A';
            else if (seen_zero) cout << 'B';
            else {
                seen_zero = true;
                cout << 'C';
            }
        }
        cout << "\n";
    }
}

Too hard

A bit on the harder side

Good difficulty

Easy

Too easy

Amazing

Good

So-so

Bad

Awful

If an element $$$x$$$ at index $$$i$$$ is not equal to $$$-1$$$, there must be a treasure at either island $$$i + x$$$ or $$$i - x$$$

If an element $$$x$$$ at index $$$i$$$ is not equal to $$$-1$$$, there must no treasures in the exclusive range of indices ($$$i + x$$$, $$$i - x$$$)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
int main() {
    int t;
    cin >> t;
 
 
    while (t--) {
        int n;
        cin >> n;
 
        vector<int> vec(n); for (auto &x: vec) cin >> x;
 
        vector<int> diff(n+1);
        for (int i = 0; i < n; i++) {
            if (vec[i] > 0) {
                diff[max(0, i-vec[i]+1)]++; 
                diff[min(n, i+vec[i])]--; 
            }
        }
        vector<bool> restricted(n);
        int curr_count = 0;
        for (int i = 0; i < n; i++) {
            curr_count += diff[i];
            restricted[i] = curr_count > 0;
        }
        bool possible = true;
        for (int i = 0; i < n && possible; i++) {
            if (vec[i] >= 0) {
                if (i - vec[i] >= 0 && !restricted[i - vec[i]]) continue;
                if (i + vec[i] < n && !restricted[i + vec[i]]) continue;
                possible = false;
            }
        }
 
        if (!possible) cout << -1 << "\n";
        else {
            for (auto x: restricted) cout << !x;
            cout << "\n";
        } 
    }
}

Too hard

A bit on the harder side

Good difficulty

Easy

Too easy

Amazing

Good

So-so

Bad

Awful

Look at performing some bubbles and reverse bubbles on small arrays. How many elements are moved?

A bubble will result is the leftmost 1 being moved all the way to the right. Similarly, a reverse bubble will result in the rightmost 0 being moved all the way to the left.

Since prefix zeroes and suffix ones don't matter, if we continuously remove them, then a bubble removes the last element of the array and a reverse bubble removes the first element of the array. Is there a way to remove the first and last elements of an array in constant time?

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
int main() {
    int t;
    cin >> t;
 
    while (t--) {
        int n;
        cin >> n;
 
        vector<int> vec(n); for (auto &x: vec) cin >> x;
        string s;
        cin >> s;
 
        ll inversions = 0;
        int cnt_ones = 0;
        for (int i = 0; i < n; i++) {
            cnt_ones += vec[i];
            if (vec[i] == 0) inversions += cnt_ones;
        }
        cout << inversions << " ";
        
        deque<int> dq;
        for (auto &x: vec) dq.push_back(x);
        int cnt_zeroes = count(vec.begin(), vec.end(), 0);
        for (int i = 0; i < n; i++) {
            while (dq.size() > 0 && dq.front() == 0) {
                dq.pop_front();
                cnt_zeroes--;
            }
            while (dq.size() > 0 && dq.back() == 1) dq.pop_back();
            if (dq.size() == 0) {
                cout << 0 << " ";
                continue;
            }
            if (s[i] == '0') {
                inversions -= (dq.size() - cnt_zeroes);
                dq.pop_back();
                cnt_zeroes--;
            }
            else {
                inversions -= cnt_zeroes;
                dq.pop_front();
            }
            cout << inversions << " ";
        }
        cout << "\n";
    }
}

Too hard

A bit on the harder side

Good difficulty

Easy

Too easy

Amazing

Good

So-so

Bad

Awful

Ignoring indexes 1 and $$$n$$$, if we remove index $$$i$$$, if we perform an operation on index $$$j$$$, all elements between $$$[i, j]$$$ will also have an operation performed on them.

If we remove index $$$i$$$, and we have to reduce the element at index $$$i+1$$$, $$$i+2$$$, etc, what will we subtract it to?

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
int main() {
    int t;
    cin >> t;
 
    while (t--) {
        ll n, k;
        cin >> n >> k;
 
        vector<ll> vec(n); for (auto &x: vec) cin >> x;
        vector<ll> vec_2(n); for (int i = 0; i < n; i++) vec_2[i] = vec[i] - i * k;
 
        vector<ll> prefix(n); prefix[0] = vec[0];
        for (int i = 1; i < n; i++) prefix[i] = prefix[i-1] + vec[i];
 
        vector<ll> ans(n);
        for (int i = 1; i < n-1; i++) {
            int lo = i+1;
            int hi = n-1;
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                if (vec_2[mid] <= (vec[i-1] - i*k)) hi = mid - 1;
                else lo = mid + 1;
            }
            
            ll num_needed = (lo - i - 1);
            ans[i] = (prefix[num_needed + i] - prefix[i]) - (k * (num_needed * (num_needed + 1))/2) - vec[i-1] * num_needed;
        }
        for (auto &x: ans) cout << x << " ";
        cout << "\n";
    }
}

Too hard

A bit on the harder side

Good difficulty

Easy

Too easy

Amazing

Good

So-so

Bad

Awful

Let's consider all locations that we have not restricted: we can separate them into 3 categories: the position is forced to be a treasure, the position has no undestroyed that depend on it, and all other positions.

The islands that are considered "non-restricted" form a chain of locations, with each non-restricted chain having a treasure between them. What must be true of the locations in this chain such that no condition is violated?

For every pair of adjacent locations, there must be at least one treasure at one of those locations.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
 
const ll MOD = 1000000007;
const int MAX_N = 200055;
int main() {
    int t;
    cin >> t;
 
 
    vector<ll> fibo(MAX_N);
    fibo[1] = 1;
    fibo[2] = 1;
    for (int i = 3; i < MAX_N; i++) {
        fibo[i] = (fibo[i-1] + fibo[i-2]) % MOD;
    }
 
    while (t--) {
        int n;
        cin >> n;
 
        vector<int> vec(n); for (auto &x: vec) cin >> x;
 
        vector<int> diff(n+1);
        for (int i = 0; i < n; i++) {
            if (vec[i] > 0) {
                diff[max(0, i-vec[i]+1)]++; 
                diff[min(n, i+vec[i])]--; 
            }
        }
        
        vector<bool> restricted(n);
        vector<bool> forced(n);
        vector<int> non_required;
        int curr_count = 0;
        for (int i = 0; i < n; i++) {
            curr_count += diff[i];
            restricted[i] = curr_count > 0;
        }
 
        bool possible = true;
        for (int i = 0; i < n; i++) {
            if (vec[i] != -1) {
                int cnt = 0;
                cnt += (i - vec[i] >= 0 && !restricted[i - vec[i]]); 
                cnt += (i + vec[i] < n && !restricted[i + vec[i]]);
                if (cnt == 0) { possible = false;}
                if (cnt == 1 || vec[i] == 0) {
                    if (i + vec[i] < n) forced[i + vec[i]] = true;
                    if (i - vec[i] >= 0) forced[i - vec[i]] = true;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (!restricted[i] && !forced[i]) non_required.push_back(i);
        }
        if (!possible) {
            cout << 0 << "\n";
            continue;
        }
 
        ll total = 1;
        int chain_len = 1;
        for (int i = 0; i < non_required.size(); i++) {
            bool cond1 = i == non_required.size() - 1 || vec[(non_required[i] + non_required[i+1])/2] == (non_required[i+1] - non_required[i])/2;
            bool cond2 = i == non_required.size() - 1 || (non_required[i+1] - non_required[i]) % 2 == 0;
            //if (i != 1) cout << (non_required[i+1] - non_required[i]) << "\n";
            if (i == non_required.size() - 1 || !cond1 || !cond2) {
                //cout << chain_len << "\n";
                total *= fibo[chain_len+2];
                total %= MOD;
                chain_len = 1;
            }
            else chain_len++;
        }
        if (count(vec.begin(), vec.end(), -1) == n) {
            total = (total + MOD - 1) % MOD;
        }
        cout << total << "\n";
    }
}

Too hard

A bit on the harder side

Good difficulty

Easy

Too easy

Amazing

Good

So-so

Bad

Awful