### Temirulan's blog

By Temirulan, history, 5 years ago, ,

Прошел первый этап XV Открытого Кубка по программированию. Как решать задачи А, Е, К?

• +35

 » 5 years ago, # | ← Rev. 9 →   +11 A Let's compute answer for vertex v. We can visit an associative vertex u like this: Firstly go some steps using given edges, after that go using reversed edges. So Dfs(vertex, isReversed) will work perfect here. From isReversed = false we can go to isReversed = true, but not in other way.CodeK, dynamic programming and meet in the middle divide and conquerSorry that I am in english.
•  » » 5 years ago, # ^ |   +11 Can you explain in more details problem K?
•  » » » 5 years ago, # ^ | ← Rev. 6 →   +13 K dp(i, j) — first i keys are assigned, and we have covered first j alphabets. dp(i, j) = min dp(i-1, k) + cost(k+1, j) Let's denote optK(i, j) — optimal k that gives for us minimum. We can prove that, optK(i, j) <= optK(i, j + 1)let's calculate recursively calc(i, l..r, optKl, optKr). Firstly, we can calculate dp(i, mid), then recursively solve for calc(i, l..mid, optKl, opt(i, mid)) and calc(i, mid+1..r, opt(i,mid), optKr)).
•  » » » » 5 years ago, # ^ |   +1 321E - Ciel и гондолы also can be solved using this trick
•  » » » 5 years ago, # ^ | ← Rev. 4 →   +5 Also, you can use convex hull optimization. Lets dp(i,j) — first i keys are assigned, and we have covered first j alphabets. dp(i, j) = min dp(i — 1, k - 1) + cost(k, j) Lets sum(i,j) = a[i] + .. + a[j]. dp(i,j) = min(dp(i-1,k-1) + cost(1,j) - cost(1,k-1) - (k - 1) * (sum(1,j) - sum(1,k-1)) dp(i,j) = min(m[k] * sum(1,j) + c[k]) + cost(1,j) . Where m[k] = - (k - 1) and c[k] = dp(i-1,k - 1) - cost(1,k-1) + (k-1) * sum(1,k-1). Code
•  » » 5 years ago, # ^ |   0 K can be done by dp with a convex hull trick.
•  » » 5 years ago, # ^ |   0 I would call it "divide and conquer" rather than "meet in the middle".
•  » » » 5 years ago, # ^ |   +8 Indeed, thanks.
{"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 0, "mathjax_display_tex": 0, "mathjax_asciimath": 1, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0, "katex": 0, "math-container": 0, "wp-katex-eq": 0, "align": 0, "equation": 0, "x-ck12": 0, "texerror": 0}