Блог пользователя nnalove

Автор nnalove, история, 3 года назад, По-английски

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

  • Проголосовать: нравится
  • -2
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

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

»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

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
  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

»
3 года назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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?

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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