CRAWA - Editorial

PROBLEM LINK:

Practice
Contest

Author: Vitalij Kozhukhivskij
Tester: Praveen Dhinwa and Hiroto Sekido
Editorialist: Lalit Kundu

DIFFICULTY:

Easy

PREREQUISITES:

None at all :slight_smile:

PROBLEM:

  • Initially the robot is at position (0, 0).
  • In the beginning it goes 1 step to the East (i.e. In a single step, its x coordinate will increase by 1 unit.)
  • then 2 steps to the North, (i.e. In a single step, its y coordinate will increase by 1 unit.)
  • then 3 steps to the West, (i.e. In a single step, its x coordinate will decrease by 1 unit.)
  • then 4 steps to the South, (i.e. In a single step, its y coordinate will decrease by 1 unit.)
  • then 5 steps to the East,
  • and so on.

You are given 105 queries of form (X,Y). You have to tell if robot ever visiter the coordinate (X,Y).

EXPLANATION:

Since number of queries is high, we need to solve all queries in O(1).

Let’s consider the vertical line as y-axis and other as x-axis. If we extend the path of the robot, we can clearly observe from the path that
. Robot visits all lines of form:

x=2*k+1 //k>=0; y ranges from -2*k to 2*k+2 (both inclusive)
x=-2*k //k>=1; y ranges from -2*k to 2*k (both inclusive)
y=2*k //k>=0; x ranges from -2*k to 2*k+1 (both inclusive)
y=-2*k //k>=1; x ranges from -2*k to 2*k+1 (both inclusive)

Now, it’s very trivial to find if a point (X,Y) lies on these possible lines.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution
Tester’s solution

2 Likes

At -2 0,-1 0,-3 5… check these test case … @rach8

Your program -

 http://ideone.com/G7WtLE 

get wrong ans in these test case
-2 0 expected ans is YES but your program is NO.

1 Like

@rajat_dtc Thanku!! that problem is resolved now, stil wrong answer.

@rach8 check this link -

 http://ideone.com/x8rLTV 
2 Likes