Thank you, you're right. I was thinking about this simple DP yesterday but couldn't figure it out. At the same time, my teammate pressured me to work on the data structure, so I ended up being forced to write some mindless advanced algorithms.

• Consider adjacent words $$$s[i,j],s[j+1,k]$$$.It should be $$$s[i,j] \lt s[j+1,k]$$$,you can see that the valid $$$k$$$ is an interval, or more accurately, a suffix.Define $$$k_{mn}$$$ as the minimum value of $$$k$$$.Define $$$dp_{i,j}$$$ as the maximum number of words with the first $$$i$$$ characters ending in $$$s[i, j]$$$.You can see $$$dp_{i,j}$$$ can update $$$dp_{j+1,k}$$$ with a time complexity of $$$O(1)$$$ using suffix marking.
• You can use $$$exkmp$$$(aka.$$$Z\;function$$$),$$$suffix\;array$$$ or others to calculate $$$k_{mn}$$$ quickly.
• Forgive my Chinglish.

Problem F's "Fact 4",You should specify that s'1 and s'2 have the same number of 1s , otherwise your statement is wrong.

s1=1000011 s2=1000100 k-1=2 s'1=1001111 s'2=1000111 s1 < s2 and s'1 > s'2

How to solve F? The solution is difficult to understand.

sorry,zxyoi.

Thank you,you are great!

Why does the solution say that $$$[1,2 * i - 1]$$$ and $$$[2 * i,n]$$$ are independent in problem E?

How to solve F? What is the relationship between this problem and Stirling number?

How to solve D?

Can you prove 1D about this common solution,thanks?