Connection Status:
Competition Arena > Reflections

Reflections

SRM 513 · 2011-05-25 · by ivan_metelsky

SRM 513 · 2011-05-25 · by ivan_metelsky · Search, Simple Math, Sorting
Class Name: Reflections
Return Type: long
Method Name: minimumMoves
Arg Types: (vector<int>, vector<int>, vector<int>, vector<int>)
Problem Statement

Problem Statement

Manao is playing a new game called Reflections. The goal of the game is transferring an artifact in 3-dimensional space from point (0, 0, 0) to point (X, Y, Z). There are two types of moves in the game:

1) The player can move the artifact by 1 unit in the direction of any coordinate axis. So, using this type of move, from point (a, b, c) the artifact can be moved to points (a + 1, b, c), (a - 1, b, c), (a, b + 1, c), (a, b - 1, c), (a, b, c + 1) or (a, b, c - 1).

2) The player can reflect the artifact against any one of the given planes. The reflection works as follows: the artifact disappears at its position before the reflection and appears on the other side of the plane at such a place that the line connecting the old and new positions is perpendicular to the plane and the old and new positions are equidistant from the plane. Reflection against each particular plane can be performed at most once during the game.

The planes are given as int[]s mirrorX, mirrorY and mirrorZ. mirrorX[i] corresponds to a plane perpendicular to the X axis with coordinate X = mirrorX[i]. mirrorY and mirrorZ contain planes perpendicular to the Y and Z axis in the same fashion. The target position is given in int[] finalPosition. finalPosition contains 3 elements, where finalPosition[0] is X, finalPosition[1] is Y and finalPosition[2] is Z.

Return the minimum possible number of moves which Manao will need to transfer the artifact.

Constraints

  • finalPosition will contain exactly 3 elements.
  • Each element of finalPosition will be between -1,000,000,000 and 1,000,000,000, inclusive.
  • mirrorX will contain between 0 and 20 elements, inclusive.
  • Each element of mirrorX will be between -1,000,000,000 and 1,000,000,000, inclusive.
  • All elements of mirrorX will be distinct.
  • mirrorY will contain between 0 and 20 elements, inclusive.
  • Each element of mirrorY will be between -1,000,000,000 and 1,000,000,000, inclusive.
  • All elements of mirrorY will be distinct.
  • mirrorZ will contain between 0 and 20 elements, inclusive.
  • Each element of mirrorZ will be between -1,000,000,000 and 1,000,000,000, inclusive.
  • All elements of mirrorZ will be distinct.
Examples
0)
{}
{}
{}
{901,-15761,10634}
Returns: 27296
1)
{}
{}
{}
{121239174,-169776576,46727479}
Returns: 337743229
2)
{}
{}
{}
{-942375608,890878630,592242030}
Returns: 2425496268
3)
{5016132}
{-4998477}
{4188859}
{4655104,-5038294,2984952}
Returns: 12598717
4)
{}
{}
{}
{-307,569,-611}
Returns: 1487
145)
{2}
{}
{}
{3, 0, 1}
Returns: 3

Manao can reflect the artifact against the only given plane, making it appear at (4, 0, 0). Afterwards, he can transfer it into the target position by two moves of the first type.

146)
{-5, 1, 4, 2, 3, 6, -6}
{}
{}
{9, 0, 0}
Returns: 2

A possible solution will be moving the artifact to (-1, 0, 0) and then reflecting it against the plane represented by mirrorX[2].

147)
{5, 8}
{}
{}
{4, 0, 0}
Returns: 4

If a reflection against a particular plane was allowed more than once, Manao could transfer the artifact in only three moves.

148)
{5}
{5}
{1, 2, 3}
{10, 12, -1}
Returns: 5

The planes perpendicular to the Z axis are of no use. After performing the reflections against the other two planes, Manao gets the artifact to point (10, 10, 0). Three more moves of the first type are required then.

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

Coding Area

Language: C++17 · define a public class Reflections with a public method long long minimumMoves(vector<int> mirrorX, vector<int> mirrorY, vector<int> mirrorZ, vector<int> finalPosition) · 173 test cases · 2 s / 256 MB per case

Submitting as anonymous