RETPO - Editorial

editorial
july14
maths
retpo
simple

#1

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

Author’s solution
Tester’s solution


#2

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.

  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+=(2B)+3

    else AD+= 4(B/2*) or AD+= (2
    B)
  5. 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 :slight_smile:
you can check solution here : AcD solution


#3

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();
	}
}

}


#4

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

#5

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;

#6

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;

#7

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


#8

Please let me know the failure test case


#9

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();
	}
}

}


#10

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 ?


#11

Awesome question and great explanation ;-D


#12

Nice, even I used this.


#13

thanks @himanshuahuja :slight_smile:


#14

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


#15

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


#16

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


#17

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

Thanks in advance.


#18

good logic !!


#19

Thanks! Very good!


#20

@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.