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)**↵
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)**↵
