Editorialist : Sudheera Y S
Problem Link : https://www.iarcs.org.in/inoi/2020/zio2020/zio2020-question-paper.pdf
Prerequisites : Pattern finding
Problem statement :
Find the number of points whose manhattan distance is atmost S from 0,0
Idea :
Let us slightly change our problem definition to - Answer for a number S is the number of points whose manhattan distance is exactly S
( We finally compute our required answer by adding the answers from 0 …… S )
We are going to solve for S = 1…4 and we will find a pattern in it ( which is easy to prove also ) and then we will continue it and will compute the answer
S = 0 : Answer = 1 - (0,0)
S = 1 : Answer = 4 - (1,0) , (0,1) , (-1,0) , (0,-1)
The points would look like this : ( Only Blue points )
S = 2 : Anwer = 8
The points would be like this : ( Only Yellow points )
S = 3 : Anwer = 12
The points with manhattan distance 3 would look like this : ( Only Red points )
S = 4 : Anwer = 16
The points with manhattan distance 4 would be like this : ( Only Green points )
Can we find some pattern here?
Let us consider all the points except the corners of the green square in the above diagram, we see that there are (S-1) points on each edge of the square and there are 4 edges so in total there are 4*(S-1) points and there are 4 corners which we are not considering, so the total number of points would be 4*(S-1) + 4 = 4*S
So the pattern is :
Answer for S = 4*S where S >= 1
And answer for S = 0 is 1
Calculating the answer :
For finding the required answer for S, we need to add our answers from S = 0……S and that would be our final answer
Subtask A :
S = 4 : Sum = 1 + 4 + 8 + 12 + 16 = 41
Answer : 41
Subtask B :
S = 10 : Here instead of adding all the numbers can we find a formula ??
Answer for S = 1 : 4*1
Answer for S = 2 : 4*2
Answer for S = 3 : 4*3
.
.
.
Answer for S = 10 : 4*10
Sum of all the answers = 41 + 42 + … + 4*10
= 4*(1+2+…+10)
= 4*(1011)/2 ( Sum of first n numbers is (n(n+1))/2 )
= 2*110
= 220
NOTE : We should remember to add 1 to our answer as S = 0 is not being considered in the formula
So the answer will be 221
Answer : 221
Subtask C :
S = 23
Applying the formula for S = 23 , we get ,
Sum of all answers = 4*(1+2+…+23)
= 4*(2324)/2 (Sum of first n numbers is (n(n+1))/2 )
= 2*552
= 1104
NOTE : We should remember to add 1 to our answer as S = 0 is not being considered in the formula
So the answer will be 1105
Answer : 1105
Code in C++ : https://github.com/sudheerays123/ZIO-Codes/blob/main/ZIO%202020%20P1.cpp
Hope you understood