Dynamic programming

[theKlaw]

https://cses.fi/problemset/task/1746

I have thought of this question for a while now, can't really see the subproblems for DP, brute force will surely give a timeout. I think the main problem is if unknown elements are in a row, for eg 2 3 0 0 0 0 4, then there could be many possibilities.

[Handy Andy]

Hello theKlaw,

Yes there could be several possibilities, but do to the constraints of the program it is a finite number.

A quick work with two inputs I came up with:

arraySize = 3 maxValue = 5
2 0 2 Starting numbers with max number being 5.

2 1 2
2 2 2
2 3 2

arraySize = 4 maxValue = 5
2 0 0 2 Starting numbers with max number being 5.

2 1 1 2
2 1 2 2
2 2 1 2
2 2 2 2
2 3 2 2
2 3 3 2

As you can see by the constraint of "difference between two adjacent values is at most 1" this limits the number of possibilities. Also the "maxValue" or 5 also figures into what you can use, but in these examples 4 and 5 can not be used.

Now when you write your program the variable names of 'n' and 'm' may seem easy to use, but do not. Variable like "arraySize" and "maxValue" will have more meaning in the code and make it easier for you and other to understand.

The next step is to post the code you have so far so everyone can see what you have done and can comment on where you have any problems.

Hope that helps,

Andy

[theKlaw]

So, you think I should put values at the unknowns from their adjacent-1 to m and check for each position?? or do I need to come up with a formula, like combinatorics?

I think, I know what to do, if the unknown is in between 2 known values, then it's simple, but the problem to me arises in a row of unknowns

Also maxValue is only useful if the row of unknowns starts from intial position or ending, other than that I don't see much use of it, e.g,

0002 then 5 4 3 2, but if we have 3 0 0 0 2 then I can only use 2,3,4 in first place, 1,2,3,4 in 2nd and 1,2,3 in third


Also in your example, arraySize=4 maxValue=5
2 0 0 2.
you missed one case:
2 2 3 2

[Handy Andy]

Hello theKlaw,

Yes. Only when you give the unknown a value can you know if it is a usable choice. Although I have heard about "combinatorics" I am not familiar with it, so I not sure how it would work.

Since you only work with two elements at a time you only have three choices, one less, the same and one more. After you change the unknowns you can check that it meats the conditions of the instructions ans count it as a usable choice.

Unless I misunderstood, "maxValue" is the largest value for a given unknown. I do realize that in a small array this may not be used unless the some of the numbers that are known are large enough to use "maxValue", but in larger arrays it will be used to limit what can be put into an unknown value. e.g., (0 5 0), the first number can only be 4 or 5, but not 6.

Sorry I missed a case, but I did say that I did it quickly. My attempt was to give you an idea to look at.

Hope that helps,

Andy

[theKlaw]

But, see here's my doubt you say we need to give the unknown value and check if it meets the condition. but for a large array with a lot of unknowns, don't you think, this would perform very poorly, I mean we not necessarily only see two elements
for eg. 3 0 0 0 0 0 0 0 0 2 (m=4)

how to check one by one , in this case?

first unknown: [2,3,4]
2nd unknown: now, i have to see for 2,3 and 4 separately,
3rd unknown: now, I have to see for the results of each previous separately, and so on.

I just can't wrap my head around how to deal with this with good performance i guess..

btw combinatorics, is just simply, using combinations, or permutations to find the total count.. like finding a pattern maybe..

[dutch]

I disagree with Andy, who seems to be suggesting a brute force approach.

Consider this input:

  5 0 0 0 0 0 7

Solutions can be thought of as paths from level 5 to level 7 across the following grid:

3 . . X . . . .
4 . X . X . . .
5 X . . . X . .
6 . X . . . X .
7 . . X . . . X
8 . . . X . X .
9 . . . . X . .

I've marked the "upper" and "lower" paths. All other paths must be inside those. So you need to figure out how to count those paths.

The overall answer is the product of the path counts for all runs of 0's (modulus 1000000007).

Note that if m was, e.g., 7, then it would be like this:

3 . . X . . . .
4 . X . X . . .
5 X . . . X . .
6 . X . . . X .
7 . . X X X X X

Also note that there is a special case where the given array starts and/or ends in zeroes.

   0 0 0 0 0 6

 1 X . . . . .
 2 . X . . . .
 3 . . X . . .
 4 . . . X . .
 5 . . . . X .
 6 . . . . . X
 7 . . . . X .
 8 . . . X . .
 9 . . X . . .
10 . X . . . .
11 X . . . . . (assuming m is at least 11)

[dutch]

Did you get it? I need to make a correction on my example. When I had only looked at the problem for a few minutes I had guesssed that the number of paths from left to right in the following example is 27. When I figured out the algorithm, however, it turns out that it's 90.

3  .  .  X  .  .  .  .
4  .  X  .  X  .  .  .
5  X  .  .  .  X  .  .
6  .  X  .  .  .  X  .
7  .  .  X  .  .  .  X
8  .  .  .  X  .  X  .
9  .  .  .  .  X  .  .

This one, corresponding to an input of 3 0 0 0 0 0 0 0 0 0 0 3, has 23376 paths from left to right.

1 . . X X X X X X X X . .
2 . X . . . . . . . . X .
3 X . . . . . . . . . . X
4 . X . . . . . . . . X .
5 . . X . . . . . . X . .
6 . . . X . . . . X . . .
7 . . . . X . . X . . . .
8 . . . . . X X . . . . .

I should make it clear that you don't really need to make a little grid like that to solve it. All you need is a couple one-dimensional arrays of ints to hold the count of the number of paths to the points in a particular column.

[theKlaw]

No, I was trying to get the grid layout and solve it that way, but I am completely lost now :(

When you say I need couple of ints of 1D array, is that number fixed?

[dutch]

You need to calculate the number of ways to go from 5 to 7 in 5 0 0 0 0 0 7.

There is 1 way to get to the 5 at the beginning (you simply start there).

How many ways are there to get to the possibilities in the next column? The possibilities for the second column are 4, 5, and 6. There is 1 way to get to each of them: 5->4, 5->5, and 5->6, respectively.

The next 0 could be anything from 3 to 7. How many ways are there to get to the 3 at that point? Only 1: 5->4->3. But to get to 4 there are 2 ways: 5->4->4 or 5->5->4. To get to the 5 there are 3 ways: 5->4->5, 5->5->5, and 5->6->5. And so on.

That's what you want to calculate, but it so happens that to calculate the numbers for a particular column, all you need are the numbers from the previous column since the number of ways to get to a certain point is simply the sums of the number of ways to get to the points in the previous column that could have led to the current point.

So you only need two arrays, one for the the previous column and one for the current column.

Here's all the numbers filled in for 5 0 0 0 0 0 7:

   5  0  0  0  0  0  7
   a  b  c  d  e  f  g
3  .  .  1  .  .  .  .
4  .  1  2  6  .  .  .
5  1  1  3  7 19  .  .
6  .  1  2  6 16 45  .
7  .  .  1  3 10 30 90
8  .  .  .  1  4 15  .
9  .  .  .  .  1  .  .

Two more examples:

      3     0     0     0     0     0     0     0     0     0     0     3
      a     b     c     d     e     f     g     h     i     j     k     l
1     .     .     1     3     9    25    69   189   518  1422     .     .
2     .     1     2     6    16    44   120   329   904  2493  6898     .
3     1     1     3     7    19    51   140   386  1071  2983  8338 23376
4     .     1     2     6    16    45   126   356  1008  2862  8140     .
5     .     .     1     3    10    30    90   266   783  2295     .     .
6     .     .     .     1     4    15    50   161   504     .     .     .
7     .     .     .     .     1     5    21    77     .     .     .     .
8     .     .     .     .     .     1     6     .     .     .     .     .

       0     0     0     0     0     6
       a     b     c     d     e     f
 1     1     .     .     .     .     .
 2     1     3     .     .     .     .
 3     1     3     9     .     .     .
 4     1     3     9    27     .     .
 5     1     3     9    27    81     .
 6     1     3     9    27    81   243
 7     1     3     9    27    81     .
 8     1     3     9    27     .     .
 9     1     3     9     .     .     .
10     1     3     .     .     .     .
11     1     .     .     .     .     .

Note that this last case (that the sequence starts with 0's) is simple since the answer is 3 to the power of the number of zeroes. It makes one wonder if there is a mathematical formula for the other cases. I don't know. I could only think of this dynamic programming solution.

[theKlaw]

Thank you so much for such detailed answer, I understand now, how to calculate the total count by only using 2 arrays, is there any way to know the upper limit and lower limit of each zero, like can I tell that on the spot, while scanning that zero?

Or I need to know the range from start zero to last zero and work my way backwards?

Like in 3 0 0 0 0 0 0 0 0 0 0 3

I know 1st zero and last zero can have 2,3,4 and then work my way till the middle?? then use these again to calculate the values, or can I know the upper and lower limit while scanning?

[dutch]

Basic shape is a rhombus.

       a
       * *
     *     *
s  *         *
     *         *
       *         *
e        *         *
           *     *
             * *
               b

#include <iostream>

void calc(int s, int z, int e) { // start, zeroes, end
    // Assuming neither s nor e are 0.
    // I'm also ignoring the limits (1 and m).

    // if s > e they can be swapped since it makes no difference in the count
    if (s > e) std::swap(s, e);

    // w is the amount that the rhombus extends above s and below e    
    int w = (z - (e - s - 1)) / 2;
    int a = w;           // upper "point" (could forgo a and just use w)
    int b = z + 1 - w;   // lower "point"

    std::cout << s << '\n';
    for (int c = 1; c < z + 1; ++c) {
        int lo = (c > a) ? e - (z + 1 - c) : s - c;
        int hi = (c < b) ? s + c           : e + (z + 1 - c);
        std::cout << lo << " to " << hi << '\n';
    }
    std::cout << e << '\n';
}

int main() {
    for (;;) {
        int start, zeroes, end;
        std::cout << "start zeroes end: ";
        std::cin >> start >> zeroes >> end;
        calc(start, zeroes, end);
    }
}

I should say that I have not actually solved this problem in the sense of writing a program to pass the tests on that site. I only wrote a program to produce those figures in my previous post, which I feel proves the concept (first worked out on paper). So I have not worked out the messy details of the full program.

EDIT: Just checking back. I said "rhombus" above, but they are really just rectangles at 45 degrees, possibly with flattened upper and lower points.

The algorithm I came up with here is based on seeing the figure as two intersecting 90 degree angles.

   *   a     *
     *     *
       * *
       * *
     *     *
s  *         *
     *         *
       *         *
e        *         *
           *     *
             * *
             * *
           *     *
         *     b   *

a and b indicate the columns where you switch from one angle to the other.