pranjal.ssh's blog

SPOJ — COLORCAT
By pranjal.ssh, history, 9 years ago, In English

Hi, I am unable to solve the following problem. http://www.spoj.com/problems/COLORCAT/

I tried a few things like denoting the color change mathematically... the c1 and c2 colored cats talk to each other then their color changes to -(c1+c2) (mod 3) but it wasn't much useful.

Any hints or ideas are welcome.

  • Vote: I like it
  • +14
  • Vote: I do not like it

»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by pranjal.ssh (previous revision, new revision, compare).

→ Reply
»
9 years ago, # |
  Vote: I like it +14 Vote: I do not like it

I dont remember all the details but my solution went like this:

Let's represent colors of cats as vector v. As you noticed two cats talking and changing color can be described using linear equations. So let's find matrix M such that v multiplied by M equals vector of cat colors after one step. Thus colors after k steps are v*M^k. This yield O(n^3 log k) solution but one can notice that matrix M is special. It's something like: value of every cell thats not in first 2 rows and first 2 columns is equal to value of north-west neighbouring cell. So every matrix is characterized only by its first 2 rows and first 2 columns and it turns out that their multiplication is actually just a few convolutions which can be done using FFT in O(n log n) so total complexity becomes O(n log n log k).

→ Reply