3
\$\begingroup\$

I solved this problem statement on dear old codeforces. The Problem Statement wants users to replace occurrences of '10' in the given string with either '1' or '0' until there is no occurrence of '10' left and the string formed is the lexicographically smallest string from the set of all valid answers.

This is my solution (and it has been accepted). However, I would like to know if we can simplify this solution further:

#include <algorithm>
#include <iostream>
#include <string>
#include <vector>
 
int main() {
    int T = 0;
    std::cin >> T;
    while (T--) {
        int n = 0;
        std::cin >> n;
        std::string str;
        std::cin >> str;
        while (str.find("10", 0) != std::string::npos) {
            auto it = std::find(str.begin(), str.end(), '1');
            auto begin = it;
            std::string window;
            while (it != str.end() && *it == '1') {
                window.push_back(*it);
                it++;
            }
            while (it != str.end() && *it == '0') {
                window.push_back(*it);
                it++;
            }
            if (std::count(window.begin(), window.end(), '0') == 0 || std::count(window.begin(), window.end(), '1') == 0) {
                std::cout << str << "\n";
                break;
            }
            while (window.size() > 1) {
                auto count0 = std::count(window.begin(), window.end(), '0');
                auto count1 = std::count(window.begin(), window.end(), '1');
                if (count0 > count1) {
                    window.erase(--window.end());
                }
                else if (count1 > count0) {
                    window.erase(window.begin());
                }
                else {
                    if (str.find("10", std::distance(str.begin(), it)) == std::string::npos) {
                        window.erase(window.begin());
                    }
                    else {
                        window.erase(--window.end());
                    }
                }
            }
            *(--it) = window.front();
            str.erase(begin, it);
        }
        std::cout << str << "\n";
    }
    return 0;
}

Please review and suggest :)

\$\endgroup\$
  • 1
    \$\begingroup\$ Please copy the full problem statement from the source and paste it in the question. Links can break. \$\endgroup\$ – pacmaninbw Jun 23 at 21:59
5
\$\begingroup\$

Add some comments describing your algorithm

Your code is a single function which is a bit long, and it's not very obvious what it is doing. There are two ways of dealing with this: either creating functions that implement logical steps of the algorithm individually, or add some comments to describe which steps your algorithm is doing. Don't add comments that just descibre exactly what the code does, but give a higher level description.

Unnecessary use of std::count()

You use std::count() a lot, but you don't need to. You can count the number of zeroes and ones when building window, and when you are calling window.erase() you can decrement your counts.

Consider using std::string functions to search for blocks of zeroes and ones

Instead of using std::find() and counting manually using while-loops, you can use std::string::find(). You can also construct a string directly from a subregion of another string.

auto first1 = str.find('1');
auto next0 = str.find('0', first1);
auto next1 = str.find('1', next0);

std::string window(str, first1, next1 - first1);

Once you have that, calculating the number of zeores and ones in window is easy:

auto count1 = next0 - first1;
auto count0 = window.size() - count1;

However, you might not even need the initial window:

Avoid constructing and then partially deconstructing the window

Your window consists of a number of ones followed by a number of zeroes. You are then slowly removing from the start and end until some conditions are met. However, while you are doing this, the only thing you really care about is the count of zeroes and ones, not the string window itself! You can reconstruct the final window from the counts left at the end.

Let's assume we have calculated count0 and count1 like I've written above. Then:

while (window.size() > 1) {

Can be replaced with:

while (count0 + count1 > 1) {

Then you do:

if (count0 > count1)
    window.erase(--window.end());
else if (count1 > count0)
    window.erase(window.begin());

Basically, this removes zeroes or ones until the number of zeroes or ones is equal. This can be replaced with the following:

count0 = count1 = std::min(count0, count1);

Then the next condition is:

if (str.find("10", std::distance(str.begin(), it)) == std::string::npos)
    window.erase(window.begin());
else
    window.erase(--window.end());

Since str is not modified here, you could move the if-condition outside of the loop. And the window.erase() calls can be replaced by count0-- and count1--. So what's left is:

bool has_second_10 =  str.find("10", next0 + count0) != str.npos;

while (count0 && count1) {
    if (count0 != count1) {
        count0 = count1 = std::min(count0, count1);
    } else {
        if (has_second_10) {
            count0--;
        } else {
            count1--;
        }
    }
}

But wait, it gets even better: you always start with a window with both ones and zeroes, and you make the count equal, and then you remove zeroes if the original string had a second occurrence of "10", otherwise you remove ones. So the single character left in the window is completely determined by has_second_10, and the while-loop can be eliminated entirely. You also don't need to count ones and zeroes anymore.

Now it's just a matter of updating the original string. Instead of modifying a character and erasing some, you can use the std::string::replace() function to do that in one go:

str.replace(first1, next1 - first1, 1, has_second_10 ? '1' : '0');

Summary

With the above improvements, the code can be simplified to:

#include <iostream>
#include <string>
 
int main() {
    int T = 0;
    std::cin >> T;

    while (T--) {
        int n = 0;
        std::cin >> n;
        std::string str;
        std::cin >> str;

        while (str.find("10", 0) != str.npos) {
            auto first1 = str.find('1');
            auto next0 = str.find('0', first1);
            auto next1 = str.find('1', next0); // this might be npos, but that's fine
            auto replacement = str.find("10", next1) == str.npos ? '0' : '1';
            str.replace(first1, next1 - first1, 1, replacement);
        }

        std::cout << str << "\n";
    }
}
| improve this answer | |
\$\endgroup\$
  • 1
    \$\begingroup\$ And this would have negated part of my possible answer because the code is now short enough not to require sub functions. \$\endgroup\$ – pacmaninbw Jun 23 at 22:37
  • \$\begingroup\$ One of the most detailed explanations I've ever been given. Thanks a lot. I will definitely implement your suggestions :) UV coming up \$\endgroup\$ – d4rk4ng31 Jun 24 at 5:08
2
\$\begingroup\$

The problem statement is much more about logical reasoning than about coding. On a unix/linux terminal, the challenge can be solved with 15 characters!

sed 's/1.*0/0/'

The equivalent c++ code is also a one-liner when using regex::replace, or a three-liner with string::find and string::replace. If you read the instructions carefully and work through a few examples, you will find two important properties (a formal proof is just as easy):

  1. Any binary string that starts with a one and ends in zero can be reduced to a single digit. You even have the choice whether this digit is zero or one.

  2. Leading zeros and trailing ones cannot be reduced.

To solve the challenge, just ignore leading zeros and trailing ones and replace the middle part, if non-empty, with a single zero digit. That's what my sed script does.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.