Hello, Codeforces community!
I recently faced an interesting problem during a company online assessment, and I wanted to share it with you all. Unfortunately, I couldn't solve it, and I’m reaching out for your help.
Problem Description
You are given three integers: A,B,C. Your task is to count the number of possible arrays of size A that satisfy the following conditions:
- The elements in the array are chosen from the set {1, 2, ..., C}.
- The maximum size of any subarray containing identical elements is at most B.
Input
An integer A: the size of the array. (1<=A<=10^9)
An integer B: the maximum size of a subarray containing identical elements. (1<=B<=min(50,A))
An integer C: the maximum value for any element in the array (elements are chosen from {1, 2, ..., C}). (1<=C<=10^5)
Output
An integer representing the number of valid arrays.(Return the value modulo 1e9+7)
Example For A=3 , B=1 , C=3 the answer is 12 and the valid subarrays are [1, 2, 1], [1, 2, 3], [1, 3, 1], [1, 3, 2], [2, 1, 2], [2, 1, 3], [2, 3, 1], [2, 3, 2], [3, 1, 2], [3, 1, 3], [3, 2, 1], [3, 2, 3]
I am thinking of dp but how to handle such large A ? Is there any problem it could be reduced to ?
Auto comment: topic has been updated by anon223 (previous revision, new revision, compare).
looks like Trilogy OA, i guess few of my friends used dp and matrix exponentiation( To optimise ) to solve the question
can you explain the approach?
You can you matrix exponention to maintain 50 dp values.
Can you please elaborate
Probably this
Final answer would be $$$ \sum\limits _{i=1}^{B} dp[ A][ i]$$$
thanks got it
Does dp[i][j] mean number of valid sequence of length i with exactly last j elements repeating?
Yes
What's the complexity of this?
$$$O(B^3log(A))$$$
Damn this is new to me, the matrix is AxB, how did you get it be in log(A)? Is there a standard algorithm for it? If so, link plz
Huh? The matrices are Bx1 and BxB
mb BxB and A is is the exponent got it
Can someone estimate CF difficulty score for this problem?
Easily around 2200 to 2500
Probably 1900 or 2000 ish, but it's a standard one
it's 1500~1700 if you know matrix expo (otherwise it's basically impossible)
Isn't your estimate kinda low? I mean 2014H. Robin Hood Archery has a score of 1900 and people say it is a pretty standard application of XOR hashing technique. And XOR hashing is less advanced than optimizing DP via matrix exponentiation (at least according to USACO which lists XOR hashing as part of Gold tier and matrix expo as Platinum).
Problem difficulties across different divisions cannot be compared; most of the 1900+ Div 3/4 problems will be solved by most of the Div 2/1 coders, so it's not a 1900+, actually.
Are you saying that problem difficulty changes depending on contest division? For example the problem I mentioned is 1900 because it is from Div3 but if it were presented in Div2 it would have been assigned say 1500 difficulty rating?
actually yea (look at last div 1 + div 2) where solving A-Ddiv1 in abt 2 hours is master perf in div1 but gm perf in div2 (which is C-F which is basically A-F) (according to carrot which may or may not be accurate)
https://pastebin.com/T0jvDyjZ — Implementation of Brute 2D DP and a faster Matrix Exponentiation
How many ways to break stick of length A into pieces of length <=B?
This is a linear recurrence, so compute in $$$O(B^3 \log N)$$$ using matrix exponentiation.
And how many ways to do it if we must also paint each piece of a color between 1 and C-1 (C-1 to ensure each piece has a different color than the previous one)?
This is still a linear recurrence, so we evaluate it using the same strategy.
Note that the first stick can be painted in any of C colors, not C-1, so the result is
Dp(A)*inv(C-1)*C