Connection Status:
Competition Arena > VisitPoints

VisitPoints

SRM 826 · 2022-03-28 · by misof

SRM 826 · 2022-03-28 · by misof · Graph Theory, Greedy
Class Name: VisitPoints
Return Type: String
Method Name: visit
Arg Types: (vector<int>, vector<int>)
Problem Statement

Problem Statement

You are in a two-dimensional plane at coordinates (0, 0). You can move in steps of length 1 in the four major cardinal directions: 'N' (north: y coordinate increases), 'S' (south), 'E' (east: x coordinate increases) and 'W' (west).


There are some targets to visit. Each target has small positive integer coordinates. You are given these coordinates in the int[]s X and Y. More precisely, for each valid i one of the targets is at (X[i], Y[i]).

It is guaranteed that the targets are not too close to each other: the Euclidean distance between any two targets is at least 2.


You must visit all targets. You may do so in any order, but you must only visit each target exactly once. (You may step on all other coordinates as many times as you like. This includes the point where you start and also points with negative coordinates.)

Find and return any sequence of at most 5000 moves that visits all targets as required. It is guaranteed that such sequences always exist.

Notes

  • It is not required to find a path of minimum total length. Any path that does not exceed the given maximum length will be accepted.
  • The "distance 2" constraint implies that no two targets are orthogonally or diagonally adjacent.

Constraints

  • X will have between 1 and 30 elements, inclusive.
  • Y will have the same number of elements as X.
  • Each element of X will be between 1 and 25, inclusive.
  • Each element of Y will be between 1 and 25, inclusive.
  • No two points described by X and Y will be at distance smaller than 2.
Examples
0)
{1, 2, 3}
{1, 3, 5}
Returns: "NENNNNEEWSS"

We are told to visit the points (1, 1), (2, 3), and (3, 5) each exactly once. Our solution first goes to (1, 1), then around to (3, 5), and finally back to (2, 3).

1)
{1, 7, 3, 9, 5}
{1, 1, 1, 1, 1}
Returns: "NEEEEEEEEE"

This time we simply move to y=1 and then walk east until we hit all the given points.

2)
{9, 20, 1, 19, 18, 14, 13, 3}
{17, 2, 4, 11, 15, 22, 13, 14}
Returns: "NNNNNNNNNENENENENENENENENESSSSSESESESESESESESESESESEWWWWWWWWWWWWWWWWWNWNWEEEEEEEEEEENENENENENENENENNNNWNNNNWNWNWNWSSSSSSSSSWWWWWWWWWWNW"
3)
{17, 2, 12, 15, 8, 23}
{12, 18, 23, 8, 17, 12}
Returns: "EEEEENENENENENENENENENENENENEWWWWWWWWWNWNWNWNWNWNWEEEEENENENENENESSSSSSSSSSSSSESESENNNWNWNWNWNWNWNWEEEEEEEEEESESESESESE"
4)
{4, 11, 13, 18, 12}
{21, 4, 17, 9, 19}
Returns: "NNNNNNNNNNNNNNNNNNENENENESSSSSSSSSSSESESESESESESENNNNNNNNNNNNENESSSSESESESESENNNNNWNWNWNWNWNW"

Submissions are judged against all 93 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class VisitPoints with a public method string visit(vector<int> X, vector<int> Y) · 93 test cases · 2 s / 256 MB per case

Submitting as anonymous