I was trying this problem from SPOJ: http://www.spoj.com/problems/LVADER/en/. I figured out the recurrence for the problem which is f(x, y) = f(x — 1, y) + f(x, y — 1) + f(x — 1, y — 1), f(x, 0) = f(0, y) = 1. The constraints of the problem does not allow me to use normal DP and I'm not aware how to use matrix exponentiation technique for 2-D recurrence. I read this article: https://threads-iiith.quora.com/Solving-Dynamic-Programming-with-Matrix-Exponentiation but I could not fully understand the idea. Any help is really appreciated.
→ Обратите внимание
До соревнования
Codeforces Round 940 (Div. 2) and CodeCraft-23
3 дня
Зарегистрироваться »
Codeforces Round 940 (Div. 2) and CodeCraft-23
3 дня
Зарегистрироваться »
*есть доп. регистрация
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | ecnerwala | 3648 |
| 2 | Benq | 3580 |
| 3 | orzdevinwang | 3570 |
| 4 | cnnfls_csy | 3569 |
| 5 | Geothermal | 3568 |
| 6 | tourist | 3565 |
| 7 | maroonrk | 3530 |
| 8 | Radewoosh | 3520 |
| 9 | Um_nik | 3481 |
| 10 | jiangly | 3467 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | maomao90 | 174 |
| 2 | adamant | 164 |
| 2 | awoo | 164 |
| 4 | TheScrasse | 160 |
| 5 | nor | 159 |
| 6 | maroonrk | 156 |
| 7 | -is-this-fft- | 150 |
| 8 | SecondThread | 147 |
| 9 | orz | 146 |
| 10 | pajenegod | 145 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2024 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 19.04.2024 04:35:09 (k1).
Десктопная версия, переключиться на мобильную.
При поддержке
(We can always translate Luke's position to (0, 0).) Sorry if something is unclear, please clarify if needed.
With matrix exponentiation, you have a list of subsets of states, where the transitions between these states are (almost) the same. For instance, in the "find n-th Fibonacci number in O(logn)" problem, the 'subsets of states' are (Fn - 1, Fn) for positive n.
Take note that they have to be chosen in such a way that they have consistent transitions. A natural choice would be the number of ways Luke can reach the cells on 2 consecutive diagonals. For instance, [(2, 0), (1, 1), (0, 2), (1, 0), (1, 1)] would be the 2nd subset, consisting of the 2nd and 3rd rightmost diagonal. The transitions would be: - for the lower diagonal, just copy the values of the previous upper diagonal, - for the higher diagonal, in each cell, sum up the values of there Luke could have been before this. Note that these locations are always in the last 2 diagonals.
Matrix exponentiation is O(n3logk), where n is the dimension of the matrix, and k is the exponent. The problem is, n is quite big for something cubed in the complexity, so although there does exist a matrix exponentiation solution, it might not be fast enough
Let's say Luke was not allowed to make diagonal moves. Then I think you can derive a closed-form using combinations. (Hint: think of making a string of "Up" and "Right" that moves Luke. How many strings gets you to Vader?)
The one thing preventing us from using this are the diagonal moves. Why? Because a string of "Up", "Right" and "UpRight" that brings us to Vader does not have a fixed length. However, the bounds allow us (I think, I have not paid close attention to the complexity) to iterate across the length of this string (or, more accurately, the number of "UpRight"s), and count how many strings of such length get you to the destination.
Read up this — Delannoy Numbers. You don't need Matrix Exponentiation here.
Can anyone provide some standard tutorial/resources to learn it. I stuck on a task of october long challenge :(
Wait until the bloody contest is over.