Could you please explain how to solve this (bonus) problem? I've no idea...

Congrats, you just caused this problem to become of positive value :P

simple solution, thank u so much...u saved me from official solution

Nice One :) .

Thanks for such a nice solution.

I had basically the same solution but (again maybe?) just a little more natural to explain.

At each moment we will define l and r as minimum and maximum number of unclosed brackets in the sequence before given that it is a prefix of a correct bracket sequence. For every starting position initially l = r = 0. When we iterate over '(' or ')' we obviously increase or decrease both by one correspondingly. When we iterate over '?' we decrease l and increase r by one. If r < 0 at any point we stop here and go to a next starting position. l can't be less than 0, so if l < 0 we increase it by 2. Finally the ending position is possible if and only if l = 0.

string s;
getline(cin, s);
int n = s.size();
int ans = 0;
forn(st,0,n) {
    int l = 0;
    int r = 0;
    forn(e,st,n) {
        if (s[e] == '(') {
            l++;
            r++;
        }
        else if (s[e] == ')') {
            l--;
            r--;
        }
        else if (s[e] == '?') {
            l--;
            r++;
        }
        if (r < 0) break;
        if (l < 0) l+=2;
        if (l == 0) ans++;
    }
}
cout<<ans;

Could you please explain it on a test: "???(" ?. Here, if I consider the whole substring, right from the 1st iteration, qmarks > score. so: qmarks = 1 score = -1; qmarks = 2; score = -2; qmarks = 3; score = -3; score = -2

Hence, the length is even and qmarks >= score. Hence it's legal. But you can't form any valid bracket with this sequence. Am i missing something?

Thank you so much. I don't understand why editorialists don't write editorials like this.

Won't the time complexity be O(n^3) then?O(n^2) for every every substring and checking takes another O(n).?

Actually, you don't need to check qmarks>=score, just qmarks==score would do, as you're deliberately balancing qmarks and score is qmarks>score.

Here is a submission describing that.

And India is blessed to have a coder like you.

if one's make "a" move can make other lose then it is optimally move right? so you have to find a path that the ichar(i) is big enough that the next person cant go any further

c < int(ch(v, x) - 'a') and dp(u, x, ch(v, x)) = false its mean the ichar you have is larger than the limit now and the ichar you have ,can make the next player fail to move,( dp is false) , thus the state now is true

Sigma is the size of the constraint on the edge. In this case,its 26. If we allowed numbers(from 0 to 9) and alphabets both in the problem, then it would have been 36.

Same. I am also really confused about this part.

In my submission (343647) I only build two big suffix trees explicitly.

In the centroid decomposition I find for each query one node in each of these 'big trees'. After the centroid decomposition I preprocess one of the suffix trees, finding for each of the queries the last node in the suffix tree that is an ancestor of the node from the centroid decomposition and is a suffix of the special word for the query (which is probably what you call 'the position in the small tree', see wlast, oldwlast and qstidx in my code).

Also at the same time I construct for each suffix of a special word the range in the inorder traversal for that special word that corresponds to the subtree (which is similar to an euler tour of the 'small trees', see bwlid and bwrid in my code).

Could you explain your solution?