0
$\begingroup$

A stone is located at the point (0,0) of an infinite grid. The stone has exactly $n$ possible moves, not necessarily unique, each described by a $vector$ of integer coordinates. The stone can make each move at most once , and the moves it makes may be arranged in any order.The goal is to reach a point as far (in the Euclidean distance) from the initial position as possible. How far can the stone be reached ? $($ Given that output is square of max distance $)$

Example : consider $ n$ $=$ $4$ and vectrs are

$[$2,-2 $]$ ,[-2,-2],[0,2],[3,1],[-3,1]

Ans is $26$ Optimal way is to use vectors [0,2], [3,1], and [2,−2].or also [0,2], [−3,1], and [−2,−2].

link for vector clarity is https://ibb.co/mJByc99

$\endgroup$
1
  • $\begingroup$ Please open this question, as the answer uses brute force (nobody uses brute force in real life) $\endgroup$ Commented May 15, 2022 at 19:40

1 Answer 1

1
$\begingroup$

Addition of vectors is commutative, so the order of moves is irrelevant. For example:

$(0,2) + (3,1) + (2,-2) = (0,2) + (2,-2) + (3,1) = (3,1) + (0,2) + (2,-2) = (5,1)$

So a simple brute force method is to calculate the distance traveled for all subsets of the set of $n$ possible moves. There are $2^n$ such subsets, but you don't need to consider the empty set. So the size of your search space is actually $2^n-1$.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.