anon223's blog

Counting Valid Arrays from a Company OA
By anon223, history, 6 weeks ago, In English

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 ?

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

»
6 weeks ago, # |
  Vote: I like it +3 Vote: I do not like it

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

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

looks like Trilogy OA, i guess few of my friends used dp and matrix exponentiation( To optimise ) to solve the question

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

You can you matrix exponention to maintain 50 dp values.

→ Reply
»
6 weeks ago, # |
← Rev. 2   Vote: I like it +34 Vote: I do not like it

Probably this

$$$ \begin{array}{l} \begin{bmatrix} dp[ i][ 1]\\ dp[ i][ 2]\\ \vdots \\ \vdots \\ dp[ i][ B] \end{bmatrix} =\begin{bmatrix} C-1 & C-1 & C-1 & \cdots & C-1\\ 1 & 0 & 0 & \cdots & 0\\ 0 & 1 & 0 & \cdots & \vdots \\ \vdots & \ddots & \ddots & 0 & \vdots \\ 0 & \cdots & 0 & 1 & 0 \end{bmatrix} .\begin{bmatrix} dp[ i-1][ 1]\\ dp[ i-1][ 2]\\ \vdots \\ \vdots \\ dp[ i-1][ B] \end{bmatrix}\\ \end{array} $$$

Final answer would be $$$ \sum\limits _{i=1}^{B} dp[ A][ i]$$$

→ Reply
»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Can someone estimate CF difficulty score for this problem?

→ Reply
  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    Easily around 2200 to 2500

    → Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Probably 1900 or 2000 ish, but it's a standard one

    → Reply
  • »
    »
    5 weeks ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    it's 1500~1700 if you know matrix expo (otherwise it's basically impossible)

    → Reply
    • »
      »
      »
      5 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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).

      → Reply
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          5 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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?

          → Reply
          • »
            »
            »
            »
            »
            »
            5 weeks ago, # ^ |
            ← Rev. 2   Vote: I like it 0 Vote: I do not like it

            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)

            → Reply
»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

https://pastebin.com/T0jvDyjZ — Implementation of Brute 2D DP and a faster Matrix Exponentiation

→ Reply
»
5 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

How many ways to break stick of length A into pieces of length <=B?

Dp(0)   = 1
Dp(A>0) = sum of Dp(A-k) for k=1..min(A,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)?

Dp(0)   = 1
Dp(A>0) = sum of (C-1)*Dp(A-k) for k=1..min(A,B)

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

→ Reply