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
# | User | Rating |
---|---|---|
1 | ecnerwala | 3649 |
2 | Benq | 3581 |
3 | orzdevinwang | 3570 |
4 | Geothermal | 3569 |
4 | cnnfls_csy | 3569 |
6 | tourist | 3565 |
7 | maroonrk | 3531 |
8 | Radewoosh | 3521 |
9 | Um_nik | 3482 |
10 | jiangly | 3468 |
# | User | Contrib. |
---|---|---|
1 | maomao90 | 174 |
2 | awoo | 164 |
3 | adamant | 161 |
4 | TheScrasse | 159 |
5 | nor | 158 |
6 | maroonrk | 156 |
7 | -is-this-fft- | 152 |
8 | SecondThread | 147 |
9 | orz | 146 |
10 | pajenegod | 145 |
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
Name |
---|
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.
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.