XRSTR - EDITORIAL

PROBLEM LINK:

Contest

Practice

Author: Rohit Tawde

Tester: Gaurish Baliga

Editorialist: Rohit Tawde


DIFFICULTY:

EASY-MEDIUM


PREREQUISITES:

Math.


PROBLEM:

Can there be a binary string of size N, containing M number of 1's such that every substring of size K has an odd number of 1's?


EXPLANATION:

Claim: \forall_{i = 1}^{N-K} a_i = a_{i+k}.

Proof: For every pair of consecutive of consecutive substrings of size k (first one starting from a_i), the elements form a_{i+1} to a_{i+k-1} are common. Therefore, the XOR of both the substrings can only be same when a_i = a_{i+k}.

Following this pattern, the whole string can be partitioned into \lfloor \frac{N}{K} \rfloor identical substrings of size K and 1 substring of size N\%K.

Let there be X number of 1's in the first partition (of size \lfloor \frac{N}{K} \rfloor) and Y number of 1's in the last partition (of size N\%K).

We get, M = (X*\lfloor \frac{N}{K} \rfloor) +Y.

\therefore Y = (X*\lfloor \frac{N}{K} \rfloor) - M.

We know that, 0 \leq Y \leq (N\%K). Also, even this partial partition will follow the same repeating pattern.

Therefore, we will get Y_{min} when we fill the first partition such that all the 0's are present before all the 1's.

\therefore Y_{min} = max[0,\space K - N + (N\%K)]

Similarly, to get Y_{max} we will keep all the 1's before all the 0's.

\therefore Y_{max} = min[X,\space (N\%K)]

Now we have to just find if there exists an odd X such that 1 \leq X \leq K and Y_{min} \leq M-(X*\lfloor \frac{N}{K} \rfloor) \leq Y_{max}.


TIME COMPLEXITY:

O(K) per test case.


SOLUTIONS:

Setter's Solution

#include<bits/stdc++.h>

#define ll long long

#define pb push_back

#define F first

#define S second

#define fast_io ios_base::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)

using namespace std;

int main() {

    fast_io;

    int t;

    cin>>t;

    while(t--){

        ll n,m,k;

        cin>>n>>m>>k;

        ll ans=0;

        ll f=0;

        for(int i =1;i<=k;i+=2){

            ll tm=n/k;

            if(m>=tm*i+max(0ll, i-k+n%k) && m<=tm*i+min(n%k, (ll)i))f=1;

        }

        if(f){

            cout<<"YES\n";

        }

        else{

            cout<<"NO\n";

        }

    }

    return 0;

}

Tester's Solution
1 Like