lelbaba's blog

By lelbaba, history, 17 months ago, In English

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 - Сжатие массива

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 - Удаляем подпоследовательности

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 и строки

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 и магическое заклинание

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 - Восстановление 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
Code

I am done for today. I hope this benefits whoever is reading. Also feel free to correct any mistakes you might have found.

Full text and comments »

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

By lelbaba, history, 22 months ago, In English

Hi everyone. I have been getting into abstract algebra out of interest and recommendation. When I read about permutations and their cyclic decomposition from group theory perspective, I have been trying to find other objects or common problems that often come up in competitive programming and can be viewed through the lens of group theory in a different perspective. So far I have only found burnside's lemma for counting problems. I am also looking for problems that may be simplified through isomorphism or other concepts that are fundamental in group theory. The ones I did find seem to be way out of my league :(

Full text and comments »

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