Statistics

Problem Statement for "Wireless"

Problem Statement

In a wireless network, the distance between nodes determines connectivity and latency. The further apart two nodes are the slower the connection. If two nodes are further apart than the maximum allowable range they cannot directly communicate. In our network, there will be 2 kinds of nodes: stationary and roaming. When a roaming node wants to communicate with another roaming node it must first communicate with one of the stationary nodes in its range. The stationary node it connects to will then send the transmission through as many stationary nodes as are necessary before finally sending to the destination roaming node. In other words, the transmission always starts at a roaming node, goes through one or more stationary nodes, and finally arrives at the destination roaming node. For example:
R = roaming, S = stationary
.......--R......
....../.........
.....S--........
........\.......
.........S......
.........|......
..R--.../.......
.....\-S........
Above is one possible route between the two depicted roaming nodes.
In this problem you will be given the initial positions of the roaming nodes and their initial velocities. Each roaming node will either be moving upward, leftward, rightward, or downward at the rate of one square per second. For example:
roamNodes Input Format: Direction X Y
roamNodes = {"UP 9 0","DOWN 2 6"}
statNodes Input Format: X Y
statNodes = {"5 2","9 4","7 7"}
      Time 0                  Time 1                  Time 2
 0123456789012345        0123456789012345        0123456789012345
0.......--R......       0................       0................
1....../.........       1....../--R......       1................
2.....S--........       2.....S..........       2.....S...R......
3........\.......       3..../...........       3.........|......
4.........S......       4.../.....S......       4..R------S......
5.........|......       5..R.............       5................
6..R--.../.......       6................       6................
7.....\-S........       7.......S........       7.......S........
Above are the positions of the nodes, and some possible routes.
We are going to assume that the routing protocol will always choose the shortest possible end-to-end (roaming node-to-roaming node) route when connecting two roaming nodes. You will be given the wireless range of all nodes, the positions and velocities of the roaming nodes, and the positions of the stationary nodes. You will determine the length of the shortest route that will ever occur between the two roaming nodes in the system at any non-negative integral time. The distance between two nodes is always measured using the cartesian distance formula: sqrt((x2-x1)^2 + (y2-y1)^2). The length of a route is the sum of the distances when travelling from node to node along the route. If two nodes share the same location, their distance is 0. Two nodes (Roaming to Static or Static to Static) can communicate if their distance is less than or equal to the given maximum range. Round final answers to the nearest integer. If the two roaming nodes could never communicate return -1. See examples for further clarification.

Create a class Wireless that contains the method bestRoute, which takes an int range, a String[] roamNodes, and a String[] statNodes and returns an int representing the length of the shortest route between the two roaming nodes in the system at any integral time greater than or equal to 0. If the two nodes could never communicate return -1.

Definition

Class:
Wireless
Method:
bestRoute
Parameters:
int, String[], String[]
Returns:
int
Method signature:
int bestRoute(int range, String[] roamNodes, String[] statNodes)
(be sure your method is public)

Notes

  • Two nodes (Roaming to Static or Static to Static) can communicate if their distance if less than or equal to the given maximum range.
  • Final answers must be rounded to the nearest integer (i.e. .5 and greater rounds up, below .5 rounds down)
  • All routes must start at a roaming node, pass through 1 or more static nodes, and complete at a roaming node.
  • UP means INCREASING Y coordinate whereas DOWN means DECREASING Y coordinate
  • RIGHT measn INCREASING X coordinate whereas LEFT means DECREASING X coordinate

Constraints

  • range will be between 1 and 30000 inclusive
  • roamNodes will contain exactly 2 elements
  • Each element of roamNodes will be of the form: Direction X Y where Direction is one of UP, DOWN, LEFT, or RIGHTX is an integer with no leading zeros between -10000 and 10000 inclusiveY is an integer with no leading zeros between -10000 and 10000 inclusive
  • statNodes will contain between 1 and 30 elements inclusive
  • Each element of statNodes will be of the form: X Y where X is an integer with no leading zeros between -10000 and 10000 inclusiveY is an integer with no leading zeros between -10000 and 10000 inclusive
  • The final answer will be within .4999 of the nearest integer.

Examples

  1. 1

    {"DOWN 100 200","DOWN 100 200"}

    {"1000 1000"}

    Returns: -1

    The roaming nodes will never be close enough to the static node to communicate.

  2. 30000

    {"DOWN 10000 10000","RIGHT -10000 -10000"}

    {"10000 -10000","10000 -10000"}

    Returns: 0

    They keep getting closer and closer until finally they all meet at the stationary node at (10000,-10000)

  3. 3000

    {"DOWN 0 10000","LEFT 10000 0"}

    {"14 100","25 -10","98 204","99 1000"}

    Returns: 49

  4. 30000

    {"DOWN 0 0","DOWN 0 0"}

    {"10000 10000","9000 10000","8000 10000","7000 10000"}

    Returns: 24413

  5. 20

    {"DOWN -20 0","DOWN 80 1"}

    {"0 0","20 0","40 0","60 1"}

    Returns: -1

  6. 20

    {"DOWN -10 10","DOWN 41 10"}

    {"0 0","10 10","21 0","31 10"}

    Returns: 59

  7. 10000

    {"DOWN 9 0","UP 2 6"}

    {"5 2","9 4","7 7"}

    Returns: 9

  8. 2000

    {"LEFT 10000 10000","DOWN 10000 10000"}

    {"-10000 8000","-10000 6000","-10000 4000","-10000 2000","-10000 0","-10000 -2000","-10000 -4000","-10000 -6000","-10000 -8000","-10000 -10000","8000 -10000","6000 -10000","4000 -10000","2000 -10000","0 -10000","-2000 -10000","-4000 -10000","-6000 -10000","-8000 -10000","-10000 -10000"}

    Returns: 40000

  9. 2222

    {"LEFT 10000 10000","DOWN 10000 10000"}

    {"-10000 7778","-10000 5556","-10000 3334","-10000 1112","-10000 -1110","-10000 -3332","-10000 -5554","-10000 -7776","-10000 -9998","7778 -10000","5556 -10000","3334 -10000","1112 -10000","-1110 -10000","-3332 -10000","-5554 -10000","-7776 -10000","-9998 -10000"}

    Returns: 39999

  10. 10000

    {"RIGHT 10000 10000","DOWN -10000 10000"}

    {"-10000 -10000","0 -10000","10000 -10000","10000 0","10000 10000"}

    Returns: 60000

  11. 100

    {"LEFT 150 150","RIGHT -150 -150"}

    {"-89 7","143 -81","-18 158","-154 -75","-116 34","-162 198","24 -21","-191 139","-66 64","38 111","-29 127","93 102","145 167","-115 -175","-179 -31","-39 -111","-39 -41","30 159","80 38","55 13","-76 114","13 -72","25 -194","179 -118","33 18","-13 177","192 -146","64 154","152 154","-73 -171"}

    Returns: 313

  12. 100

    {"DOWN 150 150","UP -150 -150"}

    {"-89 7","143 -81","-18 158","-154 -75","-116 34","-162 198","24 -21","-191 139","-66 64","38 111","-29 127","93 102","145 167","-115 -175","-179 -31","-39 -111","-39 -41","30 159","80 38","55 13","-76 114","13 -72","25 -194","179 -118","33 18","-13 177","192 -146","64 154","152 154","-73 -171"}

    Returns: 339

  13. 75

    {"RIGHT 0 0","LEFT 0 -150"}

    {"164 -87","-18 -70","-162 -15","-85 -18","155 132","139 -199","9 42","-30 150","63 -32","-86 112","35 -55","-169 107","17 8","-134 -89","-30 -78","-134 -84","160 -171","-161 111","100 99","58 -6","152 139","-66 -165","39 -195","11 -61","-87 24","24 -59","104 107","-18 -186","-34 -12","-169 -70"}

    Returns: 179

  14. 10000

    {"DOWN 0 200","RIGHT -10000 -10000"}

    {"164 -87","-18 -70","-162 -15","-85 -18","155 132","139 -199","9 42","-30 150","63 -32","-86 112","35 -55","-169 107","17 8","-134 -89","-30 -78","-134 -84","160 -171","-161 111","100 99","58 -6","152 139","-66 -165","39 -195","11 -61","-87 24","24 -59","104 107","-18 -186","-34 -12","-169 -70"}

    Returns: 17677

  15. 5000

    {"DOWN 7923 6455","UP -8442 -8111"}

    {"-3203 4987","-6003 967","7138 -7147","-2086 732","9029 -34","7634 -8425","5804 1916","-5985 -7565","-4629 7619","4267 8475","-5243 2108","-4077 -6419","6213 1797","1176 -9320","2473 -6362","6013 -7166","7402 -5986","-161 -2295","-2489 3193","3472 3381","9658 6858","-4009 -5519","-9219 7435","-5801 -5976","6554 -5077","-7496 8803","-2308 9347","5409 -6216","-5108 5201","-9868 4525"}

    Returns: 20908

  16. 6

    {"DOWN 0 50","LEFT 50 0"}

    {"-7 8","-13 11","-8 -14","-5 -13","0 -8","-11 1","6 -2","1 -7","-11 4","10 10","14 -8","-12 0","9 10","11 1","8 12","-9 -4","-14 11","-9 13","-12 9","-13 -8","6 -13","10 10","-14 8","1 -7","3 14","-11 -10","-13 -8","9 -11","-11 0","-1 9"}

    Returns: 27

  17. 5

    {"DOWN -10 10000","LEFT 10000 -1"}

    {"-7 2","-3 7","9 8","-3 3","9 4","7 -12","8 11","-2 -14","-8 -12","-11 -11","-12 7","-6 -9","-2 9","5 -2","-7 4","2 -11","5 4","-12 -14","7 -3","-6 10","0 -14","4 -10","4 12","-14 -6","-9 3","11 -11","-5 7","13 -2","5 0","4 0"}

    Returns: 13

  18. 3

    {"RIGHT -10000 0","LEFT 10000 5"}

    {"11 4","2 -1","3 4","6 -1","-13 -4","-10 0","9 -3","-3 -3","3 -1","-2 1","5 4","5 0","-6 -1","7 3","9 0","9 0","13 -3","11 4","-3 2","-6 2","-11 4","-1 2","-8 1","6 0","-4 -3","0 1","-2 0","-4 4","0 0","10 0"}

    Returns: 6

  19. 10000

    {"RIGHT 0 0","LEFT 10000 0"}

    {"11 4","2 -1","3 4","6 -1","-13 -4","-10 0","9 -3","-3 -3","3 -1","-2 1","5 4","5 0","-6 -1","7 3","9 0","9 0","13 -3","11 4","-3 2","-6 2","-11 4","-1 2","-8 1","6 0","-4 -3","0 1","-2 0","-4 4","0 0","10 0"}

    Returns: 9974

  20. 6992

    {"DOWN 1159 7593","DOWN 7227 6309"}

    {"-7731 -8344","-1262 4104","1395 440","6353 7283"}

    Returns: 6202

  21. 11782

    {"UP 3009 6607","RIGHT 9743 -945"}

    {"-8414 -6726","-2536 5441"}

    Returns: -1

  22. 4850

    {"DOWN -3787 -1513","DOWN 1872 6086"}

    {"969 1834","7139 -6068","-6604 5357","6751 -1786","-9393 3226","7573 6544"}

    Returns: -1

  23. 5650

    {"UP 4575 2019","RIGHT 6676 7031"}

    {"-6593 -494"}

    Returns: -1

  24. 20167

    {"LEFT 4262 2114","DOWN -8499 2973"}

    {"-1100 -1162","-2749 2567","-6235 -641","9858 5228","597 -4756"}

    Returns: 8519

  25. 21837

    {"RIGHT 2320 1329","UP 8424 -2449"}

    {"1537 6363","-2521 -3854","5769 -9580","4339 7127","4360 9963"}

    Returns: 12441

  26. 18719

    {"RIGHT -6006 6400","UP 9685 2388"}

    {"-4969 -3140","7529 -3702","8328 -7623","763 -321","3420 -8807","5898 -9974","-8798 -6737","-2343 -7911","6692 8620","9793 -3217"}

    Returns: 8306

  27. 8666

    {"DOWN 5651 374","DOWN 1621 2119"}

    {"-3879 -2097","-8310 -1307"}

    Returns: -1

  28. 26889

    {"RIGHT -3275 -7660","DOWN -5997 -4934"}

    {"5253 -9322","-3251 -7088","6917 3219","7875 3076","6233 -4743","9560 8271","6884 8178"}

    Returns: 3943

  29. 26138

    {"RIGHT -2278 -306","UP 802 -9852"}

    {"-4986 -5354","-6919 -5612","-9502 7455","9073 3620","558 3611","485 -3165","-4831 -404","5570 -9764"}

    Returns: 5048

  30. 11279

    {"LEFT 916 9557","UP 7552 8888"}

    {"-2433 -8989","-3448 -7695","-6546 4911","6023 -5415","-550 -5241"}

    Returns: -1

  31. 7870

    {"RIGHT 7942 -7351","UP 727 -8481"}

    {"1813 1737","-5263 8174"}

    Returns: -1

  32. 14820

    {"RIGHT -7641 -6836","UP -4793 -2713"}

    {"8739 7257","-1026 -2891","8498 7803","6211 8685","6087 4158","-3010 8537","8790 5820","2491 -2582","-335 2717","-7674 9642"}

    Returns: 10277

  33. 28050

    {"UP 3733 5162","UP -3500 8780"}

    {"4189 -5150"}

    Returns: 26233

  34. 15660

    {"LEFT 7718 3520","LEFT -8074 7993"}

    {"-5728 -3278","2450 -391"}

    Returns: 20014

  35. 10813

    {"DOWN 8177 1753","DOWN -3671 -6294"}

    {"-8610 -4336"}

    Returns: -1

  36. 13669

    {"LEFT -318 3322","UP -2088 8963"}

    {"585 3857","-3673 9423","5052 4195"}

    Returns: 6813

  37. 8730

    {"LEFT 5723 -3234","UP -4343 1849"}

    {"4937 3136","3465 -6383","-6846 603","1190 6758"}

    Returns: 15207

  38. 15119

    {"UP 6262 -2010","RIGHT 4497 1275"}

    {"1058 -8984","-1285 9094","-4137 -748","6526 5012","-23 8295","7858 2904","3430 -502"}

    Returns: 3579

  39. 8276

    {"RIGHT 2938 -6139","LEFT 7625 -7454"}

    {"977 122","-3356 1354","338 -2654"}

    Returns: 12899

  40. 1000

    { "DOWN 1 -1", "UP -1 1" }

    { "0 0" }

    Returns: 3

  41. 20000

    { "RIGHT -10000 -10000", "RIGHT -10000 -10000" }

    { "10000 10000", "10000 10000", "10000 10000", "10000 10000", "10000 10000", "10000 10000", "10000 10000", "10000 10000", "10000 10000", "10000 10000", "10000 10000", "10000 10000", "10000 10000", "10000 10000", "10000 10000", "10000 10000", "10000 10000", "10000 10000", "10000 10000", "10000 10000", "10000 10000", "10000 10000", "10000 10000", "10000 10000", "10000 10000", "10000 10000", "10000 10000", "10000 10000", "10000 10000", "10000 10000" }

    Returns: 40000

  42. 30000

    { "DOWN 0 0", "RIGHT -10000 0" }

    { "10000 10000", "9000 10000", "8000 10000", "7000 10000", "10000 1100", "9000 1100", "8000 1100", "7000 1100", "10000 1200", "9000 1200", "8000 1200", "7000 1200", "10000 1300", "9000 1300", "8000 1300", "7000 1300", "10000 1400", "9000 1400", "8000 1400", "7000 1400", "10000 1500", "9000 1500", "8000 1000", "7000 1500", "10000 1600", "9000 1600", "8000 1600", "7000 1600", "10000 1700", "9000 1700" }

    Returns: 19830

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.
This problem was used for: