VSTRING - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter:
Tester: Istvan Nagy
Editorialist: Taranpreet Singh

DIFFICULTY

Easy

PREREQUISITES

Just observation would do.

PROBLEM

Given a binary string S and an integer C, you are allowed to perform circular on S any number of times. Does there exist any rotation such that every pair of adjacent ones is separated by at most C zeros.

QUICK EXPLANATION

Assuming the last character to be adjacent to first, we can find the number of zeros between each pair of adjacent ones in a list. Now, the rotation of binary string is equivalent to deleting at most one element of this list. So if rest of the elements are up to C, then the answer is YES.

EXPLANATION

For this problem we’ll consider an example first. Assume S = 010001010. Now we shall consider all rotations of this string and compute the number of zeros between each adjacent pair of ones.

  • 010001010: The number of zeros between adjacent ones are \{3, 1\}
  • 001000101: The number of zeros between adjacent ones are \{3, 1\}
  • 100100010: The number of zeros between adjacent ones are \{2, 3\}
  • 010010001: The number of zeros between adjacent ones are \{2, 3\}
  • 101001000: The number of zeros between adjacent ones are \{1, 2\}
  • 010100100: The number of zeros between adjacent ones are \{1, 2\}
  • 001010010: The number of zeros between adjacent ones are \{1, 2\}
  • 000101001: The number of zeros between adjacent ones are \{1, 2\}
  • 100010100: The number of zeros between adjacent ones are \{3, 1\}

We can see that the list of number of zeros between adjacent ones changes only when some 1 moves from last position to first position. But why does that happen?

It’s because the last and second last occurrence of 1 is no longer adjacent, and additionally, last occurrence of one becomes the first occurrence now, so it is adjacent to second occurrence in rotated string, hence number of zeros between them are added.

Simple idea, Non-simple implementation

This way, we can actually maintain the queue type structure, and simulate the whole process, where queue supports the following operations

  • Add element at beginning
  • Remove element from end
  • Find maximum of elements in queue

In order to support last operation, there are various methods, like mentioned here or implementing queue using two stacks and using minimum stack approach.

Can we observe more?

Above approaches were correct, although require too much implementation for an easy problem like this, so let’s observe a bit more.

We saw that list of number of zeros between each pair of adjacent ones got affected only when some 1 moves from last to first. Let’s assume for a moment that last and first character of S are adjacent.

Considering S = 010001010, now the list of number of zeros between adjacent ones is \{3, 1, 2\}. It is easy to see that all rotations of S have this same list of number of zeros between adjacent ones.

Hence, rotation only affect the number of zeros between last and first occurrence of one, effectively removing it from the list.

So, we can see that if we compute the list of zeros between adjacent ones when S is assumed to be cyclic, we can delete any one element from the list. It can be seen that the new list after deletion shall correspond to a cyclic rotation of original string S.

Simpler solution, simpler life

So now we have the list of number of zeros between adjacent ones when S is assumed to be cyclic, we know we can delete exactly one element. And we want the remaining elements in list to be up to C. Hence, it is optimal to delete the largest element from the list and check if remaining elements are up to C or not.

It is equivalent to checking whether the second-maximum element of this list is up to C or not. This can all be done with much simpler implementation.

Genera Note: There are many such problems where easy idea leads to complicated implementation, but with some more insights, solutions can become a lot more simpler.

TIME COMPLEXITY

The time complexity is O(N) per test case.
The space complexity is O(N) per test case.

SOLUTIONS

Setter's Solution
#include<bits/stdc++.h>
using namespace std;
  
const int maxl = 1e6;

int main()
{   
    int t; cin >> t;
    int tl = 0;
    while(t--){
        int n, k; cin >> n >> k; assert(2 * n <= maxl);
        tl += n;
        string s; cin >> s;
        s += s;
        int len = 2 * n, p1 = len + 10, ptr = -1;
        string ans = "nO";
        for(int i = 0; i < len; i++){
            if(s[i] == '1'){
                if(i - p1 - 1 > k){
                    ptr = p1 + 1; 
                }
                p1 = i;
            }
            if(i - ptr == n){
                ans = "YeS"; break;
            }
        }
        cout << ans << endl;
    }
    assert(tl <= maxl);
} 
Tester's Solution
#include <iostream>
#include <cassert>
#include <vector>
#include <set>
#include <map>
#include <algorithm>
#include <random>
#include <limits>

#ifdef HOME
#define NOMINMAX   
#include <windows.h>
#endif

#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
#define forn(i, n) for (int i = 0; i < (int)(n); ++i)
#define for1(i, n) for (int i = 1; i <= (int)(n); ++i)
#define ford(i, n) for (int i = (int)(n) - 1; i >= 0; --i)
#define fore(i, a, b) for (int i = (int)(a); i <= (int)(b); ++i)

template<class T> bool umin(T& a, T b) { return a > b ? (a = b, true) : false; }
template<class T> bool umax(T& a, T b) { return a < b ? (a = b, true) : false; }

using namespace std;

long long readInt(long long l, long long r, char endd) {
    long long x = 0;
    int cnt = 0;
    int fi = -1;
    bool is_neg = false;
    while (true) {
	    char g = getchar();
	    if (g == '-') {
		    assert(fi == -1);
		    is_neg = true;
		    continue;
	    }
	    if ('0' <= g && g <= '9') {
		    x *= 10;
		    x += g - '0';
		    if (cnt == 0) {
			    fi = g - '0';
		    }
		    cnt++;
		    assert(fi != 0 || cnt == 1);
		    assert(fi != 0 || is_neg == false);

		    assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
	    }
	    else if (g == endd) {
		    assert(cnt > 0);
		    if (is_neg) {
			    x = -x;
		    }
		    assert(l <= x && x <= r);
		    return x;
	    }
	    else {
		    assert(false);
	    }
    }
}

string readString(int l, int r, char endd) {
    string ret = "";
    int cnt = 0;
    while (true) {
	    char g = getchar();
	    assert(g != -1);
	    if (g == endd) {
		    break;
	    }
	    // 		if(g == '\r')
	    // 			continue;

	    cnt++;
	    ret += g;
    }
    assert(l <= cnt && cnt <= r);
    return ret;
}
long long readIntSp(long long l, long long r) {
    return readInt(l, r, ' ');
}
long long readIntLn(long long l, long long r) {
    return readInt(l, r, '\n');
}
string readStringLn(int l, int r) {
    return readString(l, r, '\n');
}
string readStringSp(int l, int r) {
    return readString(l, r, ' ');
}

int main(int argc, char** argv)
{
#ifdef HOME
    if (IsDebuggerPresent())
    {
	    freopen("../VSTRING_0.in", "rb", stdin);
	    freopen("../out.txt", "wb", stdout);
    }
#endif
    int T;
    cin >> T;
    forn(tc, T)
    {
	    int N, C;
	    cin >> N >> C;
	    string S;
	    cin >> S;
	    vector<int> v;
	    int act = 0;
 		forn(i, S.size())
	    {
		    if (S[i] == '1')
		    {
			    v.push_back(act);
			    act = 0;
		    }
		    else
		    {
			    ++act;
		    }
	    }
	    if (act > 0)
	    {
		    if (v.empty())
			    v.push_back(act);
		    else
			    v[0] += act;
	    }
		    
	    sort(v.begin(), v.end());
	    v.pop_back();
	    if (v.empty() || v.back() <= C)
		    cout << "YES\n";
	    else
		    cout << "NO\n";
    }
    return 0;
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class VSTRING{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni(), C = ni();
        String S = n();
        if(S.indexOf('1') == -1){
            pn("YES");
            return;
        }
        int idx = S.indexOf('1');
        S = S.substring(idx) + S.substring(0, idx);
        ArrayList<Integer> list = new ArrayList<>();
        int cnt = 0;
        for(int i = 0; i< S.length(); i++){
            if(S.charAt(i) == '0')cnt++;
            else{
                list.add(cnt);
                cnt = 0;
            }
        }
        list.add(cnt);
        int count = 0;
        for(int x:list)if(x > C)count++;
        pn(count <= 1?"YES":"NO");
    }
    //SOLUTION END
    void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
    static boolean multipleTC = true;
    FastReader in;PrintWriter out;
    void run() throws Exception{
        in = new FastReader();
        out = new PrintWriter(System.out);
        //Solution Credits: Taranpreet Singh
        int T = (multipleTC)?ni():1;
        pre();for(int t = 1; t<= T; t++)solve(t);
        out.flush();
        out.close();
    }
    public static void main(String[] args) throws Exception{
        new VSTRING().run();
    }
    int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
    void p(Object o){out.print(o);}
    void pn(Object o){out.println(o);}
    void pni(Object o){out.println(o);out.flush();}
    String n()throws Exception{return in.next();}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(in.next());}
    long nl()throws Exception{return Long.parseLong(in.next());}
    double nd()throws Exception{return Double.parseDouble(in.next());}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        public FastReader(String s) throws Exception{
            br = new BufferedReader(new FileReader(s));
        }

        String next() throws Exception{
            while (st == null || !st.hasMoreElements()){
                try{
                    st = new StringTokenizer(br.readLine());
                }catch (IOException  e){
                    throw new Exception(e.toString());
                }
            }
            return st.nextToken();
        }

        String nextLine() throws Exception{
            String str = "";
            try{   
                str = br.readLine();
            }catch (IOException e){
                throw new Exception(e.toString());
            }  
            return str;
        }
    }
}

VIDEO EDITORIAL:

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

2 Likes

Hey, great editorial.
Could anyone help me figure out why this SOLUTION is giving WA in 1 TC?

Can anyone plz help me figuring out which corner case I am missing in m solution?
https://www.codechef.com/viewsolution/43262365

Actually, I approached it like this-
f and e are the variables to count the 0’s in the first and end position and with z I am counting zeroes between 2 1’s and storing min in ‘mi’. This means the minimum 0’s in between 1’s are stored in mi and by adding f and e and taking there minimum gives the overall minimum zeros we will get in any rotations and at the end checking if it is less than given C.

why is my solution which is similer giving wa in 2 tc?
Solution: 43264447 | CodeChef

I have implemented by using two consequent maximum as mentioned here. Someone please check why it is showing wrong answer after submission. :frowning:
Solution: 43267870 | CodeChef

#include
using namespace std;

int main() {
// your code goes here
int t;
cin>>t;
while(t–){
long long int n,c;
cin>>n>>c;
string str;
cin>>str;
long long int arr[n],j=0,count = 0;
for(long long int i=0;i<n;i++){
if(str[i]==‘1’){
arr[j++] =i;
}
}
/* for(long long int i=0;i<j;i++){
cout<< arr[i]<<endl;
}
cout<< j;/
for(long long int i=0;i<j-1;i++){
if(arr[i+1] - arr[i] > (c+1)){
count++;
}
}
/
cout<<"count "<<count<<endl;*/
if(count >=2){
cout<<“NO”<<endl;
}
else{
long long int m = ((n - 1)- arr[j-1] )+ arr[0];
if(m>c){
long long int p = ((n - 1)- arr[j-1] );
if(p>=0 and (count == 0)){
cout<<“YES”<<endl;
}else{
cout<<“NO”<<endl;}
}
else{
cout<<“YES”<<endl;
}

    }
}
return 0;

}

GETTING WA IN THE LAST TEST CASE. WHAT IS THE TEST CASE CAN IT IS FAILING?

Under the heading "Simple idea non-simple implementation" the third line ."Find max in the queue" , will give the largest gap that can be possible bewteen two adjacent ones in a possible rotation , but how can it help in determining if it possible for the string to generate a rotated string satisfying given condetions.PLEASE HELP.

if the largest gap can be broken into smaller sub-sequences where the difference btw them is less than K than the string will satisfy the condition ,
i.e. for ex : 1000101, and k = 2,
then we can do 1011000, and hence the 1’s at corners are not considered adjacent , this satisfies the condition…

simply, if the count of adjacent 1’s having distance btw them > K, is > 1, then the ans is not possible, because only one pair of adjacent 1’s can be put on the corners, in-order to make their distance invalid,
So, you can only make a string valid with the given conditions only when the number of adjacent 1’s with distance > k is strictly == 1, for

please explain me why i’m getting segmentation error in two of the sub tasks

    #include<bits/stdc++.h>

    using namespace std;

    int main(){

        int t;

        cin>>t;

        while(t--){

            int n,c;

            cin>>n>>c;

            string s;

            cin>>s;

            vector<int> oneIdx;

            for(int i=0;i<n;i++){

                if(s.at(i)=='1')

                oneIdx.push_back(i);

            }

            vector<int> zerosBtw;

            for(int i=1;i<oneIdx.size();i++){

                zerosBtw.push_back(oneIdx[i]-oneIdx[i-1]-1);

            }

            int cal = oneIdx[0]+(s.size()-oneIdx[oneIdx.size()-1]-1);

            zerosBtw.push_back(cal);

            int cnt=0;

            for(int i=0;i<zerosBtw.size();i++){

                if(zerosBtw[i]>c)

                cnt++;

            }

            if(cnt<=1)

            cout<<"YES"<<endl;

            else

            cout<<"NO"<<endl;

        }

    }
1 Like

Can anyone help me in this , these are the two solution links , the difference is only that when i am iterating the positions vector , in one solution i wrote i<size-1 and in the other i+1<size , why does the first one give run time error ?
first solution Solution: 43299399 | CodeChef
second solution Solution: 43299434 | CodeChef
the difference is only in the line 17 of both the codes .
Thank you

Time Complexity O(n)
Space Complexity O(1)

Intuition: we only need to check if while iterating the string circularly there are more than one counts of subarrays of zeros with more than C zeroes. if count > 1 then NO else YES.

Example:
100100010 c = 2 here we have only one subarray with more than c = 2 zeroes hence this can be rotated to 101001000

1000100010 c = 2 here we have two subarrays with more than c = 2 zeroes hence this can not be rotated to 1010001000 since it will still have a subarray of zeroes with number of zeroes > c.

https://www.codechef.com/viewsolution/44746916
can anyone tell me whats wrong in solution