Temirulan's blog

Opencup — Grand Prix of Ukraine
By Temirulan, history, 9 years ago, In Russian

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

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

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

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.

Code

K, dynamic programming and meet in the middle divide and conquer

Sorry that I am in english.

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +11 Vote: I do not like it

    Can you explain in more details problem K?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 6   Vote: I like it +13 Vote: I do not like it

      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)).

      → Reply
    • »
      »
      »
      9 years ago, # ^ |
      ← Rev. 4   Vote: I like it +5 Vote: I do not like it

      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

      → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    K can be done by dp with a convex hull trick.

    → Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I would call it "divide and conquer" rather than "meet in the middle".

    → Reply