USACO Stamp Painting (January 2018)

Notice that any integer sequence of length N where K elements are the same, this is a valid painting; Bessie can use her last stamp on the consecutive K elements and then incrementally work outwards (that is, backwards)..

It's easier to use complementary counting - we wish to find the # of sequences such that there exists NO K elements that are the same.

So, here's an unoptimized DP equation that is over N:

dp(n)=(M−1)⋅∑c=1K−1dp(n−c).

Notice that if this recurrence equation is being called on a value of N that is less than K, dp(n) = M^N. This is very important for our optimization.

However, this is effectively O(NK), which only gets 3/4 credit.

Let us make another different DP equation, S, defined as:

s(n)=∑ni=1dp(n)a

Hence, dp(n) = s(n)-s(n-1), so s(n)−s(n−1)=(M−1)(s(n−1)−s(n−K)),or s(n)=Ms(n−1)−(M−1)s(n−K).

But wait! Remember that dp(n) = M^N if n is less than K? That means that s(n) =M^1+M^2+...M^N, or s(n) = s(n-1)*M+M.

This is very important for initializing DP!

Code:

[to be added]

.
Bs(n)=∑n
Bi=1dp(n)as(n)=∑ni=1dp(n)aqaaa∑ni=1dp(n)
s(n)=∑ni=1dp(n) s(n)=∑ni=1dp(n)