Some Interval DP Problems and State Reduction

Revision en49, by lelbaba, 2022-11-10 15:01:42

Hi everyone! Recently I have been solving some classic interval DP problems, and came across some neat problems. Most of these problems have relatively simple recurrence relations, but the straightforward solutions will not pass in complexity, hence requires an observation to reduce the complexity (generally by reducing the number of states by some pre-computation). Most of the problems are from CF, and they already have editorials. But I will still write my own tutorials to illustrate my points.

Prerequisites : Introductory interval DP such as Longest Increasing Subsequence, Longest Common Subsequence.

1312E - Array Shrinking

You are given an array of $$$a_1,a_2,\dots,a_n$$$ length $$$n \ (n \leq 500, 1 \leq a_i \leq 1000).$$$ You can perform the following operation any number of times:

  • Choose a pair of two neighboring equal elements $$$a_i=a_{i+1}$$$ (if there is at least one such pair).
  • Replace them by one element with value $$$a_i + 1$$$. After each such operation, the length of the array will decrease by one (and elements are renumerated accordingly). What is the minimum possible length of the array a you can get?
Solution
Code

1303E - Erase Subsequences

Given two strings $$$s$$$ and $$$t$$$ ($$$|t| \leq |s| \leq 400$$$, we need to tell whether two disjoint subsequences of $$$s$$$ can be concatenated to create t.

Hint
Solution
Code

476E - Dreamoon and Strings

Given a string $$$s$$$ and another string $$$p$$$, you need to find maximum number of non-overlapping substrings of $$$s$$$ that are equal to $$$p$$$ after deleting $$$x$$$ characters from $$$s$$$ for all $$$x \in [0, |s|]$$$. ($$$|s| \leq 2000, |p| \leq 500$$$).

Solution
Code

1337E - Kaavi and Magic Spell

You are given a string $$$s$$$ of length $$$n$$$ and another string $$$t$$$ of length $$$m$$$ ($$$1 \leq m \leq n \leq 3000$$$). Initially you have an empty string $$$a$$$. In one operation, you can take the first character of $$$s$$$ and either prepend or append it to $$$a$$$ and erase it from $$$s$$$. After at-most $$$n$$$ operations, in how many different sequence of operations can you create $$$a$$$ such that it has $$$t$$$ as a prefix (modulo $$$998244353$$$).

Hint
Solutions
Code

1025D - Recovering BST

Given a sorted array $$$a$$$ of length $$$n$$$ ($$$n \leq 700$$$), you need to tell if it is possible to create a binary search tree of that array such that no two adjacent nodes are coprime.

Hint
Solution
Tags dynamic programming, intervals, tutorial

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en50 English lelbaba 2022-11-10 16:10:07 1209 (published)
en49 English lelbaba 2022-11-10 15:01:42 2223
en48 English lelbaba 2022-11-10 12:54:16 22
en47 English lelbaba 2022-11-10 12:49:56 3580
en46 English lelbaba 2022-11-10 12:26:40 14
en45 English lelbaba 2022-11-10 12:22:40 36
en44 English lelbaba 2022-11-10 12:18:22 20
en43 English lelbaba 2022-11-10 12:16:59 881
en42 English lelbaba 2022-11-10 12:14:13 1357
en41 English lelbaba 2022-11-10 10:57:02 1313
en40 English lelbaba 2022-11-08 16:11:57 4
en39 English lelbaba 2022-11-08 16:11:22 1314
en38 English lelbaba 2022-11-08 15:27:56 221
en37 English lelbaba 2022-11-08 15:20:41 71
en36 English lelbaba 2022-11-08 15:13:23 11
en35 English lelbaba 2022-11-08 15:12:32 1262
en34 English lelbaba 2022-11-08 14:45:23 777
en33 English lelbaba 2022-11-08 14:18:25 70
en32 English lelbaba 2022-11-08 14:16:32 49
en31 English lelbaba 2022-11-08 14:13:37 121
en30 English lelbaba 2022-11-08 14:11:03 188
en29 English lelbaba 2022-11-08 13:58:38 58
en28 English lelbaba 2022-11-08 13:57:19 5 Tiny change: '$f_{i,j,k} denote wh' -> '$f_{i,j,k}$ denote wh'
en27 English lelbaba 2022-11-08 13:56:26 921
en26 English lelbaba 2022-11-08 11:12:27 2 Tiny change: 'elation,\n\n$f_{l,l}' -> 'elation,\n$f_{l,l}'
en25 English lelbaba 2022-11-08 11:11:52 2 Tiny change: 'elation,\n$f_{l,l}' -> 'elation,\n\n$f_{l,l}'
en24 English lelbaba 2022-11-08 11:10:41 4 Tiny change: 'elation,\n\n$f_{l,l} = a_l$\n\n$f_{l,r}' -> 'elation,\n$f_{l,l} = a_l$\n$f_{l,r}'
en23 English lelbaba 2022-11-08 11:09:46 4
en22 English lelbaba 2022-11-08 11:09:08 5
en21 English lelbaba 2022-11-08 11:07:39 4
en20 English lelbaba 2022-11-08 11:05:47 1 Tiny change: 'rations.\n\n<spoiler' -> 'rations.\n<spoiler'
en19 English lelbaba 2022-11-08 11:04:51 2 Tiny change: 'i} + 1)$\nNote: $[' -> 'i} + 1)$\n\nNote: $['
en18 English lelbaba 2022-11-08 11:03:12 22 Tiny change: 'dp_1 = 1.$\n</spoile' -> 'dp_1 = 1.$ $dp_n$ is our answer.\n</spoile'
en17 English lelbaba 2022-11-08 11:01:56 18 Tiny change: '+ f_{j,i}$\n</spoil' -> '+ f_{j,i}$ where $dp_1 = 1.$\n</spoil'
en16 English lelbaba 2022-11-08 10:59:52 2 Tiny change: 'j \leq i, f_{j,i} \' -> 'j \leq i, \ f_{j,i} \'
en15 English lelbaba 2022-11-08 10:59:09 4 Tiny change: 'i} \ne 0} dp_{j-1} ' -> 'i} \ne 0} \ \ dp_{j-1} '
en14 English lelbaba 2022-11-08 10:58:27 237
en13 English lelbaba 2022-11-08 10:41:39 4 Tiny change: 'relation, //\n$f_{l,l}' -> 'relation, \\\n$f_{l,l}'
en12 English lelbaba 2022-11-08 10:41:09 76
en11 English lelbaba 2022-11-08 10:38:21 2 Tiny change: '{l,i} + 1)\n</spoile' -> '{l,i} + 1)$\n</spoile'
en10 English lelbaba 2022-11-08 10:37:57 158
en9 English lelbaba 2022-11-08 10:24:51 5
en8 English lelbaba 2022-11-08 10:22:29 233
en7 English lelbaba 2022-11-08 10:18:02 292
en6 English lelbaba 2022-11-08 09:37:52 9 Tiny change: 'ed to.\n\n#### Claim\nIf the s' -> 'ed to.\n\n**Claim**\nIf the s'
en5 English lelbaba 2022-11-08 09:36:52 305
en4 English lelbaba 2022-11-08 09:08:05 63
en3 English lelbaba 2022-11-08 09:03:16 98
en2 English lelbaba 2022-11-08 08:28:51 65
en1 English lelbaba 2022-11-08 08:19:37 1038 Initial revision (saved to drafts)