BOBAS's blog

Open Cup 11-25, solutions of E and J request
By BOBAS, 13 years ago, In English

I'd be happy if someone explained the solutions of E and J.

http://acm.math.spbu.ru:17249/~ejudge/files/opencup/oc12/gp6/gpce-e.pdf

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

»
13 years ago, hide # |
← Rev. 4  
Vote: I like it +9 Vote: I do not like it

Problem E.

Let calc(i, j) be the maximum coverage length of a special symbol i in the pattern P starting from P[j]. Then for each equation of the form A = B + C, calc(A, j) = calc(B, j) + calc(C, j + calc(B, j)), and for equation A = a word over * {a, ..., z} we count it the simple way.

To speed up, use a hash table (unordered_map) to memorize calc(i, j) values.

The solution is then calc(S, 0) == strlen(P).

→ Reply