Another Grid Problem

Question

There is a maze of size N*M, consisting of unit blocks. At the start Alice has K percentage of energy. Now Alice start from 1 st row and move towards N th row. From the present block she can move to a block in the next row, which is either on right or on left side of the present block. On moving to a block in i th row j th column, her energy will reduce by C(i,j) percent if C(i,j) is greater then 0, else it will be recharged by C(i,j) percent.

For Example if she has 50 percent of energy, on moving to block with C(i,j) = 15, she will have 35 ( 50 -15 ) percent of the it remaining.

Now the task is to find out the status of the Alice energy in the end, if she moves optimally to save maximum energy.

Note : Her energy will not exceed more than 100 percent, and she will not move further if her energy goes down to 0 percent .

EXAMPLE : Let us suppose a grid of 4*4 as follow :

2 -2 2 -2

-2 2 -2 2

1 -1 1 -1

-1 1 -1 1

And if K= 10 meaning she has 10 percent energy at start. then after reaching 4th row she will be having 16 percent energy.One of the optimal move will be <1,2> -> <2,1> -> <3,2> -> <4,1>

Answer 1

Let $f(i, j)$ be the maximum energy obtainable at point $(i, j)$, with $f(i, j) = -\infty$ if we cannot reach $(i, j)$. Then the answer to the problem is $$\max_{1 \leq j \leq M}{f(N, j)}$$

So how do we compute $f(i, j)$? Let's think about the base cases first:

• if $i = 1$, then $f(1, j) = K$, because the only way to arrive at $(1, j)$ is to start from that point.
• if $j < 1$ or $j > N$, then set $f(i, j) = -\infty$ to avoid invalid paths.

Now the general case: there are two ways to arrive at $(i, j)$: move from $(i - 1, j - 1)$ or move from $(i - 1, j + 1)$; in both cases we spend (or obtain) $C(i, j)$ energy -making sure we don't exceed 100-, and we choose the one with the maximum energy. Therefore, if we set $$M := \max \{f(i - 1, j - 1) - C(i, j), f(i - 1, j + 1) - C(i, j)\}$$ then $$f(i, j) = \begin{cases} \min \{M, 100\} &\mbox{if } M \geq 0 \\ -\infty &\mbox{if } M < 0\end{cases}$$

Hope that makes sense! To actually make it run in decent time you need to either use memoization or dynamic programming. See this for a slightly different version of this problem.

Answer 2

Here's an "online" method:

Create a circular linked list of length $M+1$ with entries $ K, K, \ldots, K$ and let $p$ point to one entry. (I write $p\to v$ for the value of the node $p$ points to and $p\to n$ for the successor pointer of the node $p$ points to)

Define $$ f(x,y)=\begin{cases}-1&\text{if }y\le0\text{ or }y-x< 0\\100&\text{if }y-x\ge 100\\y-x&\text{otherwise}\\\end{cases}$$

For $i=1,\ldots, N$,

set $p\to v:=0$, $z=-1$

for $j=1,\ldots,M$,

read $c=C[i,j]$ from input, set $p\to v := \max\{f(c,p\to v),f(c,p\to n\to n\to v)\}$, set $z:=\max\{z,p\to v\}$, set $p:=p\to n$

output $z$.

Note that this will output $-1$ if Alice "starves" on her way before reaching the last row at all and it will output $0$ if she reaches the last row on the last drop of energy.