Solution for Timus 2019

Revision ru4, by andreyDagger, 2021-09-19 19:37:34

Hi Guys, Can anyone help me solve this problem?

https://acm.timus.ru/problem.aspx?space=1&num=2019&locale=en

I tried to solve it greedily. Also i tried to solve it using dynamic programming. I had dp[l][r] true if exists k such that dp[l][k] is true and dp[k + 1][r] is true or dp[l + k][r — k] is true and we can connect letters from range (l, l + k) to the letters from range (r — k, r). Unfortunately, that works for O(n^3)

Tags timus

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru4 Russian andreyDagger 2021-09-19 19:37:34 2 (опубликовано)
ru3 Russian andreyDagger 2021-09-19 19:36:42 15
ru2 Russian andreyDagger 2021-09-19 19:35:28 159
ru1 Russian andreyDagger 2021-09-19 19:32:38 332 Первая редакция (сохранено в черновиках)