Xupcak's blog

By Xupcak, history, 9 years ago, In Russian

всем привет , кто может объяснить решение этой задачи ?

P.S. я прочел разбор , но не понял.

заранее не минусуйте...

  • Vote: I like it
  • +7
  • Vote: I do not like it

»
9 years ago, # |
Rev. 16   Vote: I like it 0 Vote: I do not like it

Писал одному разбор в личку. На английском.

Hello!

Sorry for the delay.
So, the main idea is to count the DPlen, bal — number of valid bracket sequences which have length len and final balance bal.

DP0, 0 = 1, just empty sequence.
DPlen, bal = DPlen - 1, bal - 1 (we added ( to all valid sequences of length len - 1)  + DPlen - 1, bal + 1 (we added ) to all valid sequences of length len - 1);

Note: Don't forget to care about bounds. In my implementation I use the forward DP style — instead looking the previous values I add current values to next DP states.

Definitions:
— String is 0-indexed array.
N — length of the string.
— For the given string replace ( with 1 and ) with  - 1.
— For the reverse string of given string replace ) with 1 and ( with  - 1.
i-th prefix sum — sum of corresponding values from 0-th index to i-th index.
i-th suffix sum — sum of corresponding values from N - 1-th index to i-th index.
— Prefix balance (I will call it pref) — minimum of all i-th prefix sums, where 0 ≤ i ≤ N - 1
— Suffix balance (I will call it suff) — minimum of all i-th suffix sums, where 0 ≤ i ≤ N - 1

Valid bracket sequence has the following properties:
pref ≥ 0.
suff ≥ 0.

Then we have some observations which I will explain on an example.

Example: ())()((
Prefix sums: {1, 0,  - 1, 0,  - 1, 0, 1}
Suffix sums: { - 1, 0,  - 1,  - 2,  - 1,  - 2,  - 1}

pref =  - 1.
suff =  - 2.

That means that the string p (from the problem description) must have a prefix balance  ≥ 1 to make the sequence valid.
Also the string q must have a suffix balance  ≥ 2.

Observations:
— Symmetry — the number of valid sequences with length len and prefix balance bal =  number of valid sequences with length len and suffix balance bal = DPlen, bal
— If length of p is len then the length of q is n - m - len.
— Balance of p is  ≥ pref.
— Balance of q is  ≥ suff.
— If we have additional bal balance in p we must have the same additional balance in q.

So, to count the answer we can iterate through all possible lengths and balances of p and add to answer DPlen, pref + bal * DPn - m - len, suff + bal.

If something is not clear just say. :)

Код.