RETPO - Editorial

devuy11 · July 14, 2014, 3:01pm

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

SIMPLE

PREREQUISITES:

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 2x , 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:

Author’s solution
Tester’s solution

abcdexter24 · July 14, 2014, 3:11pm

Awesome question and great explanation ;-D

abcdexter24 · July 14, 2014, 3:27pm

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.
AD= ans , initially 0.

Bot first moves to (a,a) point nearest to the (x,y) point. It takes AD= 2min(X,Y)= 2A.
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,
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
then simply
if B is odd ( series 1 is to be used) AD+= 4(B/2)+3* or AD+=(2*B)+3

else AD+= 4(B/2*) or AD+= (2*B)
And now simply print AD, the answer.

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

himanshujaju · July 14, 2014, 3:28pm

Nice, even I used this.

jawa2code · July 14, 2014, 3:52pm

May i know for which test case this code failed

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

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

/**
 * @param args
 */
public static void main(String[] args) {
	// TODO Auto-generated method stub
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	String point[] = null;
	try {
		int t = Integer.parseInt(br.readLine());
		long x = 0, y = 0;
		long xa=0,ya=0;
		long result = 0;
		long delta = 0;
		for (int i = 1; i <= t; i++) {
			point = br.readLine().split(" ");
			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();
	}
}

}

abcdexter24 · July 14, 2014, 5:22pm

thanks @himanshuahuja

inception44 · July 14, 2014, 5:36pm

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

```

aq_faridi · July 14, 2014, 9:21pm

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;

razkverma · July 15, 2014, 1:55am

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;

karankapoor · July 15, 2014, 3:17pm

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

jawa2code · July 15, 2014, 3:54pm

Please let me know the failure test case

jawa2code · July 16, 2014, 11:13am

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

jawa2code · July 23, 2014, 11:21am

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {

/**
 * @param args
 */
public static void main(String[] args) {
	// TODO Auto-generated method stub
	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	String point[] = null;
	try {
		int t = Integer.parseInt(br.readLine());
		long x = 0, y = 0;
		long xa=0,ya=0;
		long result = 0;
		long delta = 0;
		for (int i = 1; i <= t; i++) {
			point = br.readLine().split(" ");
			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();
	}
}

}

jawa2code · July 23, 2014, 11:22am

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

sagar_797 · August 5, 2014, 3:13pm

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

samirzach · August 13, 2014, 8:20pm

In Case 3, what exactly is meant by “So first move to (min(x,y) , min(x,y) ) and cover…” ?

Thanks in advance.

zargus · August 19, 2014, 1:12pm

good logic !!

vietsony · August 19, 2014, 3:42pm

Thanks! Very good!

abcdexter24 · September 16, 2014, 12:20am

@sagar_797 I derived this series by looking at the minimum steps required to move to next ith coordinate. means which is at i distance away in cartesian system.

kishynivas_13 · September 16, 2017, 7:50pm

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 ?