nnalove's blog

How to solve this problems?
By nnalove, history, 3 years ago, In English

I tried to solve the problem today, but I can't find any ideas? Can someone help me? Is there an issue similar to this one? https://vietnam-national20.kattis.com/problems/infinite2darray

  • Vote: I like it
  • -2
  • Vote: I do not like it

Comments Comments (8)
| Write comment?
»
3 years ago, # |
  Vote: I like it -7 Vote: I do not like it

You can simply calculate $$$F_{x, 0}$$$ firstly and then $$$F_{x, y}$$$ using the definition of $$$F$$$. This works in $$$\mathcal O(x+y)$$$ time. This can be brought down to $$$\mathcal O(\log x + \log y)$$$ time as we do in the Fibonacci sequence, however that is not required as the $$$\mathcal O(x+y)$$$ time should work fine.

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

    Can you explain how to compute $$$F_{x, y}$$$ from $$$F_{x, 0}$$$ in $$$O(y)$$$ using the definition?

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

With a help of binomial coefficients, maybe. This is matrix of B(i, j) calculated for F(4,5), same colors sum-up to the same number if every cell of this color is taken like SUM(F(i,j)*B(i,j)) — so you just choose the color that is easier to calculate — like border in matrix #5:

coefficients matrix
→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can u please elaborate more? I didn't understand your approach.

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

      Every cell (except border cells) is sum of left+top, so red-cell = sum(orange-cells) = sum(yellow-cells) = .. and so on, up to the border where they begin to overlap, so I pictured them on separate tables. And number of times each cell is taken correspond to binomial coefficients with root in F(x, y).

      → Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

To your question "Is there an issue similar to this one" I would point your attention to binomial coefficients. If you had $$$1$$$s instead of the Fibonacci Sequence on $$$F_{i,0}$$$ and $$$F_{0,i}$$$ then the diagonals $$$F_{i, k-i}$$$ would form the Pascal Triangle. The values of the Pascal Triangle correspond to binomial coefficients. Maybe this helps?

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

Let's number the diagonal the following way:

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

Let's, for example, compute the cell $$$(3, 4)$$$. If we put it in the grid, here is our answer coefficient:

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 1

And our coefficient is currently at the diagonal 7. But the definition, we can actually push the coefficients to the diagonal 6:

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 1
0 0 1 0

As well as to the diagonal 5:

0 0 0 0
0 0 0 0
0 0 0 1
0 0 2 0
0 1 0 0

So it is easy to see that our coefficient are sort of the binomial coefficients. So just push 1 more time:

0 0 0 0
0 0 0 1
0 0 3 0
0 3 0 0
1 0 0 0

Now we see if we push one more time, then the cell $$$(0, 4)$$$ might disappear. It isn't tho, because if we let the coefficient of the cell $$$(0, 3)$$$ be $$$1 + 3 = 4$$$, this means the value of $$$(0, 3)$$$ will contribute $$$1$$$ to cell $$$(0, 4)$$$ and $$$3$$$ to $$$(1, 3)$$$. But by the definition, beside the value of $$$(0, 3)$$$ is $$$Fib_3$$$, we also have $$$Fib_2$$$ (because value of $$$(0, 4)$$$ is $$$Fib_4$$$). Therefore we can left the coefficient of $$$(0, 4)$$$ be 1, but now instead of value $$$Fib_4$$$, use the value $$$Fib_2$$$. With the new value, our coefficient grid will be:

0 0 0 1
0 0 4 0
0 6 0 0
4 0 0 0
1 0 0 0

We can continue push the coefficients to the first row and column. After that we can just compute the Fibonacci numbers, multiply them by the corresponding coefficients, then summary them. Remember to use the new value (not $$$Fib_i$$$, but $$$Fib_i - Fib_{i - 1}$$$).

→ Reply