- Edited
@MSD: This 98minutes could be just a lucky guess with the algorithm. I do not think our combination technique could really hold against the huge combinatorial explosion we're dealing with.
So here's a challenge now:
Balance teams from a pool of ranks growing from 0 to 999 inclusive.
I got the difference down to 2. PS: No, I have not asked google for an answer yet. Computation time [wrong]~10 seconds[/wrong][correct]instantaneous[/correct].
I can not pledge that it is optimal however.
-Note, again: This solution is definitely not optimal since if you split the array in half, and take every other element from each array, and then join them, they'll return a difference of zero (always for any sequential array). This means we need another method to evaluate heuristic algorithms. Am satisfied enough with this algo, though I wish I could find some academic material for such a problem.
So here's a challenge now:
Balance teams from a pool of ranks growing from 0 to 999 inclusive.
I got the difference down to 2. PS: No, I have not asked google for an answer yet. Computation time [wrong]~10 seconds[/wrong][correct]instantaneous[/correct].
I can not pledge that it is optimal however.
-Note, again: This solution is definitely not optimal since if you split the array in half, and take every other element from each array, and then join them, they'll return a difference of zero (always for any sequential array). This means we need another method to evaluate heuristic algorithms. Am satisfied enough with this algo, though I wish I could find some academic material for such a problem.
diff = 2
on the left
6 8 10 11 12 13 14 15 17 18 19 20 21 22 23 24 26 27 28 29 30 32 33 34 35 36 37 38 39 40 42 43 45 47 50 57 58 60 65 67 69 70 74 75 77 78 79 81 86 87 89 90 93 97 102 105 106 107 108 110 111 112 116 119 123 125 126 127 130 133 135 136 137 139 140 141 142 143 145 147 148 149 152 154 158 161 162 164 165 167 169 170 171 173 175 176 177 180 182 183 184 188 189 192 194 195 196 200 201 203 204 205 206 207 209 210 211 214 216 217 218 219 221 226 228 229 231 234 239 242 243 247 248 251 252 253 254 255 262 263 265 266 267 268 270 271 273 277 279 280 282 284 290 293 295 298 300 303 304 312 314 315 316 317 318 320 322 325 326 335 336 339 341 343 345 346 348 349 351 352 353 354 357 358 359 360 363 366 367 368 374 376 377 379 380 381 383 384 385 390 391 396 397 403 405 406 408 411 413 415 417 420 422 425 426 427 429 433 434 438 440 442 445 447 448 449 451 459 460 461 465 467 468 469 472 473 475 479 484 485 487 491 492 493 495 497 500 501 503 506 512 514 515 518 519 523 529 535 536 537 538 539 540 544 549 551 552 553 554 555 556 557 559 562 565 568 570 571 576 577 578 579 582 586 592 593 594 595 601 602 603 605 609 610 614 617 618 622 623 624 626 629 630 632 633 634 635 638 642 643 644 646 647 649 651 656 657 659 661 663 664 666 668 671 675 677 678 679 682 683 685 686 687 692 693 694 699 700 704 705 706 707 708 710 712 713 714 715 716 717 718 719 721 722 723 724 725 726 728 729 730 731 732 734 735 736 737 739 742 744 745 746 748 750 753 754 756 759 760 761 762 763 767 769 771 772 774 775 776 777 778 781 782 784 788 790 792 793 794 795 796 797 800 807 810 813 814 816 817 818 820 821 823 824 825 831 833 834 835 836 837 838 839 840 842 844 845 847 849 854 855 856 858 859 861 862 863 865 866 870 871 872 874 880 881 888 892 893 896 897 900 902 905 906 907 908 909 910 912 913 915 920 921 925 927 931 934 935 938 941 944 945 946 949 951 953 954 956 959 961 966 971 972 974 976 977 978 979 980 981 984 986 988 989 992 993 994 997 998 999
-----------
on the right
0 1 2 3 4 5 7 9 16 25 31 41 44 46 48 49 51 52 53 54 55 56 59 61 62 63 64 66 68 71 72 73 76 80 82 83 84 85 88 91 92 94 95 96 98 99 100 101 103 104 109 113 114 115 117 118 120 121 122 124 128 129 131 132 134 138 144 146 150 151 153 155 156 157 159 160 163 166 168 172 174 178 179 181 185 186 187 190 191 193 197 198 199 202 208 212 213 215 220 222 223 224 225 227 230 232 233 235 236 237 238 240 241 244 245 246 249 250 256 257 258 259 260 261 264 269 272 274 275 276 278 281 283 285 286 287 288 289 291 292 294 296 297 299 301 302 305 306 307 308 309 310 311 313 319 321 323 324 327 328 329 330 331 332 333 334 337 338 340 342 344 347 350 355 356 361 362 364 365 369 370 371 372 373 375 378 382 386 387 388 389 392 393 394 395 398 399 400 401 402 404 407 409 410 412 414 416 418 419 421 423 424 428 430 431 432 435 436 437 439 441 443 444 446 450 452 453 454 455 456 457 458 462 463 464 466 470 471 474 476 477 478 480 481 482 483 486 488 489 490 494 496 498 499 502 504 505 507 508 509 510 511 513 516 517 520 521 522 524 525 526 527 528 530 531 532 533 534 541 542 543 545 546 547 548 550 558 560 561 563 564 566 567 569 572 573 574 575 580 581 583 584 585 587 588 589 590 591 596 597 598 599 600 604 606 607 608 611 612 613 615 616 619 620 621 625 627 628 631 636 637 639 640 641 645 648 650 652 653 654 655 658 660 662 665 667 669 670 672 673 674 676 680 681 684 688 689 690 691 695 696 697 698 701 702 703 709 711 720 727 733 738 740 741 743 747 749 751 752 755 757 758 764 765 766 768 770 773 779 780 783 785 786 787 789 791 798 799 801 802 803 804 805 806 808 809 811 812 815 819 822 826 827 828 829 830 832 841 843 846 848 850 851 852 853 857 860 864 867 868 869 873 875 876 877 878 879 882 883 884 885 886 887 889 890 891 894 895 898 899 901 903 904 911 914 916 917 918 919 922 923 924 926 928 929 930 932 933 936 937 939 940 942 943 947 948 950 952 955 957 958 960 962 963 964 965 967 968 969 970 973 975 982 983 985 987 990 991 995 996