ZOOZ - Editorial

editorial
,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: kulyash
Tester: Harris Leung
Editorialist: hrishik85

DIFFICULTY:

1009

PREREQUISITES:

None

PROBLEM:

The problem requires us to construct a binary string of length N such that the count of ‘01’ subsequences is equal to the count of the ‘10’. The string should have at least 1 occurrence of ‘0’ and ‘1’.

EXPLANATION:

A subsequence of a given sequence is a sequence that can be derived from the given sequence by deleting some or no elements without changing the order of the remaining elements. Kindly note the important point here that ‘the order of remaining elements’ cannot be changed.

Multiple solutions are possible for this string construction problem. The constraint also states that N >= 3.

Hint 1

Can we create a few strings of smaller length to identify a pattern or logic to solve this question?

Hint 2

Lets see a few example binary strings. Let us try and identify if they meet the condition or not.

Hint 2a

100 - This string has 2 occurrences of subsequence ‘10’ and 0 occurrences of subsequence ‘01’. This does not meet the condition.

Hint 2b

001 - This string has 2 occurrences of subsequence ‘10’ and 0 occurrences of subsequence ‘01’. This does not meet the condition.

Hint 2c

10101 - This string has 3 occurrences of subsequence ‘10’ which are - 10101, 10101 and 10101

It also has 3 occurrence of subsequence ‘01’ as follows - 10101, 10101 and 10101

Since the count of ‘01’s match the count of ‘10’s - 10101 is a valid string

Hint 2d

1010 - This string has 3 occurrences of ‘10’ and 1 occurrence of ‘01’. This is not a valid string

Hint 2e

111000 - This string has 9 occurrences of ‘10’ and 0 occurrences of ‘01’. This is not a valid string

Hint 2f

111001 - This string has 6 occurrences of ‘10’ and 2 occurrences of ‘10’. This is not a valid string

Hint 2g

110011 - This string has 4 occurrences of ‘10’ and 4 occurrences of ‘01’. This is a valid string

Hint 2h

101010 - This string has 6 occurrences of ‘10’ and 3 occurrences of ‘01’. This is not a valid string

Hint 2i

11011 - This string has 2 occurrences of ‘10’ and 2 occurrences of ‘01’. This is a valid string

Hint 2j

01010 - This string has 3 occurrences of ‘10’ and 3 occurrences of ‘01’. This is a valid string

What do we observe from the above examples that can help us solve this problem?

Hint 3

Note that the number of ‘1’s and ‘0’s do not need to be equal to get a valid string

Hint 4

A simple way to solve this problem is to construct a string such that it has ‘1’s at the extreme end of the string and ‘0’s in its body. For example ‘1001’, ‘10001’, 100001’, ‘1000000001’. Since N >= 3, we can use this to construct a string of any length N >= 3.

TIME COMPLEXITY:

Time complexity is O(N).

SOLUTION:

Tester's Solution 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define fi first
#define se second
const ll mod=998244353;
const int N=2e5+5;
int n;
ll a[N];
int main(){
	ios::sync_with_stdio(false);cin.tie(0);
	int t;cin >> t;
	while(t--){
		int n;cin >> n;
		cout << '0';
		for(int i=1; i<=n-2 ;i++) cout << '1';
		cout << "0\n";
	}
}
Editorialist's Solution 
t=int(input())
for _ in range(t):
    n=int(input())
    s=str()
    i=0
    while i<(n-2):
        s=s+'0'
        i=i+1
    s='1'+s+'1'
    print(s)
2

can you please point out my mistake none of the test case during submission were right **#include
using namespace std;

int main() {
// your code goes here
long long int t;
cin>>t;
while(t–)
{
long long int a;
cin>>a;
string s1="";
if(a==3)
{
cout<<“010”<<endl;
}
else
{
if(a%2==0)
{
string s=“10”;
string y=“01”;
long long int k=(a-4)/2;

        for(long long int i=0;i<k;i++)
        {
           s1=s1+'0';
        }
        s1=s+s1+y;
        }
    else
    {
        s1="010";
        long long int k=(a-3)/2;
        
        for(long long int i=0;i<k;i++)
        {
           s1='0'+s1+'0';
        }
        
    }
    std::cout << s1 << std::endl;
    }
}
return 0;

}**

3

In if (a%2 == 0) the k should just be a - 4

4

yes, i did’nt notice thanks for reply

1 Like
5

Can someone tell which testcase are failing for below code?

int n;
    cin >> n;
    if(n%2==0){
        for(int i =1;i<=n/2;i=i+2){
            cout<<"10";
        }
        for(int i =1;i<=n/2;i=i+2){
            cout<<"01";
        }
        cout<<"\n";
        return;
    }else{
        cout<<"010";
        n = n-3;
        for(int i =1;i<=n/2;i=i+2){
            cout<<"10";
        }
        
        for(int i =1;i<n/2;i=i+2){
            cout<<"01";
        }

    }
6

So, I tried this code.

#include
using namespace std;

void solver(){
int n;
cin>>n;
if(n==3){
cout<<101<<endl;
}else{
n-=4;
cout<<10;
for(int i=0;i<n;i++){
cout<<1;
}
cout<<01<<endl;
}
return;
}

int main() {
// your code goes here
int t=1;
cin>>t;
while(t–>0)
solver();
return 0;
}

My idea is that the basic pattern is
10 (n-4) times 1 01
and if n is 3 then 101

can someone point out the issue here?

7

https://coderceo.com/zero-ones-equal-one-zeros-codechef-problem-java-solution/

Here is solution in java

8

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

void solve(){

int n;
cin>>n;
	if (n%2==0)
	{
		for (int i =1; i <=n/2; ++i){
		if(i%2!=0){
			cout<<"10";
		}
		else
			cout<<"01";
		}
		cout<<endl;
	}
	else{
		for (int i = 0; i < n/2; ++i)
		{
			cout<<"01";
		}
		cout<<"0"<<endl;
	}

}

int main()
{

ios_base::sync_with_stdio(false);
cin.tie(NULL);

int t;
cin>>t;
while(t--){
	solve();

}

return 0;
}

can anyone explain me why this gave me WA even though it passed the test cases when i ran on my ide.
Is there any other test case which it can’t pass?

9

when the the input is 6 your code will print 100110 (which means 5*“10” and 4*“01”)

10

Why is my solution wrong, i think it is correct even for cases like 7 or 15 that are a bit of an edge case. Seems right to me. I’ve seen simpler solutions but mine also works, I think. Main funtion:

    public static void main (String[] args) throws java.lang.Exception
     {
	 Scanner sc = new Scanner(System.in);
	 int T = sc.nextInt();

	 while(T-->0) {
		int N = sc.nextInt();
		char bin[] = new char[N];
		for(int i=0;i<N-1;i=i+4) {
			
				bin[i]='0';
				bin[i+1] = '1';

		}		
		for(int i=2;i<N-1;i=i+4) {			
				bin[i]='1';
				bin[i+1] = '0';
			
		}
		if(N%2!=0 || N%4 !=0) bin[bin.length -1] = '0';
		
		System.out.println(new String(bin));
		
	
	}
	sc.close();
}