BNSONSTR - Editorial


Contest Division 1
Contest Division 2
Contest Division 3

Setter: Prasant Kumar
Tester & Editorialist: Taranpreet Singh






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.


  • 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.


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')

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.


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


Setter's Solution
using namespace std;

signed main(){
//	freopen("input.txt", "r", stdin);
    int t;cin>>t;
	    int n;cin>>n;
	    string s;cin>>s;
	    int sum=0;
	    for(int i=0;i<n;i++){
	    int ans=n;
	    for(int x=1;x<=n;x++){
		    for(int j=0;j<x;j++){
			    int temp=0;
			    for(int k=j;k<n;k+=x){
				    }else temp+=1;

    return 0;
Tester's Solution
import java.util.*;
class BinaryStringOnSteroid{
    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);
    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);
    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;}
    String nln()throws Exception{return in.nextLine();}
    int ni()throws Exception{return Integer.parseInt(;}
    long nl()throws Exception{return Long.parseLong(;}
    double nd()throws Exception{return Double.parseDouble(;}

    class FastReader{
        BufferedReader br;
        StringTokenizer st;
        public FastReader(){
            br = new BufferedReader(new InputStreamReader(;

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

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

        String nextLine() throws Exception{
            String str = "";
                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:


Don’t know what was happening, I was constantly write this solution only,
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)
PS: I think the codechef was giving wrong verdict, it should be MLE. Again, I got caught in this.


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)

Received Output:
Desired output:

I used Factorial method:
Can someone please help getting WA!

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

void printDivisors(long long int n, vector<long long int>& v)
    for (int i=1; i<=(n); i++)
        if (n%i == 0)

    string shiftall0s(string s)
        std::size_t found = s.find('1');
        if (found==std::string::npos)
        return s;
        string r = s.substr(found);
        return r;

int main() {
	int t;
	    long long int n;
        string 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++)
        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++)
            long long int bad=((str.length()/factors[i]) - good_pos) + bad_pos;
            min_diff = min(min_diff, bad);
	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,

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.
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.


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)

I ran the test generated by this generator

#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[]) {
 	int t =100 ;
 	cout << t<< '\n' ;
 		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.


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.


it fails on

Why this solution is giving WA?

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