Its such a shame being an expert i solved only A and C in the contest. I ended up solving E 10 minutes after the end.
after seeing other peoples codes i believe my solution is a alot complex but as per me i think its a very good solution
first we construct the forest from the regular bracket sequence.
its basically a collection of rooted trees.
we make sure children of each node are strictly ordered like the first child must be the left most one as it matters.
now we can see that maximum consecutive ((( is equivalent to any path which starting from a node only goes down to the left most (first) child
an operation is equivalent to removing a leaf and putting it on top of tree
we might compute subtree sizes initially.
now we compute an important term cost[x] be the sum of all subtree sizes of nodes which come before this node in its parent ordered list
basically its the number of times we have to perform operation to make sure that this node is the first child of its parent
from here i used binary lifting define up[i][j] be the 2^jth ancestor of node i and sum[i][j] be the sum of first 2^j ancestors of node i (0th ancestor is i itself)
we can see that if we iterate the downmost node of final optimal path cost[x] is simply the cost of going to its parent
so after fixing first node we can use binary lifting to go as up as we can with some not exceeding k after that
if the final node we took has a parent then cant go up anymore just update the answer
else if we make this the left most node of the whole tree then we will be able to again include the nodes on whcih we perform an operation since they go to very top so we also compute the cost value for all nodes which dont have a prent then remaining value of k be val let current node be x and number of nodes be cnt if cost[x] <= val : we can update cnt = min(N / 2, cnt + k); because all those leaves go up and if we can make this as left most we can also add those k leaves to answer on whcih we performed operation
(pardon my english)
