Task Pawn - maximum Euclidean distance.

  • (4 Pages)
  • +
  • 1
  • 2
  • 3
  • Last »

45 Replies - 1912 Views - Last Post: 12 November 2017 - 12:36 PM Rate Topic: **--- 4 Votes

#1 Vaxler   User is offline

  • D.I.C Head

Reputation: -5
  • View blog
  • Posts: 51
  • Joined: 07-November 17

Task Pawn - maximum Euclidean distance.

Posted 11 November 2017 - 03:00 PM

Main content of the task:
At the point (0, 0) stand a pawn. Pawn has n allowed movements. Each one is desribed as a vector of integer coordinates. Pawn can do each movement only once in any order. Vectors may repeat and then the pawn may use each of them.
Our goal is to count maximum distance from point (0, 0) to the the fatherst located point - Euclidean distance.

Input:
The first line cantains one positive number n denoting number of possible moves by the pawn.
Next n lines contain two positive numbers xi, yi (-104 ≤ xi, yi ≤ 104) separated by a single space and representing vector [xi, yi] desribing possible movement of the pawn.

Output:
Program has to print the number denoting sqaure distance from point (0, 0) to farthest point to which he can jump.

Example:

For the input:
5
2 -2
-2 -2
0 2
3 1
-3 1

Correct answer is:
26

Link to example

Explanation:
The picutre shows optimal solution using moves described by the vectors: [0, 2], [3, 1] and [2, -2]. Other optimal soultion is: [0, 2], [-3, 1] and [-2, -2]. The movments order matters.

n ≤ 200000
----------------------------------------------------------------------------------------------------

My idea was to sort 4 times by the first coordinate and by the second and then check to maximum positive or negative sum. It doesn't give the correct answers. Here are the tests and the code:
#include <iostream>
#include <algorithm>

using namespace std;

const int MAX = 200001;

using II = pair<int, int>;

II tab_X1[MAX]; // sorted by X
II tab_Y1[MAX]; // sorted by Y
II tab_X2[MAX]; // sorted by X
II tab_Y2[MAX]; // sorted by Y

long long maximum = 0;

bool sort_X1(const II & v1, const II & v2)
{
	if (v1.first < v2.first)
		return true;
	else if (v1.first == v2.first && v1.second < v2.second)
		return true;

	return false;
}

bool sort_Y1(const II & v1, const II & v2)
{
	if (v1.second < v2.second)
		return true;
	else if (v1.second == v2.second && v1.first < v2.first)
		return true;

	return false;
}

bool sort_X2(const II & v1, const II & v2)
{
	if (v1.first < v2.first)
		return true;
	else if (v1.first == v2.first && v1.second > v2.second)
		return true;

	return false;
}

bool sort_Y2(const II & v1, const II & v2)
{
	if (v1.second < v2.second)
		return true;
	else if (v1.second == v2.second && v1.first > v2.first)
		return true;

	return false;
}

long long sum(long long x, long long y)
{
	return x*x + y*y;
}

void max_SUM(const II (&tab)[MAX], int n)
{
	long long x = 0, y = 0;

	for (int i = 0; i < n; ++i)
	{
		x += tab[i].first;
		y += tab[i].second;

		maximum = max(maximum, sum(x, y));
	}

	x = y = 0;

	for (int i = n - 1; i > - 1; --i)
	{
		x += tab[i].first;
		y += tab[i].second;

		maximum = max(maximum, sum(x, y));
	}
}

int main()
{
	std::ios_base::sync_with_stdio(0);

	int n;

	cin >> n;

	int x, y;

	for (int i = 0; i < n; ++i)
	{
		cin >> x >> y;

		tab_X1[i].first = tab_X2[i].first = tab_Y1[i].first = tab_Y2[i].first = x;
		tab_X1[i].second = tab_X2[i].second = tab_Y1[i].second = tab_Y2[i].second = y;
	}

	sort(tab_X1, tab_X1 + n, sort_X1);
	sort(tab_X2, tab_X2 + n, sort_X2);
	sort(tab_Y1, tab_Y1 + n, sort_Y1);
	sort(tab_Y2, tab_Y2 + n, sort_Y2);

	max_SUM(tab_X1, n);
	max_SUM(tab_X2, n);
	max_SUM(tab_Y1, n);
	max_SUM(tab_Y2, n);

	cout << maximum << '\n';
}


Could you help me to write a faster algorithm again? The first one topic haven't been clear and sorry for it, but this one is really clear. Counting on you. I take to heart every advice. Thanks and reagards :)

This post has been edited by Vaxler: 11 November 2017 - 03:14 PM


Is This A Good Question/Topic? 0
  • +

Replies To: Task Pawn - maximum Euclidean distance.

#2 snoopy11   User is offline

  • Engineering ● Software
  • member icon

Reputation: 1467
  • View blog
  • Posts: 4,726
  • Joined: 20-March 10

Re: Task Pawn - maximum Euclidean distance.

Posted 11 November 2017 - 03:31 PM

Why not use std::vector... why use fixed arrays ?
Was This Post Helpful? 0
  • +
  • -

#3 Vaxler   User is offline

  • D.I.C Head

Reputation: -5
  • View blog
  • Posts: 51
  • Joined: 07-November 17

Re: Task Pawn - maximum Euclidean distance.

Posted 11 November 2017 - 03:37 PM

This is a better way to store information in the algorithmic tasks if we are given in advance the maximum n.

This post has been edited by Vaxler: 11 November 2017 - 03:37 PM

Was This Post Helpful? 0
  • +
  • -

#4 Vaxler   User is offline

  • D.I.C Head

Reputation: -5
  • View blog
  • Posts: 51
  • Joined: 07-November 17

Re: Task Pawn - maximum Euclidean distance.

Posted 11 November 2017 - 06:00 PM

View PostVaxler, on 11 November 2017 - 03:00 PM, said:

Could you help me write a faster algorithm again?

Sorry, not faster. Correct one and fast.
Was This Post Helpful? 0
  • +
  • -

#5 snoopy11   User is offline

  • Engineering ● Software
  • member icon

Reputation: 1467
  • View blog
  • Posts: 4,726
  • Joined: 20-March 10

Re: Task Pawn - maximum Euclidean distance.

Posted 11 November 2017 - 06:13 PM

If you say so..

so however again you say you want a faster algorithm but your code doesn't work.....

why not just concentrate on getting a working code first then optimise it......??

Anyway the problem is one of Euclidean distance which is given by the formula..

Posted Image

and you need a better naming convention strategy right now its hard to understand your code as it uses codenames for everything nothing is self explanatory as it should be...

I would start with a Euclidean Vector struct declare an array of Euclidean Vectors and proceed from there...

struct point
{
    double p;
    double q;
};
struct Euclidean_Vector
{
    point pq1;
    point pq2;
    int distance()
    {
     return (int)(sqrt(pow(pq1.q-pq1.p,2.0)+ pow(pq2.q-pq2.p,2.0)));
    }
};

Euclidean_Vector myEuclidean_Vector[MAX];


Was This Post Helpful? 0
  • +
  • -

#6 Vaxler   User is offline

  • D.I.C Head

Reputation: -5
  • View blog
  • Posts: 51
  • Joined: 07-November 17

Re: Task Pawn - maximum Euclidean distance.

Posted 11 November 2017 - 06:33 PM

My first observation was that, optimals movements are sum of vectors:
[0, 2] + [3, 1] = [3, 3]
[3, 3] + [2, -2] = [5, -1]

Then I count it as follows - 52 + (-1)2 = 26;

View Postsnoopy11, on 11 November 2017 - 06:13 PM, said:

struct point
{
    double p;
    double q;
};
struct Euclidean_Vector
{
    point pq1;
    point pq2;
    int distance()
    {
     return (int)(sqrt(pow(pq1.q-pq1.p,2.0)+ pow(pq2.q-pq2.p,2.0))); // it shouldn't be done like this - we should not base on float numbers
    }
};



It shouldn't be done like this - we should not base on float numbers. The output of this task is a square of Euclidean distance.

This post has been edited by Vaxler: 11 November 2017 - 06:34 PM

Was This Post Helpful? 0
  • +
  • -

#7 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6290
  • View blog
  • Posts: 21,616
  • Joined: 05-May 12

Re: Task Pawn - maximum Euclidean distance.

Posted 11 November 2017 - 06:48 PM

Euclidean distances are not guaranteed to be integers. Are you sure you did not mean Manhattan distances which will be integers?
Was This Post Helpful? 1
  • +
  • -

#8 Vaxler   User is offline

  • D.I.C Head

Reputation: -5
  • View blog
  • Posts: 51
  • Joined: 07-November 17

Re: Task Pawn - maximum Euclidean distance.

Posted 11 November 2017 - 06:51 PM

View PostSkydiver, on 11 November 2017 - 06:48 PM, said:

Euclidean distances are not guaranteed to be integers.

They aren't guaranteed to be integers, but the output of this task is a square of it, so calculating it as a sqrt is useless.

This post has been edited by Vaxler: 11 November 2017 - 06:53 PM

Was This Post Helpful? 0
  • +
  • -

#9 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6290
  • View blog
  • Posts: 21,616
  • Joined: 05-May 12

Re: Task Pawn - maximum Euclidean distance.

Posted 11 November 2017 - 06:55 PM

Anyway, this problem is another exercise in dynamic programming if your goal is to do things as fast as possible. Essentially, with dynamic programming, you sacrifice memory for speed.
Was This Post Helpful? 0
  • +
  • -

#10 Vaxler   User is offline

  • D.I.C Head

Reputation: -5
  • View blog
  • Posts: 51
  • Joined: 07-November 17

Re: Task Pawn - maximum Euclidean distance.

Posted 11 November 2017 - 07:01 PM

But question is how to implement a dynamic programming in this task? Any advices how to approach to this task?
Was This Post Helpful? 0
  • +
  • -

#11 snoopy11   User is offline

  • Engineering ● Software
  • member icon

Reputation: 1467
  • View blog
  • Posts: 4,726
  • Joined: 20-March 10

Re: Task Pawn - maximum Euclidean distance.

Posted 11 November 2017 - 07:56 PM

You were right it is Manhattan distance or Taxicab Geometry

this is given by the equation

Posted Image

code implementation

struct point
{
    int p;
    int q;
};
struct Taxicab_Vector
{
    point pq1;
    point pq2;
    int distance()
    {
     return abs(pq2.p-pq1.p)+ abs(pq2.q-pq1.q);
    }
};



Was This Post Helpful? 0
  • +
  • -

#12 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6290
  • View blog
  • Posts: 21,616
  • Joined: 05-May 12

Re: Task Pawn - maximum Euclidean distance.

Posted 11 November 2017 - 09:26 PM

It looks like our OP incorrectly translated things again like in his other thread. When he said:

Quote

Program has to print the number denoting sqaure distance from point (0, 0) to farthest point to which he can jump.


He really meant to say:

Quote

Program has to print the number denoting the square of the distance from point (0, 0) to farthest point to which the pawn can reach.


Our OP also incorrectly states:

Quote

Next n lines contain two positive numbers

yet the range of values given and the sample input show negative values.

The reason for using the square of the distance is to make it easier to write the program so that you will only ever have to deal with integers.
Was This Post Helpful? 0
  • +
  • -

#13 Skydiver   User is offline

  • Code herder
  • member icon

Reputation: 6290
  • View blog
  • Posts: 21,616
  • Joined: 05-May 12

Re: Task Pawn - maximum Euclidean distance.

Posted 11 November 2017 - 09:35 PM

View PostVaxler, on 11 November 2017 - 09:01 PM, said:

But question is how to implement a dynamic programming in this task? Any advices how to approach to this task?

Yes. Compose your initial correct solution as using recursion. Dynamic programming lends itself well to translating depth first recursive algorithms into iterative algorithms.

Next bone up on how to create dynamic programming solutions given a recursive recurrence. Sometimes it is as simple as implementing memoization and removing the tail recursion. Other times it requires more insight into the problem and how states change going from one recursion level to the next.
Was This Post Helpful? 0
  • +
  • -

#14 snoopy11   User is offline

  • Engineering ● Software
  • member icon

Reputation: 1467
  • View blog
  • Posts: 4,726
  • Joined: 20-March 10

Re: Task Pawn - maximum Euclidean distance.

Posted 11 November 2017 - 11:09 PM

Yes well again Skydiver,

You could be correct....however I also point you to the title 'Task Pawn - Maximum Euclidean Distance'

So you can see my initial confusion...

It seems the OP is as confused and confusing about what to do next as ever...

Again However using the data in post #1 starting at point{ 0, 0 } and this time using Manhattan distance you end up with the answer: 26

So now I'm even more confused by your suggestion that it is based on the starting point and farthest point location squared....

Because what squared is 26 ?...

Anyway I would like to think I've helped by providing the correct equations for both Euclidean Distance and Manhattan distance.

I don't think I can help any further without the proper explanation of what is actually to be calculated and perhaps even the equation to be used in this because there will be an equation that describes this well.
Was This Post Helpful? 0
  • +
  • -

#15 Vaxler   User is offline

  • D.I.C Head

Reputation: -5
  • View blog
  • Posts: 51
  • Joined: 07-November 17

Re: Task Pawn - maximum Euclidean distance.

Posted 12 November 2017 - 01:55 AM

View PostSkydiver, on 11 November 2017 - 09:26 PM, said:

Our OP also incorrectly states:

Quote

Next n lines contain two positive numbers
yet the range of values given and the sample input show negative values.The reason for using the square of the distance is to make it easier to write the program so that you will only ever have to deal with integers.


Sorry mu fault - values can be negative as well.

View PostSkydiver, on 11 November 2017 - 09:35 PM, said:

View PostVaxler, on 11 November 2017 - 09:01 PM, said:

But question is how to implement a dynamic programming in this task? Any advices how to approach to this task?
Yes. Compose your initial correct solution as using recursion. Dynamic programming lends itself well to translating depth first recursive algorithms into iterative algorithms.Next bone up on how to create dynamic programming solutions given a recursive recurrence. Sometimes it is as simple as implementing memoization and removing the tail recursion. Other times it requires more insight into the problem and how states change going from one recursion level to the next.


I know what a dynamic program programming is. But how to do it in this task?

View Postsnoopy11, on 11 November 2017 - 11:09 PM, said:

Yes well again Skydiver,You could be correct....however I also point you to the title 'Task Pawn - Maximum Euclidean Distance'So you can see my initial confusion...It seems the OP is as confused and confusing about what to do next as ever...Again However using the data in post #1 starting at point{ 0, 0 } and this time using Manhattan distance you end up with the answer: 26So now I'm even more confused by your suggestion that it is based on the starting point and farthest point location squared....Because what squared is 26 ?...Anyway I would like to think I've helped by providing the correct equations for both Euclidean Distance and Manhattan distance.I don't think I can help any further without the proper explanation of what is actually to be calculated and perhaps even the equation to be used in this because there will be an equation that describes this well.


Farthest point to which he can jump is a maximum Euclidean distance from point (0, 0). So again:
We have to calculate maximum Euclidean distance from point (0, 0) using any vectors. After calculating this value, we print to the output square of it. Basing on float values isn't good idea - that was my point.
Was This Post Helpful? 0
  • +
  • -

  • (4 Pages)
  • +
  • 1
  • 2
  • 3
  • Last »