PROBLEM LINK:
Author:
Tester: Jingbo Shang
Editorialist: Jingbo Shang
DIFFICULTY:
Easy-Medium
PREREQUISITES:
Dynamic Programming, Fast Matrix Power
PROBLEM:
You are asked to divide N slots to 3 people, A, B, and C. The number of slots allocated to A should be a multiple of k. There should be no consecutive slots for B. C should have at least one slot.
EXPLANATION:
General Idea
As k is small, we can use the following states to record the number of plans.
F[i][a][b][c] stands for the number of plans of allocated i slots to A, B, and C, where the number of slots of A mod k is a; b is a Boolean variable indicating whether B has the i-th slot; c is also a Boolean variable indicating whether C already has a slot.
Transitions are nearly obvious by considering the owner of (i+1)-th slot.
However, this bruteforce dynamic programming leads to an O(Nk) running time.
It is worth noting that the transitions are all between F[i][*] and F[i+1][*], and the operations are all multiplying come constants and summations. Therefore, we can get some intuitions to apply the fast matrix power to speed up the transitions. Finally, we get an algorithm with O(k^3 logN).
See more details in the author’s and tester’s solution for the fast matrix power algorithm if you are not familiar with that.
Corner Case
When k = 0, the number of slots allocated to A should be 0.
AUTHOR’S AND TESTER’S SOLUTIONS:
Solutions will be available soon.