EvenRoute

SRM 538 · 2011-11-22 · by vexorian

SRM 538 · 2011-11-22 · by vexorian · Dynamic Programming, Math, Simple Search, Iteration

Show categories

Class Name: EvenRoute

Return Type: String

Method Name: isItPossible

Arg Types: (vector<int>, vector<int>, int)

Problem Statement

Fox Ciel has stumbled upon a new problem: In this problem you will visit some points with integer coordinates in the Cartesian plane. Initially, you are located at the point (0,0). In each step, you can move from your current point to one of the four directly adjacent points. I.e., if you are at (x,y), you can move to one of the points (x,y+1), (x,y-1), (x+1,y), and (x-1,y).

You are given two int[]s x and y, each containing N elements. Together, x and y describe N distinct points in the Cartesian plane: for 0 <= i < N, point i has the coordinates (x[i],y[i]).

The goal is to find a sequence of steps that satisfies the following criteria:

The starting point is (0,0).
The sequence visits each of the N given points at least once.
The sequence finishes in one of the given points.

Mr. K claims to have solved this problem but Ciel does not believe him. Ciel has prepared a method to verify Mr. K's claims. Given an int wantedParity, the parity of the number of steps in the sequence found by Mr. K, Ciel will find if it is possible to find a sequence that follows the previously mentioned conditions and a new one:

The parity of the total number of steps is wantedParity. In other words, if wantedParity=0 then the total number of steps must be even, and if wantedParity=1 then the total number of steps must be odd.

Return "CAN" (quotes for clarity) if at least one such sequence of steps exists, and "CANNOT" otherwise.

Constraints

wantedParity will be 0 or 1.
x will contain between 1 and 50 elements, inclusive.
y will contain the same number of elements as x.
Each element of x and y will be between -1000000 and 1000000, inclusive.
No point in the input will be equal to (0,0).
No pair of points in the input will be equal.

Examples

{-1,-1,1,1}
{-1,1,1,-1}
0
Returns: "CAN"

A possible sequence containing an even number of steps: 2 steps: (0,0) -> (-1,-1). 2 steps: (-1,-1) -> (-1,1). 2 steps: (-1,1) -> (1,1). 2 steps: (1,1) -> (1,-1).

{-5,-3,2}
{2,0,3}
1
Returns: "CAN"

A possible sequence containing an odd number of steps: 7 steps: (0,0) -> (-5,2). 4 steps: (-5,2) -> (-3,0). 8 steps: (-3,0) -> (2,3).

{1001, -4000}
{0,0}
1
Returns: "CAN"

The shortest sequence that visits all the given points is the sequence that first goes to (1001,0) and then to (-4000,0). Note that this sequence does not have an odd amount of steps. However, there is a longer sequence with an odd number of steps: (0,0) -> (-4000,0) -> (1001, 0).

{11, 21, 0}
{-20, 42, 7}
0
Returns: "CANNOT"

{0, 6}
{10, -20}
1
Returns: "CANNOT"

{0}
{1}
1
Returns: "CAN"

Very small case.

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

Coding Area

Language: C++17 · define a public class EvenRoute with a public method string isItPossible(vector<int> x, vector<int> y, int wantedParity) · 258 test cases · 2 s / 256 MB per case