Greetings.
So I've been trying to solve this problem recently.
http://codeforces.com/gym/101745/problem/D
I want to for a fixed substring of s check whether it can stamp the string or not, but I fail to solve this after a few days.
I found the editorial:
https://codeforces.com/blog/entry/58135
But still can't understand the definition of DP for O(n^4) solution.
So can anybody help me and explain with more details here?
Thanks.
dp[i][j] says for fixed substring of s named t we want to make prefix of length i of s stamped and use prefix of length j of t in last part of prefix i of s
It's indeed quite hard to understand from the editorial.
d[i][j]
is true when we can color prefix [0, i - 1] such that the rightmost usage of a pattern occurs in such a place that first j cells of a pattern are used for this prefix (so they cover the last j cells of the prefix), and m - j cells are sticking out to the right of cell i.Check this slight C++17 update for the O(n4) tutorial solution.
47314861
An additional constraint is used to prune the O(n2) search space of all non-empty substrings of
s
for a valid stampt
: the last letter oft
should be equal to the last letter ofs
.You may also find the debug information of test case 2 in the following version helpful in tracing the DP algorithm.
https://ideone.com/vlT0YP
Thanks!
With pleasure.
The following is another optimization to the code. The function
string::substr()
is called O(n) times only to compute suffixes ofs
starting at position k. Non-empty substrings are generated from these suffixes using O(n2) calls to the the functionstring::pop_back()
.47333814