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. 