# XRSTR - EDITORIAL

Contest

Practice

Author: Rohit Tawde

Tester: Gaurish Baliga

Editorialist: Rohit Tawde

EASY-MEDIUM

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