PROBLEM LINK:Author: Dmytro Berezin DIFFICULTY:Easy PREREQUISITES:Dynamic programming PROBLEM:There are $N$ dogs numbered from $1$ to $N$ in a line. A ball will be pass around. Initially, dog $s$ has the ball. A dog with the ball can pass it to another dog. With the pass strength of $x$, dog $i$ can pass the ball to dog $i  x$ or dog $i + x$ (provided such dog/s exist). There will be $M$ passes of the ball, and the pass strength of the $j$th pass is $A_j$. For each dog, how many ways are there for the ball to end up at that dog? Output your answers modulo $10^9 + 7$. QUICK EXPLANATION:Use dynamic programming. Let $f(i,j)$ be the number of ways for the ball to end up at dog $i$ after the first $j$ passes. Then we have the following recurrence: $$f(i,j) = f(i  A_j, j1) + f(i + A_j, j1)$$ where we define $f(i,j) = 0$ if $i$ is not in the range $[1,N]$. Also, for base cases, we have $f(s,0) = 1$ and $f(i,0) = 0$ for $i \not= s$. There are only $N$ possible values for $i$ and $M+1$ possible values for $j$, so we can store these values in an $N\times (M+1)$ table and then fill the table up with this recurrence in increasing order of $j$. The answers that we want are $f(i,M)\bmod (10^9 + 7)$ for $1 \le i \le N$. EXPLANATION:Slow solutionThe simplest solution to this problem that is guaranteed correct is to just enumerate all possible choices for passes. There are two choices for each pass, either left or right, and there are $M$ passes, so there are $2^M$ possible choices. A simple recursion like the following will do: (C++)
Notice the following:
Now, this code tries all $2^M$ possibilities so it runs in $O(2^M)$ time. This passes the first subtask, but is too slow for the second; Notice that if $M = 1000$ for instance, then $2^M = 2^{1000}$ is a very large number. Fast solutionThis means we need to find a better solution for the second subtask. To do so, we'll first describe a different bruteforce. Let's define the function $f(i,j)$ as the number of ways for the ball to end up at dog $i$ using the first $j$ passes. With this definition, we immediately notice two things:
The nice thing about $f(i,j)$ is that we can define a particular recurrence with it. If we want the ball to end up at $i$, it means that before the $j$th pass, it must be exactly $A_j$ units away from position $i$. But there are only two such positions: $i  A_j$ and $i + A_j$. So actually, we have the following recurrence $$f(i,j) = f(i  A_j, j1) + f(i + A_j, j1)$$ where we define $f(i,j) = 0$ if $i$ is not in the range $[1,N]$ (which means the position doesn't exist). Now, with this definition, a straightforward recursive implementation can be done:
Unfortunately, this is also slow. In fact, it's even worse than the previous one; It runs in $O(2^M\cdot N)$ in the worst case! So what now? It turns out that there are two insights that will help us:
Thus, we can employ a different strategy to compute $f(1,M), f(2,M), \ldots, f(N,M)$. Instead of creating a recursive function, we will just create a 2D array that will contain all values of $f(i,j)$ that we need, namely for $1 \le i \le N$ and $0 \le j \le M$, and then fill them up in increasing order of $j$. The following illustrates it:
This technique of tabulating values and then reusing previouslycomputed ones is called dynamic programming. The advantage of this technique is that it's much faster! Notice that it only takes $O(1)$ to compute each entry of $f$. Since there are $N\times (M+1)$ entries, the whole algorithm runs in $O(NM)$ time. This passes the second subtask! Minor improvementsThere are a few minor improvements that can be done. The first is to reduce the memory requirements. Notice that the above requires $O(NM)$ memory for the whole table. However,
Therefore, instead of storing the whole table, we only need to store the current and previous rows! This reduces the memory usage from $O(NM)$ to $O(2N) = O(N)$. The following illustrates it:
Here are a couple of things to notice in this code:
There's a further improvement that can be done, and the key insight is that for a fixed $j$, almost half of the entries are $0$. This is because for a fixed $j$, the parity of the final destination is always the same as the parity of $A_1 + A_2 + \ldots + A_j$. It means that entries at positions with a differing parity will be $0$, and there are approximately $N/2$ such positions. Thus, we can reduce the running time and required memory by half by only considering positions of the correct parity. This is slightly more complicated though, and there isn't really a huge benefit, so this improvement is mainly for fun :) Time Complexity:$O(NM)$ AUTHOR'S AND TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 13 May '16, 03:15

@glow There are only two ways to end at position 4, 2>3>2>4 2>1>2>4 For the first pass dog 2 has pass strength 1. So,it can only move, 2>1 or, 2>3 So, it is not possible for 2nd dog to pass to 4th dog in the first pass. Therefore,(2>4) pass is wrong. Hence the passes 2>4>5>4 and 2>4>3>4 are invalid. answered 16 May '16, 20:10

doubtinput > 1 5 3 2 1 1 2 ways to end at position 4(1based indexing) > 2>3>2>4 2>1>2>4 2>4>5>4 2>4>3>4 but when i run an AC code it show 2 ways to end at position 4. Can someone explain how only 2 ? answered 16 May '16, 18:55

Initially the ball is with 2. 1] Pass strength 1. 2>3 & 2>1 2] Pass strength 1 again. 2>3>2 & 2>3>4 . 2>1>2 3] Pass strength 2. 2>3>2>4 2>3>4>2 2>1>2>4 . So by doing the above passes the ball would end up at position 4(2 times) & at position 2(one time). answered 16 May '16, 20:01

here's my algorithm... compared every move to bit string. if ith bit in the bit string is 0 then move right with power a[i] else if it is 1 move left with power a[i]. I got sub task #1 correct but TLE for the second one. Can anyone please suggest some optimization for this code ?? thanx in advanced... answered 17 May '16, 00:00
