aajjbb's blog

Jimi Hendrix — Petrozavodsk Winter Training Camp 2016
By aajjbb, history, 9 years ago, In English

Hi,

I'm having a hard time trying to figure out an efficient solution to problem J — Jimi Hendrix from Petrozavodsk Winter Training Camp 2016.

Do you guys have any tips ?

Thanks

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

»
9 years ago, # |
  Vote: I like it +6 Vote: I do not like it

It's a DP on tree problem.

To solve the problem, you need to calculate maximal number of symbols from prefix of string S you have visited on some path started somewhere in subtree of vertex V and ended in V and similarly for suffix (assume they are dp[v][0] and dp[v][1]).

Than, when you calculated this values for all children of some vertex V, you should check is there exists the path passing through the vertex V that is the answer, you need to check is there exists such two children ch1 and ch2 of vertex V, that dp[ch1][0] + f(edge(ch1, v)) + dp[ch2][1] + f(edge(v, ch2)) >= m, where f is 1 or 0, if this edge contains needed symbol of S or not. (Such two children can be found using prefix maximum of dp values)

And if you maintain vertices, where path for dp[v][0] and dp[v][1] starts, all the problem can be done using one simple DFS.

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

    Thanks for you answer, I tried something very similar, but somehow I tried to decompose the tree with centroids and go up-tree in O(log(n)) but it's pretty easy to see a counter to this idea.

    → Reply