B. JoJo's Incredible Adventures - Unraveling the Maximum Area Rectangle Problem

Welcome back, aspiring programmers!

Today, we will explore my solution for problem B - JoJo's Incredible Adventures, an intriguing challenge from Codeforces. If you haven't tried it yet, you can find the problem link here. The problem tasks us with finding the maximum area rectangle consisting only of ones within a square table formed by cyclic shifts of a given binary string s. Without further ado, let's delve into the intricacies of this enigmatic puzzle and dissect my solution step by step.

Understanding the Problem

In this problem, we are given a binary string s of length n, comprising characters '0' and '1'. We are required to construct a square table of size n×n, where each row represents a cyclic shift of the original string s. The goal is to find the maximum area rectangle consisting solely of ones within this table.

The Solution Approach

To tackle this problem efficiently, I adopted the following approach:

1. Initialize variables to keep track of the total consecutive ones, the indices of the first and last zeros encountered, and a count to find consecutive ones.

2. Traverse the string s character by character. Whenever we encounter '1', we increase the count of consecutive ones. When we encounter '0', we update our variables and reset the count.

3. Calculate the maximum consecutive ones before the first zero and after the last zero. These values will help us in finding the maximum area rectangle.

4. Calculate the half of the total consecutive ones and then compute the area of the maximum rectangle. This area is the product of half of the total consecutive ones and the remaining consecutive ones after dividing by two.

The Code Implementation

#include<bits/stdc++.h>
using namespace std;
#define Sezar  ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL)
#define tc(t)  int t; cin >> t; while (t--)
#define ll     long long

// Function to calculate ceiling division of two integers
ll ceil_div(ll a, ll b) {return a % b == 0 ? a / b : a / b + 1;}

void solution()
{
    string s;
    cin >> s;
    ll totalConsecutiveOne = 0, indexOfFirstZero = -1, indexOfLastZero = -1, count = 0;

    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] == '1')
            count++;
        else
        {
            totalConsecutiveOne = max(totalConsecutiveOne, count);
            count = 0;
            if (indexOfFirstZero == -1)
                indexOfFirstZero = i;
            if (indexOfLastZero < i)
                indexOfLastZero = i;
        }
    }
    // If all characters in the string are ones
    totalConsecutiveOne = max(totalConsecutiveOne, count);

    if (totalConsecutiveOne == s.size())
    {
        // If all characters in the string are ones, 
       //the maximum area is the area of the squre itself.

        ll anss = totalConsecutiveOne * totalConsecutiveOne;
        cout << anss << endl;
        return;
    }

    ll totalConsecutiveOneBeforeFirstZeroAndAfterLastZero = indexOfFirstZero + (s.size() - indexOfLastZero - 1);

    totalConsecutiveOne = max(totalConsecutiveOne, totalConsecutiveOneBeforeFirstZeroAndAfterLastZero);

    ll halfOfTotalConsecutiveOne = ceil_div(totalConsecutiveOne, 2);

    ll ans = halfOfTotalConsecutiveOne * (totalConsecutiveOne - halfOfTotalConsecutiveOne + 1);

    cout << ans << endl;
}

int main()
{
    Sezar;
    tc(t) solution();
}

Time and Space Complexity

Time Complexity: The time complexity of this solution is O(n), where n is the length of the input string s. This is because we traverse the string s only once to find the required values.

Space Complexity: The space complexity is O(1) as we are using a constant amount of additional space to store variables for calculations.

Conclusion

Congratulations! You have successfully unraveled the solution to problem B - JoJo's Incredible Adventures on Codeforces. This fascinating challenge allowed us to explore the world of cyclic shifts and apply some clever calculations to find the maximum area rectangle composed of ones within a square table. I hope this blog has helped you comprehend the problem better and provides a clear understanding of my code solution.

Happy coding and until next time, keep honing your programming prowess! 🚀

Farhan Ishtiyak