typedeftemplate's blog

By typedeftemplate, history, 5 years ago, In English

Suppose you want to construct sequences from the restricted alphabet {1, 2, 3, 4, 5, 6}. However, you cannot place the number i (i = 1, 2, 3, ... 6) more than A[i] times consecutively, where A is a given array. Given the sequence length 1 <= N <= 10^5 and the array A with 1 <= A[i] <= 50, how many possible sequences are possible?

For example, suppose A = {1, 2, 1, 2, 1, 2} and N = 2. In this case, there can only be one consecutive 1, two consecutive 2's, one consecutive 3, etc. So in this example, something like "11" would be invalid, but something like "12" or "22" would be valid. It turns out that there are actually 33 possible sequences in this case (namely, two-digit sequence except for "11", "33", and "55").

I was wondering how I can solve this problem? Initially, I tried to use a DP approach, but I have been thinking there might be a clever combinatoric strategy. Like, in the example I showed above, it's pretty quick to just do complementary counting. It gets really messy when I try to work it out for larger cases though. I've also tried to use inclusion-exclusion and got nowhere.

Another thing I noted is that A[i] is pretty small, but I wasn't able to get anywhere with that observation.

I would greatly appreciate some help in solving this problem. It might just be a really easy combinatorics problem. I am really bad at that topic, so I wouldn't be surprised if is just something I am not seeing.

Thanks.

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

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

$$$dp(i, j, k)$$$: $$$i$$$ is the current index of the sequence you are building, $$$j$$$ is the element put in the position $$$i - 1$$$ and $$$k$$$ is the number of times this element has been repeated in the last block. For transitions, you can put in position $$$i$$$ every element different from $$$j$$$ and you can only put $$$j$$$ in $$$i$$$ if $$$k < A[j]$$$.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it -6 Vote: I do not like it

    Oh wow, that is really clever. But I am having some difficulty actually implementing this. You say that position i can have every element different from j, but how would we tell what j actually is? Because I thought j can take on different values depending on the sequence. Sorry, I am pretty new to DP. I can show you some real code I have tried soon

    Also, how do you get TeX to work in comments?

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Also, how do you get TeX to work in comments?

      By writing in $$$\TeX$$$.

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 3   Vote: I like it +5 Vote: I do not like it

        Ok, I figured it out. $$$Thanks$$$.

        I am pretty new to DP, and I'm still struggling with the implementation portion of this. I'm declaring a 3D matrix dp[100005][6][50] to follow what fofao_funk is saying, but I have really no clue how to get started. I've also read the DP part of CLRS, and I still can't manage to figure this out.

        Could you please show me the setup for this problem? I've been stuck on this particular problem for a few days now, while I am able to easily solve some of the simpler problems. I would like to eventually be able to solve DP problems on my own, but this sort of problem is difficult for me.

        I think I am especially confused since there are 3 dimensions.

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          Rev. 8   Vote: I like it +2 Vote: I do not like it

          Okay, let's try. Consider the following fact: $$$dp[i][j][k]$$$ is how many valid sequences exist, such that their length is $$$i$$$, last number is $$$j$$$, and it has been repeated $$$k$$$ times in the suffix.

          First off, if $$$k > A[j]$$$, i.e. for example we're looking at $$$dp[12][4][3]$$$ from your input. Now, how many such valid sequences exist? Obviously 0, since by our input we cannot write more than two consecutive "4"-s (and moreover, our $$$N = 2$$$).

          Okay, for the sake of convenience, let's now consider some other input that allows taking bigger sequences of equal numbers and asks for greater length sequences, so that $$$dp[12][4][3]$$$ is valid.

          Secondly, how can we get that $$$dp[12][4][3]$$$? Remember, it means the number of sequences of length 12 that end in exactly three "4"-s. But hey, every such sequence is made in the following fashion: we take a sequence of 11 elements with exactly two consecutive "4"-s in the end and append one "4" to the end! So there are as many $$$dp[12][4][3]$$$-s as there are $$$dp[11][4][2]$$$-s! Observation 1: $$$dp[i][j][k]$$$ = $$$dp[i - 1][j][k - 1]$$$ for valid combinations of $$$j$$$ and $$$k$$$, except...

          We forgot to take one important case into consideration, though. What if our last number is repeated only one time in the end, i.e. $$$dp[i][j][1]$$$? How can we get all such sequences? Well, we could append $$$j$$$ to any sequence of length $$$i - 1$$$, except for those that end with $$$j$$$ — because then we would have more than one repeating last symbol! Observation 2: $$$dp[i][j][1]$$$ = sum over all $$$dp[i - 1][m][n]$$$, where $$$m \ne j$$$.

          Now try to combine these two observations into a correct algorithm. I might have missed a couple of things, but on the whole I think it is right.

          Code (answers will get big real quick, so you'll have to count modulo something in the process to keep it meaningful)
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Link to the problem?

  • »
    »
    5 years ago, # ^ |
    Rev. 4   Vote: I like it +1 Vote: I do not like it

    As far as I know, it is not an official problem from a contest or anything. I learned about this problem by word of mouth