SETSK - Editorial

editorial
, ,
1

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4

Author: raysh07
Tester: iceknight1093
Editorialist: iceknight1093

DIFFICULTY:

Simple

PREREQUISITES:

None

PROBLEM:

For a permutation P and an integer K, define f(P, K) as follows:

  • Let S be a set that’s initially empty.
  • For each i = 1, 2, 3, \ldots, N,
    • If there exists an element x\in S such that |x-P_i| \le K, do not change S.
    • Otherwise, insert P_i into S.

You’re given K and the final set S, as a boolean array B.
Does there exist a permutation P of length N such that f(P, K) = S?

EXPLANATION:

An element P_i is not inserted to the set S if it already contains some existing element x that has a difference of at most K from P_i.
In particular, this means that S can never contain two elements whose difference is \le K, because after inserting one of them the other one can’t be inserted.

Thus, if there exist two indices i and j such that:

  • 1 \le i < j \le N,
  • |i-j| \le K, and
  • B_i = B_j = 1

Then the answer is certainly No because it’s impossible to have both i and j in the set.

This can easily be checked in \mathcal{O}(N^2) time.

Next, let’s look at the elements that are not present in S.

Suppose we have B_i = 0 for some i.
This means that whenever the element i is processed, there must exist some element belonging to the set which is at most K away from it.

So, certainly there must exist some j such that i-K \le j \le i+K and B_j = 1.
That is, some element in the range [i-K, i+K] must belong to the set, so that it can deny i itself being added to the set.

If this check fails for any i that has B_i = 0, then again the answer is No.

This is also easy to check in \mathcal{O}(N^2) time - just run a brute-force loop for each i.

We’ve derived two conditions that are necessary:

  1. For any pair of indices (i, j) such that B_i = B_j = 1, we must have |i - j| \ge K.
  2. For any index i such that B_i = 0, there must be some j in the range [i-K, i+K] such that B_j = 1.

These two conditions are also sufficient for the answer to be Yes.
This is simple to prove via construction: consider the permutation where we first take all indices i such that B_i = 1, and then all indices i such that B_i = 0.
The above conditions guarantee that this construction will result in the desired f(P, K).

It’s possible to perform the checks in \mathcal{O}(N) time if you wish to try.
However, \mathcal{O}(N^2) is perfectly fine for the problem’s constraints.

TIME COMPLEXITY:

\mathcal{O}(N^2) or \mathcal{O}(N) per testcase.

CODE:

Editorialist's code (C++) 
// #include <bits/allocator.h>
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include "bits/stdc++.h"
using namespace std;
using ll = long long int;
mt19937_64 RNG(chrono::high_resolution_clock::now().time_since_epoch().count());

int main()
{
    ios::sync_with_stdio(false); cin.tie(0);
    
    int t; cin >> t;
    while (t--) {
        int n, k; cin >> n >> k;
        vector b(n, 0);
        for (int &x : b) cin >> x;

        string ans = "Yes";
        for (int i = 0; i < n; ++i) {
            if (b[i] == 0) {
                bool found = false;
                for (int j = 1; j <= k; ++j) {
                    if (i+j < n and b[i+j] == 1) found = true;
                    if (i-j >= 0 and b[i-j] == 1) found = true;
                }
                if (!found) ans = "No";
            }
            else {
                for (int j = 1; j <= k; ++j) {
                    if (i-j >= 0 and b[i-j] == 1) ans = "No";
                }
            }
        }
        cout << ans << '\n';
    }
}