Codeforces Round #239 (Div. 2), problem: (D) Long Path editorial in russian: http://codeforces.com/blog/entry/11333?locale=ru
В задаче требовалось промоделировать путь персонажа по графу. Заметим, что если мы пришли в вершину i, то ребра во всех вершинах с номерами меньшими, чем i, повернуты в pi. Это дает нам возможность заметить рекуррентную формулу: пусть dpi— число шагов, необходимое, чтобы добраться из вершины 1 в вершину i, если все ребра изначально повернуты назад, в pi. тогда dpi + 1 = 2dpi + 2 - dppi. Ответом будет dpn + 1.
Сложность решения — O(n).
BONUS: Умеете ли вы решать задачу, если нет ограничения, что pi ≤ i? В такой формулировке задача становится более интересной, но я пока не знаю решения.
Codeforces Round #239 (Div. 2), problem: (D) Long Path solution in english(translated via google):
In the task required to simulate the way a character count. Note that if we came to the top of i, then the edges of all vertices with numbers less than i, turned in pi. This gives us the opportunity to observe the recurrence formula : let dpi - the number of steps required to get from one vertex to vertex i, if all the edges initially turned back in pi. then dpi + 1 = 2dpi + 2 - dppi. The answer is dpn + 1.
Complexity of the solution - O (n).
BONUS: Can you solve the problem if there is no restriction that pi ≤ i? In this formulation, the problem becomes more interesting , but I do not know the solution.
Codeforces Round #239 (Div. 2), problem: (D) Long Path solution: http://ideone.com/UO6jUA
#include <iostream> #include <cstdio> using namespace std; int main() { int n, p[1005], a[1005], r; const int md=1e9+7; r=0; scanf("%d", &n); for(int i=1; i<=n; i++) scanf("%d", &p[i]); for(int i=1; i<=n; i++) { a[i]=2; for(int j=p[i]; j<i; j++) a[i]+=a[j], a[i]%=md; r+=a[i], r%=md; } printf("%d", r); return 0; }
NOTE: if you try sample inputs then you will realise that it needs some dynamic programming as indicated in problem tags as "dp". try yourself some inputs, for example:
3
1 1 1
output should be 14. the dynamic programming array (ceilings of rooms) looks like below case:
8 4 2
and after that Vasya can enter to room n+1.
and other numbers of crosses at the ceilings of rooms are displayed below:
sample input 1:
2
1 2
output 1:
4
numbers of crosses at the ceilings of rooms:
2 2
sample input 2:
4
1 1 2 3
output 2:
20
numbers of crosses at the ceilings of rooms:
8 6 4 2
sample input 3:
5
1 1 1 1 1
output 3:
62
numbers of crosses at the ceilings of rooms:
32 16 8 4 2
