BOBAS's blog

By BOBAS, 10 years ago,

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

• +12

 » 10 years ago, # | ← Rev. 4 →   +9 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).