ZIO20001 - Editorial

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 :slight_smile:

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 )

|487x467.12244897959175

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 :slight_smile:

8 Likes

can i use beggar’s method in P&C to solve it?
tfjvhm
each manhattan dist = a+b
S=a+b
number of a,b satisfying = C(n+r-1,r-1)
= C(S+1,1)=S+1
sum over S+1 for s from 1 to S
do the same for other quadrants. However, my answer is wrong. I may’ve done a silly calc mistake.
But, is this approach correct?

1 Like

Didnt understand what you are saying
Can you ps explain bit more clearly what you said
Thanks :slight_smile:

2 Likes

Tried this problem.
Turns out the general formula is quite simple!!

Just 2S^2 + 2S + 1!!

3 Likes

Problem statement should be little bit more clear…

What is missing or should be added ? :slight_smile:

1 Like