editorial.pdf


Preview of PDF document editorial.pdf

Page 1 2 3 4 5 6 7 8 9 10 11

Text preview


Problem A
Let’s first solve a simpler problem – when the sequence 𝑐 is cyclic, i.
e. when 𝑐𝑖 = 𝑐𝑖 π‘šπ‘œπ‘‘ 𝑁 , for 𝑖 β‰₯ 0.
This simpler version is similar to Fibonacci sequence. Actually, for 𝑁 = 1
and 𝑐0 = 1, it is the Fibonacci sequence. To find the 𝐾 π‘‘β„Ž number of these
kind of recursive sequences fast we should first write them in their matrix
form. Matrix form of this sequence is:
𝐹
𝑐
𝑐
𝐹
( 𝑖 ) = ( π‘–βˆ’1 π‘–βˆ’2 ) ( π‘–βˆ’1 )
πΉπ‘–βˆ’1
πΉπ‘–βˆ’2
1
0
Expanding this, we can see that
𝐹
𝐹
𝑐 π‘π‘–βˆ’1
( 𝐾 ) = πΆπΎβˆ’1 πΆπΎβˆ’2 … 𝐢2 𝐢1 ( 1 ), where 𝐢𝑖 = ( 𝑖
).
πΉπΎβˆ’1
𝐹0
1
0
How do we calculate this efficiently?
For relatively small 𝐾, and we will take 𝐾 < 𝑁 for this case, we can
do
this
just
by
multiplying
all
the
matrices.
For large 𝐾 (𝐾 β‰₯ 𝑁), we will take advantage of the fact that 𝑐 is cyclic.
Since 𝑐 is cyclic with cycle of length 𝑁, we know that πΆπ‘βˆ’1 πΆπ‘βˆ’2 … 𝐢1 𝐢0 =
𝑐 𝑐
𝐢𝑖𝑁+(π‘βˆ’1) 𝐢𝑖𝑁+(π‘βˆ’2) … 𝐢𝑖𝑁+1 𝐢𝑖𝑁 , for 𝑖 β‰₯ 0 (note that 𝐢0 = ( 0 π‘βˆ’1 ) ).
1
0
Let’s define this product of matrices as 𝑆 = πΆπ‘βˆ’1 πΆπ‘βˆ’2 … 𝐢1 𝐢0 .
Now, we can write a formula for 𝐹𝐾 that can be calculated quickly:
𝐹𝐾
𝐹
(
) = πΆπ‘Žβˆ’1 πΆπ‘Žβˆ’2 … 𝐢1 𝐢0 𝑆 𝑏 πΆπ‘βˆ’1 πΆπ‘βˆ’2 … 𝐢2 𝐢1 ( 1 ), where 𝑏 = (𝐾 βˆ’
πΉπΎβˆ’1
𝐹0
𝑁) 𝑑𝑖𝑣 𝑁 and π‘Ž = 𝐾 π‘šπ‘œπ‘‘ 𝑁.
We can calculate 𝑆 𝑏 in 𝑂(π‘™π‘œπ‘”π‘) steps using exponentiaton by
squaring, and then we can just multiply everything in the expression to get
𝐹𝐾 quickly.
Let’s get back to the full problem, when 𝑐 is almost cyclic. In this
case, we cannot just use 𝑆 𝑏 in the formula above, because some matrices in
𝑆 𝑏 may not respect the cyclic property. Instead of 𝑆 𝑏 , we will have
something like
𝑆 βˆ™ 𝑆 βˆ™ … βˆ™ 𝑆 βˆ™ 𝐸1 βˆ™ 𝑆 βˆ™ 𝑆 βˆ™ … βˆ™ 𝑆 βˆ™ 𝐸2 βˆ™ … = 𝑆 𝑑1 βˆ™ 𝐸1βˆ™ βˆ™ 𝑆 𝑑2 βˆ™ 𝐸2 βˆ™ 𝑆 𝑑3 βˆ™ …
where 𝐸𝑖 denotes the product of matrices of the cycle, with some matrices
being different than the matrices of the original cycle. Also, 𝑖 ≀ 2𝑀 since