Help me in solving ZOOZ problem

help
,
1

My issue

i dont understand why this code would give wrong answer.
For a string of length n, to have equal occurrences of 01 and 10, we can make sure the string 010 exists in the string spaced with 0s.
hence for n=6, it would be 010010 (as 6 is a multiple of 3 the string 010 repeats twice) for n = 7 it would be 0100100 there would be an extra 0 at the end as 7%3 = 1.
i don’t get for which case this approach would fail

My code

#include <iostream>
using namespace std;

int main() {
	// your code goes here
	int t; cin>>t ;
	while(t--){
	    int n ; cin>>n ;
	    
	    if(n%3 == 0 ){
	        for(int i = 0; i<n/3; i++){
	            cout<<"010" ;
	        }
	        cout<<endl ;
	        break ;
	    }else if(n%3 == 1){
	        for(int i = 0; i<n/3; i++){
	            cout<<"010" ;
	        }
	        cout<<"0"<<endl ;
	        
	        }else if(n%3 == 2){
	        for(int i = 0; i<n/3; i++){
	            cout<<"010" ;
	        }
	        cout<<"00"<<endl; 
	        
	    }
	   
	}
	return 0;
}

Problem Link: ZOOZ Problem - CodeChef

2

@shylamadan
In this question it is said that 01 and 10 as a subsequence not substring means they need not to be contiguous .
so not n=7
u r printing 0100100
it has subsequence of 01 =4
and it has subsequence of 10=6 which is not equal.

1 Like
3

What the question desires is your output must have same number of 01 and 10 as subsequence . For example :- 101 has single 10 and single 01 as subsequence.
but your code generates substrings which leads to the error.

Hint for solving this problem is think about this line in question
~The count of 0101 subsequences in the string is equal to the count of 1010 subsequences.
( It never states that your code must have N number of subsequences or many subsequences )

If you still have any doubts feel free to ask

1 Like
4

This is my solution using the concept of palindromes
it might help you :slight_smile:

t = int(input())
for i in range(t):
    n = int(input())
    bs = ""
    if (n % 2 == 0):
        lh = "1" + ("0" * (n//2 - 1))
        rh = lh[::-1]
        bs += lh
        bs += rh
        print(bs)
    else:
        lh = "1" + ("0" * ((n-2)//2))
        rh = lh[::-1]
        bs += lh
        bs += "0"
        bs += rh
        print(bs)
1 Like