# RETPO - Editorial

Author: Vitalij Kozhukhivskij
Tester: Shang Jingbo and Gerald Agapov
Editorialist: Devendra Agarwal

SIMPLE

Maths.

### PROBLEM:

You need to reach point (x,y) from (0,0) using snake game rule only difference is that snake cannot travel straight for more than 1 unit and the first step is in the Y-axis.

### Explanation

As the snake move is totally symmetrical , we can assume that number of steps required to reach from (0,0) to (x,y) is independent of the sign of x and y.

Reason
First move is in either positive Y or negative Y axis. From there , snake can either move in negative or positive x axis and so on.

Case 1: Let us solve the case when y = 0, i.e steps required to reach (x,0) from (0,0):

Wlog we can assume that x is positive . Now if x is odd , then total number of 2x+1 steps are required.
Proof is immediate by sketching a small diagram [ Remember that the first move is towards Y axis ] . If x is even , then total number of steps required is 2
x , proof by sketching.

Case 2: Let us solve the case when x = 0, i.e steps required to reach (0,y) from (0,0):

Wlog we can assume that y is positive . Now if y is odd , then total number of 2y-1 steps are required . If y is even , then total number of 2y steps are required.

Case 3: Let us now solve the case when neither x nor y are zero :

Till now , you must have realized that the snake move is perpendicular and it will cover 1 unit in y and 1 unit in x direction . So first move to (min(x,y) , min(x,y) ) and cover the remaining distance by the above cases discussed.

Pseudo Code

``````get_answer(x,y):
x= abs(x);	//get the absolute value of x
y=abs(y);	//get the absolute value of y
z=min(x,y);	//get the minimum of x and y
return 2*z + val(x-z,y-z))

// if a is 0 , then it is case 2 , else it is case 1.

val (a , b) :		//either case 1 or case 2
return ( (a&1) ? (2*a+1) : (2*a) ) + ( (b&1) ? (2*b-1) : (2*b)  );
``````

Complexity:

O(1).

### AUTHORâ€™S AND TESTERâ€™S SOLUTIONS:

8 Likes

I solved by checking the four Cartesian quadrants. Then checked few points on the co-ordinate axis.
The general formula was then easy to derive.

given x, y:
X=abs(x) and Y=abs(y) where abs() is the absolute value function

A=min(X,Y) , D=max(X,Y) , B=D-A where min(x,y) is minimum value and max(x,y) of x and y.

1. Bot first moves to (a,a) point nearest to the (x,y) point. It takes AD= 2min(X,Y)= 2A.

2. Then I derived a series: 3,4,7,8,11,12 â€¦ which is actually two APs 3,7,11 â€¦ and 4,8,12â€¦ combined. general term 4(n-1)+3 and 4n respectively. This is for moving increasing steps 1,2,3,

3. Now if B is odd and Y is greater than X ( which means bot has to move in up or down direction and now itâ€™s facing either towards +x axis or -x axis) then AD-=2

4. then simply
if B is odd ( series 1 is to be used) AD+= 4(B/2)+3* or AD+=(2*B)+3

note: All variable will fit under int data type as 1 â‰¤ T â‰¤ 105 and -109 â‰¤ x, y â‰¤ 109 , you can take AD as long long.

thanks
you can check solution here : AcD solution

1 Like

May i know for which test case this code failed

http://www.codechef.com/viewplaintext/4256084

import java.io.IOException;

public class Main {

``````/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String point[] = null;
try {
long x = 0, y = 0;
long xa=0,ya=0;
long result = 0;
long delta = 0;
for (int i = 1; i <= t; i++) {
x = Long.parseLong(point[0]);
y =  Long.parseLong(point[1]);
if(x==0&&y==0){
System.out.println(4);
continue;
}
xa=Math.abs(x);
ya=Math.abs(y);
if (x == y) {
result = 2 * x;
System.out.println(result);
continue;
}

if(xa>ya){
delta = (xa-ya);
result=2*ya;
//more 3s
if(delta%2==0){
delta /= 2;
result += delta + 3 * delta;
}else{
delta /= 2;
result += delta + 3 * (delta+1);
}
}else{

delta = (ya-xa);
result=2*xa;
//more 1s
if(delta%2==0){
delta /= 2;
result += delta + 3 * delta;
}else{
delta /= 2;
result += (delta+1) + 3 *delta;
}
}
System.out.println(result);
}
} catch (NumberFormatException | IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
``````

}

Another Logic

```x=abs(x);
y=abs(y);
if(x<=y)
{
if((x+y)%2==0)
ans=2*y;
else
ans=(2*y)-1;
}
else
{
if((x+y)%2==0)
ans=2*x;
else
ans=(2*x)+1;
}
print ans

``````
1 Like

here is the simplest code :

``````    x = abs(x); y = abs(y);
if(x >= y)
ans = (x+y) + (((x-y)+1)/2)*2;
else
ans = (x+y) + ((y-x)/2)*2;``````
1 Like

here is a diffrent one ----

``````    cin>>x>>y;
if(x<0)x*=-1;
if(y<0)y*=-1;
ll ans=0;
ans+=min(x,y)*1ll*2;
int u=max(x,y)-min(x,y);
ans+=(u/2)*1ll*4;
if(x<y)ans+=u%2;
else if(x>y)ans+=(u%2)*1ll*3;
cout<<ans<<endl;``````

sir can you please explain why going first to min(x,y),min(x,y) will give us min steps ?

Please let me know the failure test case

import java.io.IOException;

public class Main {

``````/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub
String point[] = null;
try {
long x = 0, y = 0;
long xa=0,ya=0;
long result = 0;
long delta = 0;
for (int i = 1; i <= t; i++) {
x = Long.parseLong(point[0]);
y =  Long.parseLong(point[1]);
xa=Math.abs(x);
ya=Math.abs(y);
if (x == y) {
result = 2 * x;
System.out.println(result);
continue;
}

if(xa>ya){
delta = (xa-ya);
result=2*ya;
//more 3s
if(delta%2==0){
delta /= 2;
result += delta + 3 * delta;
}else{
delta /= 2;
result += delta + 3 * (delta+1);
}
}else{

delta = (ya-xa);
result=2*xa;
//more 1s
if(delta%2==0){
delta /= 2;
result += delta + 3 * delta;
}else{
delta /= 2;
result += (delta+1) + 3 *delta;
}
}
System.out.println(result);
}
} catch (NumberFormatException | IOException e) {
// TODO Auto-generated catch block
e.printStackTrace();
}
}
``````

}

x=abs(x);
y=abs(y);
if(x<=y)
{
if((x+y)%2==0)
ans=2y;
else
ans=(2y)-1;
}
else
{
if((x+y)%2==0)
ans=2x;
else
ans=(2x)+1;
}
print ans

wonâ€™t this logic fail for 3 2 where the answer is 5, but this logic gives 7 ?

Awesome question and great explanation ;-D

Nice, even I used this.

1 Like

thanks @himanshuahuja

Hello,please respond to this code,what is the problem with it
Regards
Samuel

I have tried both versions but failed ,can any one send me test case it failed,or let me know the mistake
Regards
Samuel

@abcdexter24 From where did you derieved the series 3,4,7,8,11,12â€¦??

In Case 3, what exactly is meant by â€śSo first move to (min(x,y) , min(x,y) ) and coverâ€¦â€ť ?