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

# | User | Rating |
---|---|---|

1 | tourist | 3821 |

2 | Benq | 3744 |

3 | ksun48 | 3559 |

4 | Radewoosh | 3538 |

5 | peehs_moorhsum | 3531 |

6 | Um_nik | 3488 |

7 | maroonrk | 3423 |

8 | Petr | 3379 |

9 | sunset | 3337 |

10 | ecnerwala | 3335 |

# | User | Contrib. |
---|---|---|

1 | 1-gon | 206 |

2 | awoo | 181 |

2 | Errichto | 181 |

4 | Um_nik | 180 |

5 | -is-this-fft- | 175 |

6 | maroonrk | 174 |

7 | Radewoosh | 173 |

8 | tourist | 172 |

9 | SecondThread | 171 |

10 | rng_58 | 166 |

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

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jul/26/2021 20:51:37 (f1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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.

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

My bad, I misread the question.

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

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

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

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?

Let's number the diagonal the following way:

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

coefficient:And our

coefficientis currently at the diagonal 7. But the definition, we can actually push thecoefficientsto the diagonal 6:As well as to the diagonal 5:

So it is easy to see that our

coefficientare sort of the binomial coefficients. So just push 1 more time: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: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}$$$).

Thanks you so much. Sorry for my late.