1
$\begingroup$

I'm new to dynamic programming and find a problem about balancing parentheses and smileys ":)" and "(:" at HackerRank, which is impossible to do.

I've been trying to solve it by 3 days now. The main issue with this problem is that the input string size is in range of 10^9 (creating a dynamic programming 2d array of size 10^9*10^9 takes forever) and no matter what I try the execution time out. Someone please help.

Here is the problem about balancing parentheses and smileys ":)" and "(:"

Improve this question
$\endgroup$
  • $\begingroup$ What have you tried? $\endgroup$ – nir shahar Jul 11 '20 at 9:37
  • $\begingroup$ @nirshahar here it is : hastebin.com/iwixojegil.http $\endgroup$ – some dev Jul 11 '20 at 9:42
  • $\begingroup$ Could you explain to me the idea for the code? Im not really good in C++ $\endgroup$ – nir shahar Jul 11 '20 at 10:03
  • $\begingroup$ @nirshahar here I have a clean explanation if you have any trouble ask me hastebin.com/aliqovitus.cpp $\endgroup$ – some dev Jul 11 '20 at 10:57
  • 1
    $\begingroup$ In standard balancing parentheses problem, at every position in the string, you have a single number: the current number of unmatched opening parentheses. But here you can have multiple numbers; when you encounter :), you can treat it as either parenteses or not, and your depth can either remain the same or decrease by 1. Now note that at any point, possible numbers form an interval. Interval update rules are simple. When you see ): [a, b] -> [a-1, b-1]. When you see :): [a, b] -> [a-1, b] (since you can ignore parentheses, the upper bound doesn't decrease). ( and :( are similar $\endgroup$ – Dmitry Jul 11 '20 at 10:57
2
$\begingroup$

The problem confused me as well until I understood that smileys can be separated into a colon and a parentheses if required (because a colon as the text says is also a valid character.) Now you can write a linear algorithm. By counting how many brackets are open, how many could be opened by smileys and how many could be closed by smileys:

int main() {
    int n; string s; 
    getline(cin,s); n = stoi(s); // get value of n
    for(int i = 0; i < n; i++){
        getline(cin,s);          // read line
        ll open = 0, smiopen = 0, smiclose = 0;
        bool colon = false;      // was the last character a colon?             
        bool balanced = true;
        for(ll j = 0; j < s.size(); j++){
            if(colon){
                if(s[j] == '(') smiopen++;  //you COULD open an expr.
                if(s[j] == ')' && open > 0) {open--; smiclose++;} // you COULD close an expr.
            }else{
                if(s[j] == '(') open++; // you HAVE TO open an expr.
                if(s[j] == ')') {       // you HAVE TO close an expr.
                    if(open > 0) open--;
                    else if(smiopen > 0) smiopen--;   //open an optional expr. for balance
                    else if(smiclose > 0) smiclose--; //unclose optional close
                    else{ balanced = false; break;}   //not possible to match found ')'
                }
            }
            colon = false; 
            if(s[j] == ':') colon = true;
        }
        if(balanced && open == 0) cout << "YES"<<endl;
        else cout << "NO"<<endl;
    }
}

You might notice smiopen and smiclose could be fused into one variable. But I separated them for clarity.

Improve this answer
$\endgroup$
  • $\begingroup$ wow it worked. thanks a lot (today I can sleep with a smile) $\endgroup$ – some dev Jul 11 '20 at 14:24

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.