Statistics

Problem Statement for "Amazing"

Problem Statement

We are designing an Amazing Race course. Contestants will travel back and forth between various cities. We want to choose the required sequence of cities so that the total effort of a contestant is as close as possible to 1000.

The total effort of a contestant is the sum of the effort for each city-to-city trip, but the effort for a trip depends on how tired the contestant is. Let effort(c1,c2) be the effort required to travel from city c1 to city c2 when a contestant is fresh. We estimate that if the contestant has already completed k trips then the effort required for a trip from city c1 to city c2 is

                 factork *  effort(c1,c2)
where factor is a fixed value >= 1.

Create a class Amazing that contains a method totalE that is given factor, numTrips, and a String[] effort. Each element of effort contains a single space separated list of integers. The jth integer in the ith element of effort is effort(ci,cj). Your method should find the race course with exactly numTrips trips that comes closest to requiring a total effort of 1000, and return the absolute difference between that total effort and 1000.

A trip may go from a city to itself, and effort(ci,ci) is not necessarily 0.

Definition

Class:
Amazing
Method:
totalE
Parameters:
double, int, String[]
Returns:
double
Method signature:
double totalE(double factor, int numTrips, String[] effort)
(be sure your method is public)

Notes

  • Your return value must have an absolute or relative error less than 1e-9.

Constraints

  • factor will be between 1.0 and 2.0, inclusive.
  • numTrips will be between 1 and 10, inclusive.
  • effort will contain n elements where n is between 1 and 10, inclusive.
  • Each element of effort will contain exactly n non-negative integers separated by single spaces.
  • Each element of effort will contain no leading spaces and no trailing spaces.
  • Each integer in each element of effort will be between 0 and 1000, inclusive, and contain no leading zeroes.

Examples

  1. 1.0

    2

    {"1000 300 700","200 0 901","35 100 0"}

    Returns: 1.0

    One course requires contestants to start in city 1, then travel to city 2, and then back to city 1. The total effort would be 1001. The only other equally good course would be to start in city 2, then travel to city 1 and then back to city 2.

  2. 2.0

    2

    {"1000 300 700","200 0 901","35 100 0"}

    Returns: 29.0

    Now that the tiredness factor is 2.0, the courses from the previous example would require too much effort (1101 and 1902 respectively). The best course would be to start at city 1, go to city 2 at an effort of 901 and then to city 0 with an additional effort of 2.0*35 giving a total of 971.

  3. 1.3

    10

    {"1000 300 700","200 0 901","35 100 0"}

    Returns: 2.8999999999998636

  4. 1.2

    10

    {"3 3 5 6 7 8 9 10 100 95","3 3 5 6 7 8 9 10 100 95","3 3 5 6 7 8 9 10 100 95","3 4 5 6 7 8 9 10 100 95","3 4 5 6 7 8 9 10 100 95","3 4 5 6 7 8 9 10 100 95","3 4 5 6 7 8 9 10 100 95","3 4 5 6 7 8 9 10 100 95","3 4 5 6 7 8 9 10 100 95","3 4 5 6 7 8 9 10 100 95"}

    Returns: 0.0

  5. 2.0

    10

    {"3 3 5 6 7 8 9 10 100 95","3 3 5 6 7 8 9 10 100 95","3 3 5 6 7 8 9 10 100 95","3 4 5 6 7 8 9 10 100 95","3 4 5 6 7 8 9 10 100 95","3 4 5 6 7 8 9 10 100 95","3 4 5 6 7 8 9 10 100 95","3 4 5 6 7 8 9 10 100 95","3 4 5 6 7 8 9 10 100 95","3 4 5 6 7 8 9 10 100 95"}

    Returns: 2069.0

  6. 2.0

    10

    {"990 90 990 990 999 921 991 991 991 311","990 988 0 990 993 992 991 991 991 311","990 988 990 0 993 922 991 991 991 311","990 988 990 990 18 992 991 991 991 311","990 988 990 1 999 2 991 991 991 311","990 988 990 990 9 992 1 991 991 311","990 898 990 990 999 992 991 1 991 311","990 988 990 990 999 929 991 991 1 311","990 988 990 990 0 992 991 991 991 311","990 988 990 990 999 992 991 991 991 311"}

    Returns: 2.0

    ab bc cd de ef fg gh hi ie ed 88 0 0 144

  7. 2

    10

    {"990 88 990 990 999 921 991 991 991 311","990 988 0 990 993 992 991 991 991 311","990 988 990 0 993 922 991 991 991 311","990 988 990 990 18 992 991 991 991 311","990 988 990 1 999 2 991 991 991 311","990 988 990 990 9 992 1 991 991 311","990 898 990 990 999 992 991 1 991 311","990 988 990 990 999 929 991 991 1 311","990 988 990 990 0 992 991 991 991 311","990 988 990 990 999 992 991 991 991 311"}

    Returns: 0.0

  8. 1.0

    10

    {"990 88 990 990 999 921 991 991 991 311","990 988 0 990 993 992 991 991 991 311","990 988 990 0 993 922 991 991 991 311","990 988 990 990 18 992 991 991 991 311","990 988 990 1 999 2 991 991 991 311","990 988 990 990 9 992 1 991 991 311","990 898 990 990 999 992 991 1 991 311","990 988 990 990 999 929 991 991 1 311","990 988 990 990 0 992 991 991 991 311","990 988 990 990 999 992 991 991 991 311"}

    Returns: 0.0

  9. 1.1

    10

    {"990 88 990 990 999 921 991 991 991 311","990 988 0 990 993 992 991 991 991 311","990 988 990 0 993 922 991 991 991 311","990 988 990 990 18 992 991 991 991 311","990 988 990 1 999 2 991 991 991 311","990 988 990 990 9 992 1 991 991 311","990 898 990 990 999 992 991 1 991 311","990 988 990 990 999 929 991 991 1 311","990 988 990 990 0 992 991 991 991 311","990 988 990 990 999 992 991 991 991 311"}

    Returns: 0.9984372609999355

  10. 1.4

    10

    {"1 2 3 4 5 6 7 8 9 10","2 3 4 5 6 7 8 9 10 1","3 4 5 6 7 8 9 10 1 2","4 5 6 7 8 9 10 1 2 3","5 6 7 8 9 10 1 2 3 4", "6 7 8 9 10 1 2 3 4 5","7 8 9 10 1 2 3 4 5 6","8 9 10 1 2 3 4 5 6 7","9 10 1 2 3 4 5 6 7 8","10 1 2 3 4 5 6 7 8 9"}

    Returns: 301.86336256000016

  11. 2

    1

    { "250 569 565 489 247 434 918 11 536", "16 387 975 859 575 734 207 829 231", "541 415 964 402 540 456 157 959 574", "84 319 509 452 653 754 738 101 186", "608 813 953 37 454 852 924 325 326", "146 48 851 821 650 799 110 517 395", "350 228 594 885 929 647 538 286 485", "341 592 382 688 744 527 276 779 336", "597 341 831 995 902 149 399 76 629"}

    Returns: 5.0

  12. 1.2021064934944823

    9

    { "11"}

    Returns: 769.1286345469899

  13. 1.198274255699284

    1

    { "709 468 825 601 803 453 556 56 194 943", "164 488 604 744 483 948 572 401 507 0", "366 841 656 171 168 662 489 923 836 672", "339 14 649 90 178 210 550 604 475 712", "733 66 154 78 459 192 544 196 451 951", "403 444 764 34 819 408 356 405 860 443", "206 896 629 105 850 78 29 880 811 133", "782 920 758 116 85 914 801 970 719 216", "86 855 791 204 887 550 67 715 698 636", "390 870 625 934 964 863 586 87 94 396"}

    Returns: 30.0

  14. 1.7129786602289676

    5

    { "152 184 124 765 645 330 608 586 662 205", "465 96 653 807 943 46 881 286 702 47", "954 130 348 34 156 849 692 106 986 997", "703 505 867 512 107 456 560 31 967 603", "864 812 271 706 906 329 349 122 759 55", "230 518 187 173 175 666 181 691 107 105", "232 754 84 271 698 561 346 690 741 989", "18 757 504 190 438 983 76 724 784 437", "585 72 524 265 351 195 714 21 665 308", "523 300 603 76 316 551 795 510 253 537"}

    Returns: 2.581806118796294

  15. 1.9594891786402466

    9

    { "787 527 221 400 644 337 733 463", "906 711 828 555 342 238 227 317", "397 12 379 419 792 467 538 741", "780 242 338 448 499 126 800 451", "190 955 567 902 134 118 222 860", "908 665 172 247 235 89 363 210", "222 468 629 462 743 216 876 352", "14 992 423 590 853 56 505 592"}

    Returns: 30848.60410363156

  16. 1.8558249701744756

    5

    { "754 903 849 812 971", "579 147 249 145 992", "273 428 618 713 231", "240 698 179 83 532", "677 668 848 22 693"}

    Returns: 976.9208506736704

  17. 1.8705345580951183

    10

    { "518"}

    Returns: 310438.37920939457

  18. 1.0161448717918589

    2

    { "662 224 214 126 383 829 236 246 522", "436 212 673 616 997 731 600 718 780", "526 483 834 738 680 479 777 238 874", "314 730 481 767 141 91 876 366 588", "153 124 218 198 226 388 894 448 221", "499 525 944 520 618 699 781 392 881", "625 16 823 700 378 885 521 254 49", "562 619 218 27 134 721 815 154 337", "106 442 764 340 628 668 188 93 820"}

    Returns: 2.6653179510198015

  19. 1.125641876128402

    7

    { "666 340 534 468 620 826 946 466 101 999", "446 735 357 271 235 877 369 463 544 81", "418 186 348 978 99 664 974 164 61 10", "871 594 182 660 983 853 906 275 733 835", "51 302 279 308 617 185 941 355 213 974", "622 285 228 188 156 976 244 534 751 894", "708 959 65 415 905 157 326 425 95 863", "140 576 222 734 203 632 361 56 788 284", "274 636 117 180 391 429 414 657 325 562", "916 621 431 493 377 510 702 112 315 425"}

    Returns: 0.1390208354077913

  20. 1.6440742484837152

    8

    { "603 211 478 962 320 775 466 670 965 678", "833 229 42 376 517 406 531 161 946 350", "800 742 43 304 559 388 299 191 806 138", "40 383 563 962 408 171 490 295 483 917", "924 319 284 48 492 656 679 766 876 2", "326 890 770 280 680 271 8 47 518 768", "685 779 189 169 421 856 656 229 982 625", "110 55 219 427 649 221 878 841 430 5", "781 918 287 749 382 163 516 633 843 776", "25 340 842 902 69 616 263 478 785 408"}

    Returns: 1122.0868855740619

  21. 1.1909877678421346

    3

    { "285 235 965 793 588 646", "97 959 876 796 596 409", "914 993 462 657 667 748", "940 959 946 141 665 782", "465 911 570 680 650 25", "530 780 801 787 337 52"}

    Returns: 10.440295203515007

  22. 1.6765947195564763

    2

    { "287 242", "685 835"}

    Returns: 90.73592213266738

  23. 1.1449487438739705

    1

    { "121 993 959", "93 593 815", "530 12 510"}

    Returns: 7.0

  24. 1.1117413837990406

    4

    { "974 1", "170 129"}

    Returns: 186.60053292070552

  25. 1.4812801274381782

    10

    { "829"}

    Returns: 84882.44420164707

  26. 1.8085844971067893

    4

    { "518 457", "2 805"}

    Returns: 967.2857413849756

  27. 1.40607026402223

    8

    { "574 420 236 740", "301 514 604 459", "512 428 239 1000", "766 623 564 440"}

    Returns: 7400.36161427868

  28. 1.8614868953538508

    9

    { "49 701", "567 806"}

    Returns: 14207.785735286532

  29. 1.8691448042762921

    3

    { "115"}

    Returns: 268.2725830826247

  30. 1.3282838746818721

    9

    { "495 208 756 144 264 975 597 242 687", "97 287 582 589 128 988 245 188 81", "8 853 56 423 664 740 65 879 774", "158 626 453 512 775 417 530 480 519", "922 104 357 420 792 23 315 634 67", "18 100 825 725 173 5 248 796 875", "33 83 616 187 332 972 484 353 410", "747 181 884 811 808 467 361 599 538", "407 581 597 603 687 387 126 122 324"}

    Returns: 1.6905279740440164

  31. 1.6205110384606627

    9

    { "355 995 253 790", "586 433 851 309", "62 814 136 774", "990 543 790 60"}

    Returns: 6355.251208032537

  32. 1.0877159936806178

    1

    { "181 840 4 378 910 543", "577 69 416 104 453 855", "846 972 822 136 659 760", "52 408 413 262 830 716", "625 470 523 11 306 450", "241 196 807 958 171 744"}

    Returns: 28.0

  33. 1.826595936367748

    4

    { "676 292 499 981 241", "473 241 776 849 587", "494 274 991 847 577", "904 401 395 385 509", "548 710 160 439 524"}

    Returns: 1841.5196521264534

  34. 1.8267698525615743

    2

    { "359 911 66 494 663", "249 141 96 971 71", "97 653 764 380 824", "565 103 360 891 139", "538 137 709 316 951"}

    Returns: 0.5756928345822416

  35. 1.543052856537917

    2

    { "815 805 543", "433 235 517", "857 2 189"}

    Returns: 32.75832683010299

  36. 1.2188529924245088

    7

    { "615 280 822 720 733 294 673 238", "236 592 150 741 554 919 808 327", "561 262 848 409 346 887 601 298", "562 959 691 169 129 164 464 842", "755 529 597 319 665 116 445 454", "218 157 861 987 594 44 590 565", "489 686 718 268 421 7 783 452", "413 745 627 49 860 79 225 875"}

    Returns: 7.839622672677706

  37. 1.0366880629467952

    5

    { "289"}

    Returns: 554.9903637874988

  38. 1.3169957815587363

    2

    { "949 431 117 443 986", "958 135 802 128 97", "187 429 222 616 516", "410 640 897 714 46", "569 43 82 725 926"}

    Returns: 0.8219416300838702

  39. 1.0251231190192032

    9

    { "877 385", "3 387"}

    Returns: 719.9134638228136

  40. 1.2634715180057343

    10

    { "287 281", "951 548"}

    Returns: 9154.296868999318

  41. 1.0954086900775115

    5

    { "143 518 633 981 386 889 901 908", "47 886 306 124 687 784 660 64", "756 88 505 295 44 120 40 293", "636 300 146 299 78 556 422 941", "844 950 147 774 431 493 364 842", "87 3 603 338 13 391 785 370", "308 608 447 297 695 4 200 741", "864 642 98 816 942 317 362 240"}

    Returns: 0.05865753434261478

  42. 1.4014970280072754

    7

    { "295 316 613 178 394 196 276", "370 350 407 176 318 159 431", "75 24 522 827 536 933 950", "884 867 811 488 328 552 399", "192 778 515 717 421 709 122", "190 369 41 381 412 205 592", "691 979 32 897 489 466 443"}

    Returns: 410.4293289474749

  43. 1.9457006859476405

    3

    { "603 688 720 140", "571 0 658 280", "989 397 632 454", "434 898 289 839"}

    Returns: 60.01032460319311

  44. 1.668766675400383

    7

    { "875 27 125", "841 280 716", "56 266 597"}

    Returns: 2103.9713483077867

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: