TopCoder Statistics - Problem Statement

Problem Statement

You are a frog. You live on an infinite lattice of grid points. For each pair of integers x, y there is a grid point with coordinates (x,y). At this moment, you sit on the grid point (xMe,yMe). You want to get home: to the grid point (xHome,yHome).

There are two ways in which you can travel. Your first option is jumping: if you are at (x,y), you can jump to one of the four neighboring grid points: (x+1,y), (x-1,y), (x,y+1), or (x,y-1). Each jump takes one second.

Your second option is using a teleport. There are three teleports in the entire world. Each of them connects two different grid points. If you are at one of the endpoints, you may activate the teleport and travel to its other endpoint. Traveling by teleport takes 10 seconds.

You are given ints xMe, yMe, xHome, yHome, and a String[] teleports that describes the three teleports. Each element of teleports will be a String containing four integers x1, y1, x2, and y2, separated by single spaces. These integers describe a teleport with endpoints at (x1,y1) and (x2,y2).

Your method must return the shortest time in which you can reach your home.

Definition

Class:: ThreeTeleports
Method:: shortestDistance
Parameters:: int, int, int, int, String[]
Returns:: int
Method signature:: int shortestDistance(int xMe, int yMe, int xHome, int yHome, String[] teleports)
(be sure your method is public)

Notes

Traveling by a teleport is not mandatory. You may pass through its endpoint and decide not to use it.

Constraints

xMe, yMe, xHome, and yHome will all be between 0 and 1,000,000,000, inclusive.
teleports will have exactly three elements.
Each element of teleports will have the following format: "x1 y1 x2 y2" (quotes for clarity), where x1, y1, x2, and y2 are integers between 0 and 1,000,000,000, inclusive. The integers x1, y1, x2, and y2 will not contain unnecessary leading zeroes.
All eight points (your location, the location of your home, and the six teleport endpoints) will be pairwise distinct.

Examples

3

3

4

5

{"1000 1001 1000 1002", "1000 1003 1000 1004", "1000 1005 1000 1006"}

Returns: 3

The frog must make at least 3 leaps. For example, from (3,3) to (3,4), then to (3,5), and finally to (4,5). The teleports are all too far away to be useful.
0

0

20

20

{"1 1 18 20", "1000 1003 1000 1004", "1000 1005 1000 1006"}

Returns: 14

The journey can be done in 40 jumps = 40 seconds, but there is a better solution: Make 2 jumps to get from (0,0) to (1,1), use the teleport to get to (18,20), and make 2 jumps to get to (20,20). This solution takes (2+10+2) = 14 seconds.
0

0

20

20

{"1000 1003 1000 1004", "18 20 1 1", "1000 1005 1000 1006"}

Returns: 14

The teleports may be used in either direction, and in any order.
10

10

10000

20000

{"1000 1003 1000 1004", "3 3 10004 20002", "1000 1005 1000 1006"}

Returns: 30
3

7

10000

30000

{"3 10 5200 4900", "12212 8699 9999 30011", "12200 8701 5203 4845"}

Returns: 117

Sometimes the best solution requires us to use more than one teleport. In this case, the optimal solution looks as follows: Using jumps, travel to (3,10). Use the first teleport. Using jumps, travel from (5200,4900) to (5203,4845). Use the third teleport. Using jumps, travel from (12200,8701) to (12212,8699). Use the second teleport. Using jumps, travel from (9999,30011) to (10000,30000).
0

0

1000000000

1000000000

{"1 1 2 2", "3 3 4 4", "5 5 6 6"}

Returns: 2000000000
0

1000000000

1000000000

0

{"1 1 2 2", "3 3 4 4", "5 5 6 6"}

Returns: 2000000000
0

0

1000000000

1000000000

{"0 1 0 999999999", "1 1000000000 999999999 0", "1000000000 1 1000000000 999999999"}

Returns: 36

Watch out for overflows. The correct return value will always fit into a int, but some other paths may be very long.
7

2

999999991

4

{"0 1 0 999999999", "1 1000000000 999999999 0", "1000000000 1 1000000000 999999999"}

Returns: 42
10

500000000

1000000000

1000000000

{"0 1 0 999999999", "1 1000000000 999999999 0", "1000000000 1 1000000000 999999999"}

Returns: 500000032
100000000

500000000

900000000

500000000

{"0 1 0 999999999", "1 1000000000 999999999 0", "1000000000 1 1000000000 999999999"}

Returns: 800000000
100000000

100000000

900000000

900000000

{"0 1 0 999999999", "1 1000000000 999999999 0", "1000000000 1 1000000000 999999999"}

Returns: 400000032
0

0

1000000000

1000000000

{"10 10 20 20", "30 30 40 40", "50 50 60 60"}

Returns: 1999999970
630664613

48733225

873984926

111605493

{ "496495503 532857995 6389190 205314732" , "351146273 99276298 616908938 737305630" , "149168564 223552081 896571830 750247780" }

Returns: 306192581
50408182

27065196

71243950

211493804

{ "460798245 193700180 768780978 110314044" , "161021468 381388250 38241460 277796212" , "132401597 100164166 555601411 757948526" }

Returns: 205264376
712631043

118540020

532788793

140802423

{ "260045739 373051551 534047058 967908021" , "420942603 167942392 1752658 859937375" , "928889958 363876166 948383842 599106823" }

Returns: 202104653
546584061

324784219

966183692

999475275

{ "661541168 612406094 429392943 370311369" , "680615656 677465501 325928495 616181925" , "547062176 137391772 718766719 174029970" }

Returns: 854429983
866154370

322991744

210516672

546263750

{ "96594644 804330222 205018575 615354689" , "672041722 224166329 767001599 433866842" , "829621741 766952971 35347560 237749511" }

Returns: 878909704
813300993

984676869

954874690

294675479

{ "547128517 972299039 241873242 209633570" , "884270246 526283458 348993624 663818661" , "443452221 232587364 147469751 396526508" }

Returns: 831575087
824232356

763852653

316650882

317179572

{ "666331214 94848296 477923139 276070409" , "399770590 652426803 611280619 557969047" , "387720696 51570693 580888001 747874855" }

Returns: 596000856
272910313

968932248

211109133

454430785

{ "276284707 433053339 420117411 756213781" , "463896611 622885230 316291167 744006274" , "882163211 914764017 201629599 992297292" }

Returns: 446478595
333373883

162127112

758288658

535408203

{ "301497316 99178126 799699526 915898169" , "510380099 847661103 663240458 643662878" , "516479190 886338396 630580976 727878106" }

Returns: 516726397
513658547

74790663

649497119

4513793

{ "897416087 150884582 338400872 733815494" , "317208874 536047322 304705529 828936845" , "876575 650834011 927727672 614182273" }

Returns: 206115442
890781683

725016422

223949611

729365455

{ "837010969 527691546 465582551 801723024" , "53348214 899908371 238290034 675589157" , "378572645 776632317 67054402 300225591" }

Returns: 565086109
671841872

266168722

761730781

351958038

{ "377298076 821197206 600551083 929681356" , "474188466 626805504 181527483 556858312" , "123521315 82002428 223621568 656571357" }

Returns: 175678225
113609575

199402546

971590229

883308753

{ "744525829 50839519 958841937 382679275" , "163149158 740144914 392701099 790710178" , "472377598 380977537 444595305 723543772" }

Returns: 1227102929
34745001

812395769

978246999

451840145

{ "535143777 712994346 29745647 117880392" , "170907737 778817344 196765135 218545545" , "851728243 112142809 437824671 175015147" }

Returns: 920547207
238531736

490888840

818814410

289729074

{ "49633963 630835852 380961180 442790597" , "987665175 651154119 683443633 862022026" , "165297338 279480238 832064542 526237341" }

Returns: 534401409
726193834

757504680

110855185

371980211

{ "221032227 914814041 177485617 599940635" , "143241481 504287599 116315997 508799197" , "467907376 904218420 8586378 467750868" }

Returns: 603039672
521929712

318949212

953456006

988385697

{ "888889590 491833199 453233527 579263848" , "254546297 955685711 462575961 294916199" , "467724564 950513093 670863496 432807182" }

Returns: 786395810
6346093

433210778

990738508

655051170

{ "838325312 552167142 978083117 809531431" , "85317813 536122004 81312943 111391313" , "452715627 313591789 202784053 331060" }

Returns: 1118071245
23703008

294481282

879597716

890702265

{ "548714867 864135503 299644062 152852762" , "744500033 326837995 758408571 796371805" , "588539897 957430875 542141665 246273536" }

Returns: 775019195
145498650

392127453

106767214

175331073

{ "535104496 227065053 131260293 229282354" , "799049409 992413071 551610714 493058672" , "997181444 979615910 515667313 732225457" }

Returns: 255527816
43767499

293613968

923531489

877694217

{ "43766240 293262939 422848910 391571754" , "423570510 391739114 860143685 364709398" , "859696623 365194596 922682678 877070828" }

Returns: 3645738
257303836

567013022

559816427

455017415

{ "908198683 645993163 102156109 463093409" , "559129648 454419496 101580415 463430281" , "907886971 646772770 256344090 566821070" }

Returns: 4440311
251747174

214945386

915592983

47527

{ "46330587 376224822 343332664 837421511" , "342600537 838350568 916109879 795241" , "46508754 375623483 252326212 214982438" }

Returns: 4321420
730373425

894753427

242867242

580292800

{ "731370559 894260538 172085400 979696883" , "363158 916339097 172202330 980134715" , "1092044 916434891 242013485 579549409" }

Returns: 4466643
44431990

149823130

366572829

342647922

{ "256908645 198313227 709862831 854534743" , "710540444 855250605 44064139 150465583" , "257583322 198383935 366941723 343167644" }

Returns: 4037810
26554310

445514835

921490406

189666250

{ "232701270 702993783 27114202 445183655" , "232197206 703689877 867358576 813207569" , "922407358 189531062 866873232 813512913" }

Returns: 3934088
806025998

977572157

137475848

518499417

{ "300541907 750846639 261777803 20498007" , "806086410 977277507 299630466 751837744" , "137470494 518212575 260805942 20756966" }

Returns: 3780654
172221514

635197135

513983821

30256221

{ "228570717 762145365 171563344 635477977" , "514432142 30864120 246132856 854567327" , "229215795 762882261 246873370 855236210" }

Returns: 4786633
484243167

568782388

635773238

553089901

{ "433961062 561211307 731058277 471001013" , "635422730 552873347 433722128 562168089" , "484182728 569260814 730742352 471974824" }

Returns: 3591409
888440684

918829226

463020864

489848629

{ "888499837 917836841 37096754 270276299" , "36615580 270408718 204642168 268085611" , "462714380 489547658 203676351 267919738" }

Returns: 3404306
847805538

349559051

718319133

781723914

{ "848735459 349913415 875148587 836885115" , "853355015 139284922 717935849 781696273" , "853922317 139254496 875553612 836359458" }

Returns: 3223650
972542529

533951492

404979554

524765571

{ "54197249 420779627 658459747 295997579" , "404840511 524223595 657614524 296528492" , "972648462 534303792 54861802 421546927" }

Returns: 3947271
922397295

120406410

946248138

902180543

{ "968688738 508615169 947154032 901341020" , "922035635 119733598 505998745 436520840" , "506560174 436417638 968296341 508660983" }

Returns: 3882761
140442590

423955552

381051282

739157713

{ "817785273 844831633 807923175 758265776" , "807505937 757728853 141318993 424271395" , "380472740 740100286 817007921 845037669" }

Returns: 4650940
265812178

546280252

199699268

797385816

{ "767300196 303589461 200493762 796484481" , "185452201 185667426 766498232 304308185" , "265722902 547031623 185297155 185986578" }

Returns: 4531392
632841087

294160314

329243573

743769717

{ "743660503 752676070 376957534 447358131" , "743084539 753638725 633770263 293932260" , "377237876 448284125 329013656 743251417" }

Returns: 4650432
361636101

203058830

434802682

881001269

{ "221381092 261647733 360887805 202979837" , "434024867 880063690 562486609 644340562" , "561595250 645213325 221678001 260880078" }

Returns: 5371399
9649579

460291009

5078017

414501854

{ "3726072 525772909 891715551 699525377" , "3963892 526707921 10367369 459902547" , "892241242 698944467 5573758 414937410" }

Returns: 4317012
760370766

313775395

436426943

133380682

{ "760509378 314607049 981117324 144817332" , "342167113 210421618 981616998 145710117" , "342799252 210073412 435501254 133316968" }

Returns: 4332503
415423343

524068936

871257497

510345517

{ "166734363 756275100 483158338 186218485" , "165862224 755668983 415920710 523303262" , "871082452 509851953 482192307 186533833" }

Returns: 4691315
408709545

19818312

907384075

935316792

{ "908013745 936128408 408766869 19792665" , "907700932 935589088 408222639 20044607" , "906906269 935720441 408683231 19615732" }

Returns: 1110359
678896388

272811031

974078426

686078654

{ "975017215 685758903 678906491 272803813" , "974676866 685915435 678572249 273284657" , "974247459 686825470 679414142 272893204" }

Returns: 1275871
834690520

940005356

958288744

8948665

{ "957592754 8653203 835460756 939933504" , "834998702 940724437 959022890 9627275" , "835227301 940899508 958130690 9331917" }

Returns: 1833550
860336881

6062489

565263345

621528510

{ "859658631 6004615 565888255 620711850" , "859926272 6954049 564361902 621511067" , "564631673 621041364 859899536 6038574" }

Returns: 1580088
553455458

915427850

12558279

382265250

{ "553123299 914597814 12313069 382684524" , "554028822 915928902 12858951 382663825" , "554322441 915834138 13368240 381912317" }

Returns: 1773673
883668557

648159861

725143100

363296639

{ "725987322 363002914 884256666 649095099" , "883913159 648543784 726045820 362936145" , "883509057 647192604 725410094 364060451" }

Returns: 1891749
57410944

767040452

442440953

202788472

{ "443351874 203641790 57320885 766384843" , "443434206 201903966 57988518 766691811" , "442668676 203163481 57393912 766065785" }

Returns: 1594441
655895284

670602750

15785618

752456236

{ "15098545 751733030 656876365 670352215" , "655132632 671281532 16702367 751800318" , "15940240 752817614 655841285 671117169" }

Returns: 1084428
216564110

232397552

663275024

217633078

{ "663089563 218618259 217423090 231502831" , "662994348 216866075 217342483 232800025" , "663471159 218550458 216318662 232136976" }

Returns: 1619549
310401578

851184245

945105322

826414352

{ "945634105 826112125 311004685 851742792" , "945712756 826876436 310586196 851789967" , "309518520 851821934 945666020 826366500" }

Returns: 1859868
140529534

778518573

421124743

902221938

{ "420464081 901986466 140769925 778200802" , "140123764 779311194 421946918 901656305" , "140146583 779165308 420195493 902719178" }

Returns: 1454306
172612040

218257441

479447071

954584480

{ "480081384 954546952 172350045 218221178" , "172512847 217555053 478775303 954659375" , "479248236 955087303 172067841 217534668" }

Returns: 970109
365148679

516462508

262445444

854069332

{ "364595394 516628551 262378156 855055435" , "261529527 853236558 364819650 517347108" , "262578930 853982244 364790325 515590378" }

Returns: 1451068
943571916

789588185

27475276

191482273

{ "942855606 790455407 27002990 192178557" , "944484156 788843306 27199778 191479818" , "27414378 190509090 944204209 790480792" }

Returns: 1935082
884679002

526275681

344998300

877963230

{ "885093350 525281944 345752526 877149167" , "885476268 526368121 345867073 877065320" , "345135154 878342657 885153968 525573813" }

Returns: 1693125
260633944

764469353

447834027

260101624

{ "260203725 763952424 447979553 260939680" , "447953426 260140251 259770878 765372207" , "261133629 764276065 447343759 260069695" }

Returns: 1215180
456105671

672341185

160456638

1542670

{ "159578348 1057696 455535149 673275958" , "159905957 1767193 455115669 672513105" , "457055197 671916146 159521177 1975481" }

Returns: 1937136
219563023

657800264

161354481

990960963

{ "219715046 658052159 160433557 991306084" , "220274019 658476931 162228969 991207664" , "162001360 991472930 219295899 657259520" }

Returns: 1669973
871816760

773474856

69431425

582201089

{ "68549041 582125418 872374087 772811290" , "871091348 773871328 69888587 582681865" , "871654744 773597092 70073195 583080619" }

Returns: 1805562
723552702

446044757

506632797

212654751

{ "722647315 445855628 506673455 211929595" , "506032528 213289618 723983513 446994815" , "507242513 213198187 724300993 446713353" }

Returns: 1860340
643729313

579469950

458675469

564240749

{ "643737194 579541992 292324374 575773962" , "459114022 564318234 644488528 579128105" , "458680424 564330752 292270286 575795554" }

Returns: 250581
645480437

30976971

642491624

813956858

{ "440826652 674992349 645464695 30940501" , "645813109 31197660 641501668 813884275" , "642411071 814042803 440923466 674932455" }

Returns: 375438
194908615

399537617

480772206

679952356

{ "710432895 532260636 480829253 679992698" , "481347899 680307272 194314622 400188243" , "194846489 399496469 710359037 532324233" }

Returns: 338138
188203740

894001326

611862458

112072569

{ "187601640 893974686 612735834 111346634" , "664716824 754351240 188237572 893968702" , "611876923 112140395 664649713 754308748" }

Returns: 258370
410334001

976686045

548006854

959698717

{ "409398287 976182602 547051880 959444509" , "548651986 959251373 992348428 235453981" , "993330733 235549593 411032437 977655203" }

Returns: 2648349
108123087

218083574

952167030

281512065

{ "951647202 281079347 108031518 217793901" , "851133055 344629831 108157750 218105234" , "851093848 344571693 952140430 281593011" }

Returns: 261234
640961680

9800688

547936182

125596476

{ "227584670 160515679 640974387 9769446" , "640832367 9130963 546963385 126242387" , "547879147 125609937 227603148 160465892" }

Returns: 182730
743695770

736162224

791258070

134616547

{ "744652576 735580925 784725497 815048519" , "790697228 133837596 743821409 735970918" , "791412760 134665885 785065310 814300896" }

Returns: 1656748
80301858

826413595

409044578

289436766

{ "603571157 421362949 409089649 289364578" , "408329576 289469617 80677380 826459196" , "79635990 826855332 604350031 422092195" }

Returns: 1168986
402997626

974866052

410601023

976666447

{ "257874349 353667986 410599639 976626671" , "410841963 977392295 402106060 974643252" , "257774403 353733269 403086520 974928667" }

Returns: 357918
163273342

152247602

436640006

52351390

{ "163225303 152774985 436300752 52576578" , "436635464 52427408 629247185 684839214" , "629296406 684872457 163182903 152291382" }

Returns: 297263
267117142

660278827

988066327

971801584

{ "184548180 47599697 267162850 660365634" , "988302068 970995435 266454704 659766440" , "184525595 47533464 988123241 971750794" }

Returns: 329057
105265889

372130284

295586799

278164339

{ "295373298 277524134 104716469 371718656" , "743404192 163670744 105294517 372069038" , "743412272 163740330 295540550 278193405" }

Returns: 242875
450438763

543262536

907778177

341091975

{ "907166811 341265177 451308981 543540165" , "907586189 341089958 489844366 784580910" , "489297290 784717296 450764017 543771023" }

Returns: 1711228
727930453

792916213

535371809

496301091

{ "534398597 496319596 382099332 257994564" , "535915505 496371603 727996727 792323561" , "728106404 793394649 382376820 257969280" }

Returns: 1273144
797762822

105049316

501338537

963127925

{ "502122596 962253685 107133342 852206971" , "798054002 105980808 107903206 852919413" , "500949508 962401626 797693327 104888829" }

Returns: 1345320
479701668

55648194

790815034

931331108

{ "480103474 55315516 791765669 931354967" , "790106620 931658623 864533988 536949875" , "479157797 55937404 865123715 536354907" }

Returns: 1708988
558494097

471878520

747970147

137526654

{ "747031025 137237805 699409969 431028574" , "558554643 471217710 698729696 430541959" , "748894468 136601188 559119718 471786887" }

Returns: 2567051
499739134

998104108

103065617

36342563

{ "907475399 854269762 499663207 998158032" , "907535851 854229365 103144343 36366227" , "102387995 35913426 498742368 997641357" }

Returns: 333110
301113766

787205896

391837360

214797774

{ "391903320 214716644 604288997 590754091" , "301571157 786718547 391789985 215403869" , "301144315 787258921 604376632 590674984" }

Returns: 397426
1

1

1000

1000

{"0 1 1 0", "2 1 1 2", "3 3 4 4"}

Returns: 1998
0

0

1000000000

1000000000

{"0 1 0 999999999", "1 1000000000 999999999 0", "1000000000 1 1000000000 999999999" }

Returns: 36
0

0

100000000

100000000

{"999999999 999999999 555555555 555555555", "5 6 1 1", "444444444 444444444 555555556 555555556" }

Returns: 200000000
0

0

999999993

999999993

{"999999970 999999970 999999995 999999995", "999999996 999999996 999999997 999999997", "999999998 999999998 999999999 999999999" }

Returns: 1999999954
0

0

10000

10000

{"1 1 50 50", "52 52 8000 8000", "7700 7700 9999 9999" }

Returns: 638
0

0

1000000000

1000000000

{"1 1 2 2", "3 3 4 4", "5 5 6 6" }

Returns: 2000000000
0

0

1000000000

1000000000

{"1 1 2 2", "6 6 3 3", "4 4 5 5" }

Returns: 2000000000
0

0

1000000000

1000000000

{"999999999 999999998 999999998 999999999", "999999997 99999998 999999996 999999998", "999999999 999999996 999999997 1000000000" }

Returns: 1100000011
3

3

199999999

123123123

{"1 2 2 3", "1000 1000 230000 200000", "300 300 3333333 3333333" }

Returns: 316457060
0

0

1000000000

1000000000

{"0 999999998 0 999999999", "1 1000000000 999999999 0", "1000000000 999999998 1000000000 999999999" }

Returns: 2000000000
0

0

20

20

{"1000 1003 1000 1004", "18 20 1 1", "1000 1005 1000 1006" }

Returns: 14
3

7

10000

30000

{"3 10 5200 4900", "12212 8699 9999 30011", "12200 8701 5203 4845" }

Returns: 117
1000000000

1000000000

1

999

{"100000 1004 99998 1001", "99999 1002 3 997", "2 998 1 99" }

Returns: 1999899013
0

0

1000000000

1000000000

{"999999999 1000000000 1000000000 999999999", "999999998 1000000000 1000000000 999999998", "999999999 999999999 1 1" }

Returns: 14
1000000000

1000000000

1

990

{"100000 1004 99998 1001", "99999 1002 3 997", "2 998 1 99" }

Returns: 1999899018

Statistics

Problem Statement for "ThreeTeleports"

Problem Statement

Definition

Notes

Constraints

Examples