BNSONSTR - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Prasant Kumar
Tester & Editorialist: Taranpreet Singh

DIFFICULTY

Easy

PREREQUISITES

None

PROBLEM

Given a circular binary string s of length N, where you can perform operations on this string, flipping character from ‘0’ to ‘1’ and vice versa.

Determine the minimum number of operations needed to obtain a good string, where a circular string is good when it contains at least one occurrence of ‘1’ and for each ‘1’, distance to next ‘1’ is the same.

QUICK EXPLANATION

  • The distance between '1’s can only be a factor of N.Try all factors of N as distance.
  • For each factor, try all possible start points. i.e. For distance d, there are d positions where ‘1’ should appear, and the rest string should be filled with zeros.
  • Find minimum Hamming distance of given string to any of the valid strings found above.

EXPLANATION

Valid distance between '1’s

Let’s define the distance between two positiions i and j in 0-based indexing as j-i if i \leq j and j+N-i otherwise. Denoting distance by d(i, j).

Let’s suppose, we have a good string with k occurrences of 1s, and the distance between each ‘1’ from the next one is d. Assuming the positions of ones are p_1, p_2 \ldots p_k, we have d(p_i, p_{i+1}) = d for all 1 \leq i < k and d(p_k, p_1) = d as well.

We can see that starting from p_1, moving to next p_i until reaching p_1 again, leads to visiting N positions exactly once. So, we can claim that d*k = N holds.

Claim: If a circular string of length N is good, then the distance between each ‘1’ and the next ‘1’ is a factor of N.

Hence, let us try all divisors d one by one, and compute the minimum number of operations needed to convert s into a good string with distance d between ones.

All good string s with distance d

Let’s suppose we fix the distance between each ‘1’ and the next as d where d is a factor of N.
The circular binary string would look like ‘1’ followed by d-1 ‘0’, then ‘1’ followed by d-1 '0’s and so on, covering the whole string. For N = 6, d = 3, we get string 100100.

But there are string 010010 and string 001001 as well with d = 3.

We need to fix the position of the first occurrence f of ‘1’ in the string, as the first occurrence, as f and d defines the whole good circular string uniquely.

Pair (f, d) represent a string with each ‘1’ having distance d from the next one, and position f contains ‘1’. We can see that for each position p, it contains ‘1’ if and only if p \bmod d = f, and ‘0’ otherwise.

Computing minimum Hamming distance to good string

Let’s try pair (f, d), representing string T, and try to compute its hamming distance from given string s. We know that T contains exactly N/d ones, and the rest zeros, so let’s iterate on those positions. Let’s make a set A denoting the set of positions of '1’s in T.

We need to count the number of positions p in set A such that s_p = ‘0’, and number of positions not in A such that s_p = ‘1’, as the sum of these values would be the hamming distance.

Let c denote the number of ones in whole string s, and x denote the number of ones in positions in set p present in set A such that s_p = ‘1’. We can see that The hamming distance is (N/d - x) + (c-x) \implies N/d + c - 2*x.

In case you missed

N/d -x is the number of positions where T contains ‘1’, but s contains ‘0’, and (c-x) denote the number of positions where T contains ‘0’ but s contains ‘1’

We can compute c beforehand, and compute x, the number of ones at positions p such that p \bmod d = f, in time O(N/d) time by following loop.

x = 0
for(int p = f; p < N; p += d)
    if(s[p] == '1')
        x++

Hence, we shall try all valid pairs (f, d) one by one, compute Hamming distance from string s, and print minimum.

Time complexity analysis

For a fixed distance d, let’s consider all start points f. There are exactly d unique choices for f, and computing each one takes N/d iterations, leading to total N iterations.

Hence, for each factor d of N, we need O(N) time, leading to time complexity O(N*\sigma(N)), where \sigma(N) is the divisor function.

TIME COMPLEXITY

The time complexity is O(N*\sigma(N)) per test case.

SOLUTIONS

Setter's Solution
#include<bits/stdc++.h>
using namespace std;

signed main(){
//	freopen("input.txt", "r", stdin);
    int t;cin>>t;
    while(t--){
	    int n;cin>>n;
	    string s;cin>>s;
	    int sum=0;
	    for(int i=0;i<n;i++){
		    sum+=s[i]-'0';
	    }
	    int ans=n;
	    
	    for(int x=1;x<=n;x++){
		    if(n%x)continue;
			    
		    for(int j=0;j<x;j++){
			    int temp=0;
			    for(int k=j;k<n;k+=x){
				    if(s[k]=='1'){
					    temp-=1;
				    }else temp+=1;
			    }
			    ans=min(ans,sum+temp);
		    }			
		    
	    }
	    cout<<ans<<endl;
    }


    return 0;
}
Tester's Solution
import java.util.*;
import java.io.*;
class BinaryStringOnSteroid{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni();
        char[] C = n().toCharArray();
        int count = 0;
        for(int i = 0; i< N; i++)count += C[i]-'0';
        int ans = N;
        for(int d = 1; d <= N; d++){
            if(N%d != 0)continue;
            for(int st = 0; st < d; st++){
                int cur = 0;
                for(int j = st; j< N; j += d)
                    cur += C[j]-'0';
                int op = N/d+count-2*cur;
                ans = Math.min(ans, op);
            }
        }
        pn(ans);
    }
    //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 BinaryStringOnSteroid().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;
        }
    }
}

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

7 Likes

Don’t know what was happening, I was constantly write this solution only,
but
https://www.codechef.com/viewsolution/48004425
was not passing
but when I wrote it just in different way to optimize the space, it passed (in much less time 0.12s, after removing pragmas also it passed in 0.16s)
https://www.codechef.com/viewsolution/48008019
PS: I think the codechef was giving wrong verdict, it should be MLE. Again, I got caught in this.

2 Likes

Can we do it with binary search, since d can be between 1 and N, hence we can check if a D is possible then that will give min changes , so overall se can minimise D ( we can store for a possible D its changes reqd and will find it will be min for min D). Time Complexity - O(Nlogn)

input:
1
6
110010
Received Output:
3
Desired output:
1

I used Factorial method:
https://www.codechef.com/viewsolution/48018698
Can someone please help getting WA!

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

//https://www.geeksforgeeks.org/find-divisors-natural-number-set-1/
void printDivisors(long long int n, vector<long long int>& v)
{
    for (int i=1; i<=(n); i++)
    {
        if (n%i == 0)
        {
                v.push_back(i);
        }
    }
}

    string shiftall0s(string s)
    {
        std::size_t found = s.find('1');
        if (found==std::string::npos)
        return s;
        
        string r = s.substr(found);
        while(r.length()<s.length())
        r+='0';
        
        return r;
    }

int main() {
    
	int t;
	cin>>t;
	
	while(t--)
	{
	    long long int n;
	    cin>>n;
        
        string s;
        cin>>s;
        
        vector<long long int> factors;
        printDivisors(n, factors);
        
        string str = shiftall0s(s);

        vector<long long int> pos;
        for (int i=0;i<str.length();i++)
        {
            if(str[i]=='1')
            pos.push_back(i);
        }
        
        
        long long int min_diff=INT64_MAX;
        
        for (int i=0;i<factors.size() && pos.size()>0;i++)
        {
            long long int good_pos=0;
            long long int bad_pos=0;
            for (int j=0;j<pos.size();j++)
            {
                if(pos[j]%factors[i]==0)
                {
                    good_pos++;
                }
                else
                {
                    bad_pos++;
                }
                
                if(bad_pos>min_diff)
                break;
            }
            
            long long int bad=((str.length()/factors[i]) - good_pos) + bad_pos;
            min_diff = min(min_diff, bad);
            
            if(min_diff==0)
            break;
        }
	    
	    if(pos.size()==0)
	    cout<<1<<endl;
	    else
	    cout<<min_diff<<endl;
	}
	
	return 0;
}

Why am I getting TLE.
I’m pretty sure my logic is exactly the same as the editorial.
PLEASE…! could someone look into it ?
I am linking one of my submissions,
https://www.codechef.com/viewsolution/48018944

I have even tested them on my pc with 100 test case with strings of length 5000 each .
And it runs within half a second.
@taran_1407 ??

1 Like

spot the difference @jdvoid_44

Thanks for the reply,
but just noticed that using int gives AC while longlong gives TLE.
WHY?
And why does it work within time limit on my pc and not on codechef servers?

using long long treats leads to every number being treated as a 64 bit number which slows down computation and also consumes a lot of memory leading to an MLE or TLE. And looking at your template it seems like you have blind faith in this little demon. I recommend you to change your template.

2 Likes

Thanks, will do that.
but still it doesn’t explain why it works on my machine and not on the server, which should handle computations easily compared to ordinary laptops.

Codechef ide is slower . ( Just for comparison much slower than CF and Atcoder’s)

image
I ran the test generated by this generator

gen.cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;

ll rand(ll a, ll b) {
    return a + rand() % (b - a + 1);
}
const ll mxN = 1e9 ;
int main(int argc, char* argv[]) {
  srand(atoi(argv[1]));
 	int t =100 ;
 	cout << t<< '\n' ;
 	while(t--){
 		int n = 5e5 ;
 		cout << n << '\n' ;
 		for(int i=0;i<n;i++)
 			cout << rand(0,1) ;
 		cout << '\n' ;
	}
}

Maybe my PC is slow, how much time does this test-case take on your pc.

In the problem it states that,
the sum of N over all test cases does not exceed 5 . 10^5
But your generator clearly exceeds that. (which is 100*(5e5) in your case)
I’d suggest changing n to 5e3.

1 Like

Ah… my bad totally missed it, looks like CodeChef is slow indeed. Other test-cases are working under 0.6 seconds.

2 Likes

Is there any DP based sol. which anyone tried something like dp[N][2] ? If so I request u guys to please link ur sol. Thanx

Nice Explaination

Hey please could someone tell the problem with my code.
My idea is same as the editorial but I just shifted all leading zeros to the end so that the starting character is always 1.

code
Thanks!

it fails on
1
6
110010

Why this solution is giving WA?
48020224

It is possible that a larger d gives lesser flips than a smaller d.