ArmyTeleportation
SRM 645 · 2014-12-30 · by w10d
Problem Statement
King Janusz is in great trouble. His enemies have attacked his kingdom from a direction the king did not expect and now he must relocate his troops quickly. The desperate king asked the great sorcerer Mirek for help.
Mirek has three magic towers that are able to teleport troops. Each time a tower is activated, all soldiers get teleported to new locations. The new location is computed by reflecting the old position through the position of the activated tower. (In other words, the activated tower will be in the middle of each segment that connects the old and the new position of a soldier.)
The king can activate the towers in any order he likes. Each tower can be activated arbitrarily many times.
You are given the current locations of the troops in
The soldiers are not allowed to move in any way other than by teleportation. The order of soldiers does not have to be preserved. (For example, the soldier that started at (x1[0], y1[0]) may end at (x2[2], y2[2]).)
Return "possible" (quotes for clarity) if it is possible to reach the state in which there are soldiers at all desired locations. Otherwise, return "impossible".
Constraints
- x1, y1, x2 and y2 will have the same number of element which will be between 1 and 50, inclusive.
- xt and yt will have exactly 3 elements each.
- The points described by x1 and y1 are pairwise distinct.
- The points described by x2 and y2 are pairwise distinct.
- The points described by xt and yt are pairwise distinct.
- Each element of x1, y1, x2, y2, xt and yt will be between -1,000,000 and 1,000,000, inclusive.
{0, 1}
{0, 1}
{2, 1}
{4, 3}
{2, 3, 2}
{0, 1, 3}
Returns: "possible"
We have soldiers at (0,0) and (1,1). We want to have soldiers at (2,4) and (1,3). There are three towers: at (2,0), (3,1), and (2,3). Mirek can teleport the king's troops as follows: He will activate the tower at (2,0). One soldier will teleport from (0,0) to (4,0), the other from (1,1) to (3,-1). He will activate the tower at (3,1), teleporting the soldiers to (2,2) and (3,3). He will activate the tower at (2,3), teleporting the soldiers to (2,4) and (1,3), as desired.
{0, 1, 2}
{2, 4, 6}
{3, 5, 6}
{1, 1, 0}
{3, 1, -2}
{4, 2, 10}
Returns: "impossible"
The soldiers are standing in a line. It is impossible to change that during the teleportation.
{0, 1}
{1, 2}
{1, 2}
{2, 3}
{0, 0, 0}
{5, 3, 8}
Returns: "impossible"
Regardless of the order of teleportation, the soldier that starts at (0,1) will always have his x coordinate equal to zero. Therefore he will never reach any of the desired destinations.
{6, -5, 1}
{3, -10, -7}
{0, 11, 5}
{-5, 8, 5}
{0, -5, 4}
{-8, -9, -4}
Returns: "possible"
{3, 2, 1}
{1, 2, 3}
{4, 5, 6}
{6, 5, 4}
{-2, 5, 6}
{1, -3, 2}
Returns: "impossible"
{0}
{0}
{10}
{20}
{2,7,12}
{4,14,24}
Returns: "possible"
towers linearly dependent, possible division by 0
{0}
{0}
{11}
{22}
{3,4,6}
{6,8,12}
Returns: "impossible"
equation has a fractional solution but the answer is no
{-9210, 600, 4896, -2518, 9393, 8029, 6474, -4148, 5839, -1725, 1880, -7290, 5969, 907, 4122, 7259, 8711, 5686, 8001, 4204, -7005, 5700, 6142, -1223, -8554, 887, 1634, 1571, -2000, 2544, -6018, -7253, 1026, 7856, -3836, 19, -5473, 824, -1629, -7909, -8107, -5655, -5683, 9860, 1880, -2205, 1396, -144, -1097, -4152}
{5298, -9647, 7407, 1900, -2073, 899, -6000, 7207, 1718, -4483, -3176, 3070, -2871, 7479, -3280, 8073, -7607, -6614, -5182, -8894, -3969, -9169, 1334, 9218, 1683, -9472, 2486, -2206, -3152, 1588, -9462, -4166, 2430, 9062, -1668, 3428, -2234, -2737, -4748, 7032, 3440, 5350, -8453, -3183, -281, 5509, -3109, 1190, -7309, -6810}
{-52664, -42854, -38558, -45972, -34061, -35425, -36980, -47602, -37615, -45179, -41574, -50744, -37485, -42547, -39332, -36195, -34743, -37768, -35453, -39250, -50459, -37754, -37312, -44677, -52008, -42567, -41820, -41883, -45454, -40910, -49472, -50707, -42428, -35598, -47290, -43435, -48927, -42630, -45083, -51363, -51561, -49109, -49137, -33594, -41574, -45659, -42058, -43598, -44551, -47606}
{96492, 81547, 98601, 93094, 89121, 92093, 85194, 98401, 92912, 86711, 88018, 94264, 88323, 98673, 87914, 99267, 83587, 84580, 86012, 82300, 87225, 82025, 92528, 100412, 92877, 81722, 93680, 88988, 88042, 92782, 81732, 87028, 93624, 100256, 89526, 94622, 88960, 88457, 86446, 98226, 94634, 96544, 82741, 88011, 90913, 96703, 88085, 92384, 83885, 84384}
{-9752, -3873, 1283}
{3133, -1136, -5732}
Returns: "possible"
50 big tests with answer yes
{2393, -1669, 3476, -325, -9733, -5675, 2372, 7077, 54, 7422, 9518, 8038, 4251, -648, 7458, -3039, 8987, -7165, -9549, 1909, -6104, -3584, 7791, 2020, 9585, 561, -535, 5295, -1048, -1034, 1426, 6326, -6593, 4209, -6117, 4092, 2982, -6591, -716, -384, -147, -9463, 5582, 6468, -2553, -502, 1883, 4777, -4284, -2492}
{6951, 1513, 2752, -1489, -1405, 1941, -4691, 3021, 621, -5374, 5701, 4209, 6701, -9269, -497, -4876, 8364, 8775, 1398, 8815, -3756, 3567, -6847, -9220, 4909, 286, -5126, 7571, 9089, -2453, 4619, 4333, 4600, -3920, 7067, 4547, 6459, -5370, 9172, -5202, -2572, -1371, -7201, -9753, 12, 3335, 8613, -4696, 7275, 6277}
{79409, 83471, 78326, 82126, 91537, 87477, 79430, 74725, 81748, 74380, 72284, 73764, 77551, 82450, 74344, 84841, 72815, 88967, 91351, 79893, 87906, 85386, 74011, 79782, 72217, 81241, 82337, 76507, 82850, 82836, 80376, 75476, 88395, 77593, 87919, 77710, 78820, 88393, 82518, 82186, 81949, 91265, 76220, 75334, 84355, 82304, 79919, 77025, 86086, 84294}
{-996027, -990589, -991829, -987586, -987671, -991017, -984385, -992097, -989697, -983702, -994777, -993285, -995777, -979807, -988579, -984200, -997440, -997851, -990474, -997891, -985320, -992643, -982229, -979856, -993985, -989362, -983950, -996647, -998165, -986623, -993695, -993409, -993676, -985156, -996143, -993623, -995535, -983706, -998248, -983874, -986504, -987705, -981875, -979323, -989088, -992411, -997689, -984380, -996351, -995353}
{7116, 6320, 6357}
{-4433, 3817, 5978}
Returns: "impossible"
8 yes-tests with mini changes making them no-tests
{-34245, 18740, 29644, 29436, -43345, -41996, -9998, -11235, 25030, 35095, -48930, 3113, 27828, 43839, -28060, 30823, -38609, -28780, 8281, -33893, -15510, 49849, 27825, -19797, -5795, 20819, 26562, -40678, 25754, -22359, -44574, 9582, -35527, 37566, 39940, 34573, 18092, -29129, 21566, 2427, -48822, -23461, 48037, 8733, -15929, -12564, -19826, 22040, 20473, 47634}
{-28630, 9088, 23428, 32228, -43220, -35077, -43468, 13591, -43505, -29588, 48980, -4779, 38303, 45328, -3345, 34877, -48887, -317, 33267, 15883, -8998, -23357, 6093, 8092, -448, -7764, -5943, 22316, -11290, 17019, -44202, -35686, 1691, -39506, -22945, 8962, -4852, 34850, -4526, 10401, 34340, -429, 47163, -48876, -34254, 17375, -20567, -44361, -15934, -11230}
{-978705, -925720, -914816, -915024, -987805, -986456, -954458, -955695, -919430, -909365, -993390, -941347, -916632, -900621, -972520, -913637, -983069, -973240, -936179, -978353, -959970, -894611, -916635, -964257, -950255, -923641, -917898, -985138, -918706, -966819, -989034, -934878, -979987, -906894, -904520, -909887, -926368, -973589, -922894, -942033, -993282, -967921, -896423, -935727, -960389, -957024, -964286, -922420, -923987, -896826}
{-12502, 25216, 39556, 48356, -27092, -18949, -27340, 29719, -27377, -13460, 65108, 11349, 54431, 61456, 12783, 51005, -32759, 15811, 49395, 32011, 7130, -7229, 22221, 24220, 15680, 8364, 10185, 38444, 4838, 33147, -28074, -19558, 17819, -23378, -6817, 25090, 11276, 50978, 11602, 26529, 50468, 15699, 63291, -32748, -18126, 33503, -4439, -28233, 194, 4898}
{-32497, -5267, 13234}
{16541, 45209, 26828}
Returns: "impossible"
50 tests generated using different towers
{0}
{0}
{674898}
{-334590}
{3,-4,3}
{0,1,-5}
Returns: "impossible"
I got a bug saying 'yes' on this test
Submissions are judged against all 144 archived test cases, of which 11 are shown here. Case numbers match the judge’s.
Language: C++17 · define a public class ArmyTeleportation with a public method string ifPossible(vector<int> x1, vector<int> y1, vector<int> x2, vector<int> y2, vector<int> xt, vector<int> yt) · 144 test cases · 2 s / 256 MB per case