Solution Notes (Kalki Seksaria):

A greedy algorithm solves this problem. We can define the depth up to a point in the string as opening paranthseses minus closing parentheses. Every time the depth becomes negative, we have to change a ')' into a '('. This must be done at or before the point at which the depth becomes negative. At the end of the string, the depth may be positive. If this is the case, depth/2 opening parentheses near the end of the string should be converted into closing parentheses. Only depth/2 reversals must be made because each exchange affects the depth by two. It may be the case that we have converted both '(' into ')' and ')' into '('. However, the greedy algorithm still works because it is impossible to make the two cancel, as all of the '(' into ')' exchanges must take place after the last ')' into '(' exchange.

#include <iostream>
#include <fstream>
using namespace std;
string s;
int main()
{
    ifstream in ("clumsy.in");
    ofstream out ("clumsy.out");
    
    in >> s;
    int depth = 0;
    int ans = 0;
    
    for (int i = 0; i < s.length(); i++)
    {
        if(s[i] == '(')
            depth++;
        else
            depth--;
        
        if(depth < 0)
        {
            ans++;
            depth += 2;
        }
    }
    ans += depth/2;
    
    out << ans << "\n";
    out.close();
    return 0;
}