Not able to solve this

#1

I am trying to solve this question…
https://codeforces.com/contest/1323/problem/C
I tried for a long time…But couldn’t reach to a proper acceptable solution.
I saw the editorial… But not able to get much intution.
Please tell me… what should be the approach in this question.

#2

hello @ashishnnnnn

have u solved balanced paranthesis problem?

#3

Yes…There we use stack…
Actually i have used something like that…
In this question…
https://codeforces.com/contest/1323/submission/99316928
Couldn’t find where i am wrong.

#4

if string containts only ( and ) then the idea without stack is that we iterate from left to right if we encounter ( then we incremnt the count and i we encounter ) then we decrement the count[ removing 1 -> ( from the count ] at the end if the value of count is zero then that indicates that string is balanced otherwise not balanced

let me know r u getting this or not

#5

Yaa… But here we don’t have to check only that whether string is balanced or not…

#6

i m talking about idea not the solution

#7

Yaa… I got the idea to check if balanced or not…
similar i have done in my subssion… There i have counted number of “(” and number of “)”…
If they are equal…means it can be made as balanced string.

#8

ok ,another propery that balanced paranthesis satisfies is number of for and index i number of opening brackets till i >= number of closing brackets till i.

let me know it make sense or not

#9

Yaa… Make sense…

#10

that means for balanced paranthesis count will nver be negative right?
it will be either be + ve (number of opening brackets > number of closing brackets) or 0 (balanced) right?

#11

Yaa…got till here…

#12

image
now the first graph should make sense to u
just plotting count on y axis and index on x axis.

#13

Yaa… Make sense… :slight_smile:

#14

now the mountains that are down the line must be above the line to make the overall string balanced.
becuase just now we discussed that count for balnaced paranthsis cant be negative

#15

Yaa… that is right…

#16

so the problem is solved now. we just need to pick such negative mountains and make them positive/0.
so answer will be summation of lenght of all negative mountains

#17

Yaa…means mountains which are negative we have to make them positive…

#18

yes… . … . . .
. . .

#19

Yaa… Got it…
Thanks … A lot of thanks for explaining with that much detail… … :slight_smile::slight_smile:

#20

keep this technique in mind. this is very much helpful in solving parathesis based problems