Arjun can we can generate a RBS using 2nd optimal sequence?? i.e. ()( answer for this is YES. But as we are able to generate two different sequences using 1st and 2nd optimal approach, overall answer will be NO.
*I came up with DP approach with O(n^2) time complexity, but it didn't work. I would have never thought that the problem can be solved by using Greedy. I guess we gotta keep practicing;))))))* LETS GOOO!!!
To find opening and closing questions marks, why do u need prefix sums. In a RBS there are n/2 open and n/2 close. Count the cur_open and cur_close. THen, opening_question marks=n/2-cur_open and closing_question_marks=n/2-cur_close. However, the prefix sum>=0 actually led to actual solution. Great! From next time i will try to think on prefix sums for bracket sequence problems.
For sequence to be RBS, final prefix sum should be 0. That means if with ignoring '?' final prefix sum is x then '?' must contribute -x to make the sequence RBS.
But why is it impossible to create RBS with third optimal approach when second is impossible? I'm sorry it is not intuitive proved for me. ((())) first (()()) second and third ()()()
Join the discord for doubts and more:
discord.gg/aFBTauq
i spent 1 hr for this question and still wasn't able to find the solution, after seeing this video u literally just opened my eyes....great work bro🔥🔥
Great to hear!
Thanks for the video
No worries :)
Give this guy a medal 🥇
:)
Tank you, I learnt a lot from you.
Thanks Asala
Lovely explanation
Thanks Arjun
Thanks!
Welcome!
what is the logic behind both approaches
Prefix sums must be positive.
Finally was able to solve B thanks everyone for guidance
Glad it helped.
Great man, but today's B problem was too easy.
Subscribed!!
Thanks
this is inhuman problem , no education in educational round
but great video
Yeah seemed just lucky I thought of this approach. I was doing some random sweep +1,-1 algos with keeping ? as buffer.
?(?)()?) it's not working on this one output is "YES" by our solution but it should be "NO" how?? Correct me If I am wrong !
Arjun can we can generate a RBS using 2nd optimal sequence?? i.e. ()( answer for this is YES. But as we are able to generate two different sequences using 1st and 2nd optimal approach, overall answer will be NO.
Do u have any advice to help me solve c in the contest as it seems really hard for me to solve
Problem C for the previous contests have been little harder than usual
*I came up with DP approach with O(n^2) time complexity, but it didn't work. I would have never thought that the problem can be solved by using Greedy. I guess we gotta keep practicing;))))))* LETS GOOO!!!
To find opening and closing questions marks, why do u need prefix sums. In a RBS there are n/2 open and n/2 close. Count the cur_open and cur_close. THen, opening_question marks=n/2-cur_open and closing_question_marks=n/2-cur_close. However, the prefix sum>=0 actually led to actual solution. Great! From next time i will try to think on prefix sums for bracket sequence problems.
Yes that also works.
Please also make videos on d,e problems of this round
Will be making a video on D. E was quite hard so don't know video on that will be possible.
Not able understand solution of xor tree problen E can you help plz
replied to you on discord
it would be good if u link the code in the desc
It would provoke a bad habit, i recommend to implement on your own.
Sir in Line no 46 to 52 what is actually going on ?
We are generating 2nd optimal sequence and inserting them into question marks. Then we are checking if the string generated after this is RBS or not.
Ohk sir now i gót it...thnx for clearification 😇
Hats off
Thanks Ayush :)
How is o - c equal prefix need proof
For sequence to be RBS, final prefix sum should be 0. That means if with ignoring '?' final prefix sum is x then '?' must contribute -x to make the sequence RBS.
@@competitivecoding-newtonsc9601 Mashallah quick and good answer thank you soo much☺
❤️👍
:)
Code doesnt work
It does
Please upload d
will upload in the morning
first submit on the cf yourself then give the code here.
The code is accepted :)
@@competitivecoding-newtonsc9601 it's giving Yes for ?(?)()?)
But why is it impossible to create RBS with third optimal approach when second is impossible? I'm sorry it is not intuitive proved for me.
((())) first (()()) second and third ()()()
If 2nd optimal approach didnt give a RBS, that means there was an index i with pref[i]
@@competitivecoding-newtonsc9601 thanks a lot, I get it)
How to think like that in the actual contest ?🥲
Keep trying various things. I also thought of this accidentally. My first approach was way off.
Ok thanks bhaiya❤
It is a kind of adhoc, so have to try different approaches until u get AC