JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: Marathon Match 9
Problem: SortedCube

Problem Statement

    

Consider a list of K unique integers given by {x1, x2, ..., xK }. This list is considered sorted in ascending order if x1 < x2 < ... < xK.

We define a plane as an N x N two-dimensional array of integers. A plane is sorted if each of the N rows (numbered from 0 to N-1) of the plane are a sorted list (as defined above) and each of the N columns (numbered from 0 to N-1) of the plane are a sorted list (as defined above).

Finally, we define a cube as an N x N x N three-dimensional array of integers. In fact, such a cube consists of N planes (numbered from 0 to N-1). We can associate a Cartesian coordinate system with the cube as shown in the figure below. The arrows indicate the direction in which coordinates increase. Then, the 0th plane represents the top face of the cube (z = 0), and the N-1th plane represents the bottom face of the cube (z = N-1). A cube is sorted if each of the 3*N planes (i.e. all the planes with constant x, y, and z) in the cube are sorted (as defined above). An alternative definition is to say that if one point has all three coordinates less than or equal to another point, then the first point must have value less than or equal to the second point. In this problem, each integer from 1 to N3 inclusive will appear exactly once in the cube.

Create a class SortedCube with a single method sortCube. The method will take an int[] initCube as argument which gives the initial configuration of the cube, in plane-major order (that is, the first N*N numbers represent plane 0 of the cube, the following N*N numbers represent plane 1, etc.). Each plane is represented in row-major order (that is, the first N numbers represent row 0 of plane 0, the following N numbers represent row 1 of plane 0, etc.). In other words, the element with index N*N*Z + N*Y + X in the input is the value at coordinate (X,Y,Z). In addition, you are given an int N. Your sortCube method should return a String[] array. Each element of the return array must be formatted as "X1,Y1,Z1-X2,Y2,Z2" (quotes for clarity only) where each of 'X1', 'Y1', 'Z1', 'X2', 'Y2', and 'Z2' represent an integer in the range 0 to N-1, inclusive. Each element describes two positions within the cube; specifically, (Xi, Yi, Zi) represents a position in the Zith plane, at (row, column) = (Yi, Xi). Thus, the array returned by your sortCube method describes the swaps that should be performed in the order they should be performed, so as to obtain a sorted cube.



Scoring

You will receive a score of 0 for a particular testcase if any of the following conditions are true for any element of the return array:

  • (X1 < 0) or (X1 > N-1)
  • (Y1 < 0) or (Y1 > N-1)
  • (Z1 < 0) or (Z1 > N-1)
  • (X2 < 0) or (X2 > N-1)
  • (Y2 < 0) or (Y2 > N-1)
  • (Z2 < 0) or (Z2 > N-1)

You will also receive a score of 0 if:

  • The swaps described in your return array don't result in a sorted cube
  • Any element of the return array is formatted incorrectly
  • The returned array contains more than N3 elements

Otherwise, your score for a particular testcase will be N3/(numSwaps + 1), where numSwaps is the total number of elements in your returned array. The execution time limit is 30 seconds. Your total score will be the sum of your scores for each testcase.



Test Case Generation

Test cases are generated as follows:

  • N is chosen uniformly at random in the range [10, 50], inclusive.
  • Execute the following pseudocode:
    	for i = 0 to N3-1
    		initCube[i] = i + 1
    		randomIndex = random number from range [0, i], inclusive
    		swap elements at index 'i' and 'randomIndex' in initCube
    	end-for
    	

 

Definition

    
Class:SortedCube
Method:sortCube
Parameters:int[], int
Returns:String[]
Method signature:String[] sortCube(int[] initCube, int N)
(be sure your method is public)
    
 

Notes

-The first example case has a smaller value of N for testing purposes.
 

Constraints

-N will be between 10 and 50, inclusive.
-The execution time limit is 30 seconds.
-The memory limit is 64 MB.
-The return array can contain a maximum of N3 elements.
 

Examples

0)
    
N = 5
Plane 0:
72 35 125 92 4
3 51 89 44 40
108 54 106 34 45
2 75 110 42 84
48 62 122 24 20
Plane 1:
49 102 94 100 77
39 86 81 123 66
120 78 57 112 64
105 31 80 46 90
55 38 27 101 91
Plane 2:
10 83 14 98 69
73 5 50 59 95
115 21 61 124 41
30 117 88 93 109
79 7 47 67 65
Plane 3:
33 70 25 16 104
32 99 121 68 103
26 113 56 97 9
22 76 71 52 111
107 82 119 53 74
Plane 4:
63 23 43 28 8
12 15 96 118 116
58 18 36 13 29
6 1 37 11 60
87 19 114 17 85
Download this example (219B)



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

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)2010, TopCoder, Inc. All rights reserved.