**Editorialist** : Venkatakrishnan A

**Problem Link** : https://www.iarcs.org.in/inoi/2020/zio2020/zio2020-question-paper.pdf

**Short Explanation of Question** : We are asked to find the number of points such that the Manhattan Distance (mentioned in the problem) is atmost S.

**Pre-requisites** : Basic recursion.

**Solution** :

This is clearly a *Dynammic Programming* problem, because here we have overlapping sub-problems, which are related by a recursion.

**State of DP** : Let dp[N] be the number of such points such that the Manhattan Distance is atmost N.

**Base Case** : dp[0] = 1, dp[1] = 5.

**Some Mathematics**:

We have to find the number of solutions to the equation

```
|x| + |y| = S
```

which is calculated to be

```
4*S(S-1)/2 + 1 = 2S(S-1) + 1
```

So, we have

```
dp[S] = 2S(S-1) + 1
```

Thus calculating the value of dp[S+1] too, we get the recursion

```
dp[S+1] = dp[S] + 4
```

**Code** : https://ideone.com/rvWbaU

**Subtasks**:

*Subtask 1* : S=4

*Answer* : 41

*Subtask 2*: S=10

*Answer*: 221

*Subtask 3*: S=23

*Answer*: 1105

Thank you.