BININSC - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

Author: John Zakkam
Testers: Aneesh D H, Suryansh Kumar and Siddharth
Editorialist: John Zakkam

DIFFICULTY:

CAKEWALK

PREREQUISITES:

Basic geometry, Basic math.

PROBLEM:

Given a binary string S consisting of only 1ā€™s and 0ā€™s where 1 represents a Square and 0 represents a Circle . The diameter of the circle and the side of the square must be any integer (obviously > 0) . You will have to perfectly inscribe the respective geometric figure at Si+1 inside of Si where i Ļµ [0,Nāˆ’2], if it is possible . Note that, it will not be possible to inscribe if the dimension of the geometric figure you are perfectly inscribing is not an integer and you will discard the rest of the string. Find the maximum number of circles we can inscribe in a square according to the given string.

KEY OBSERVATION :

For any circle that is perfectly inscribed in a square of any integer dimension, let the side of the square be a, then the circle which should be perfectly inscribed in this square should have a diameter a and if we now want to perfectly inscribe another square in this circle of diameter a, we need a square of side a/\sqrt{2} so, it is not an integer. But by observation, we can inscribe another circle of the same diameter any number of times.

EXPLANATION:

We check for the first occurrence of a contiguous substring of 1ā€™s in the string then print the count of the number of zeroes present after it .This is only possible when the first character of the binary string is 1, if the first character is 0, then we can directly print 0.

SOLUTIONS:

Setter's Solution in C++ 
#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

int32_t main()
{
	ll n;
	cin >> n;
	vector<string> s(n);
	for (int i = 0; i < n; i++)
		cin >> s[i];
	for (int i = 0; i < s.size(); i++) {
		if (s[i][0] == '0')
			cout << 0 << endl;
		else {
			ll ans = 0, flag0 = 0, flag1 = 0;
			for (int j = 0; j < s[i].size(); j++) {
				if (s[i][j] == '1')
				{
					if (ans != 0)
						break;
					flag1 = 1;
				}
				else
				{
					flag0 = 1;
					if (flag1 and s[i][j] == '0')
						ans++;
				}
			}
			cout << ans << endl;
		}
	}
	return 0;
}
Tester's Solution in Python 
    t = int(input())
    for _ in range(t):
        s = str(input())
        if (s[0] == '0'):
            print(0)
        else:
            i=0
            ans=0
            while(i < len(s) and s[i]=='1'):
                i += 1
            while(i < len(s) and s[i]=='0'):
                ans += 1
                i += 1
            print(ans)

Time Complexity : O(n*b) where b is the maximum length of the binary string.

PS: I tried to explain it as properly as I could. Please let me know if there are any mistakes or if something is unclear. I hope people enjoyed Code Chronicles 2.0.

4 Likes