hossainzarif's blog

By hossainzarif, 2 months ago, In English

problem
submission
I don't know why my approach works.
I first found out the balance of every string $$$(number of left bracket - number of right bracket)$$$ and minimum balance of every string. let $$$bal$$$ be balance and $$$mnbal$$$ be minimum balance. Like $$$()))(($$$ has balance $$$0$$$ and minimum balance $$$-2$$$ (obtained at index $$$3$$$).
Then I took 4 vectors.
$$$v_1$$$ having pair $$$(mnbal, bal)$$$ where $$$mnbal >= 0$$$ and $$$bal >= 0$$$
$$$v_2$$$ having pair $$$(mnbal, bal)$$$ where $$$mnbal < 0$$$ and $$$bal >= 0$$$
$$$v_4$$$ having pair $$$(mnbal, bal)$$$ where $$$mnbal < 0$$$ and $$$bal < 0$$$ and $$$mnbal = bal$$$
$$$v_3$$$ having pair $$$(mnbal, bal)$$$ where $$$mnbal < 0$$$ and $$$bal < 0$$$ and $$$mnbal \neq bal$$$

Then, I sorted $$$v2$$$ in decreasing order and $$$v3$$$ in increasing order, and appended $$$v_1$$$, $$$v_2$$$, $$$v_3$$$, $$$v_4$$$ in order checking conditions and it got accepted. But, I can't find out why my idea works.
Please help.

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it