USACO Gold 2018 January - Stamp Painting

Problems and Contests
#1

In the problem Stamp Painting I found an O(log(n)), 1-liner formula that passes 10/12 cases (it fails on test cases 2 and 11).

    cout << (((n-k+1)*binpow(m,n-k+1)-(n-k)*binpow(m,n-k))%MOD+MOD)%MOD << "\n";

(binpow is binary exponentiation, and MOD = 1e9+7)

After some stresstesting, I’ve found that this formula works on roughly 75% of cases for random N, M, and K.

Because I guessed the formula, I’m not quite sure why it works (and why sometimes it doesn’t work). Can someone enlighten me?

Thanks in advance!

#2

It counts the number of maximal single-color segments with length at least K by counting the number of single-color segments of length exactly K and subtracting those of length exactly K+1. It only works when 2K>N (where a painting is valid if it has exactly one maximal single-color segment with length at least K).

Not sure where you got 75% from (unless you’re including K>N :wink: ). For some reason, K is close to N for most of the test cases …