Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Rhombicosidodecahedron's blog

Can anybody help?
By Rhombicosidodecahedron, 5 years ago, In English

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.

  • Vote: I like it
  • -2
  • Vote: I do not like it

Comments Comments (6)
| Write comment?
»
5 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
← Rev. 5   Vote: I like it 0 Vote: I do not like it

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 stamp t: the last letter of t should be equal to the last letter of s.

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks!

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      With pleasure.

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      The following is another optimization to the code. The function string::substr() is called O(n) times only to compute suffixes of s starting at position k. Non-empty substrings are generated from these suffixes using O(n2) calls to the the function string::pop_back().

      47333814

      → Reply