ArraySorting
SRM 779 · 2020-02-20 · by lazy_fox
SRM 779 · 2020-02-20 · by lazy_fox · Dynamic Programming, Recursion, Sorting
Problem Statement
Problem Statement
You are given the
You can perform several operations on this array. In each operation you can take any element of A and replace it by any new value from the range [1,2000].
Using as few such operations as possible, convert A into an array that is sorted in non-decreasing order. Return the sorted array you produced. If there are multiple correct answers, return the lexicographically smallest one among them.
Notes
- Given two distinct arrays with the same number of elements, the lexicographically smaller one is the one that has a smaller value at the first index at which they differ.
Constraints
- A will contain between 1 and 2000 elements,
- Each element of A will be between 1 and 2000, inclusive.
Examples
0)
{ 10, 8 }
Returns: {1, 8 }
The sequence is not sorted, so we need to make at least one change. There are multiple ways how to make it sorted in exactly one change. For example, we could produce {3, 8}, {10, 10}, or {10, 470}. The lexicographically smallest sorted sequence that can be produced in one step is obtained by changing the 10 to a 1.
1)
{ 6, 9 }
Returns: {6, 9 }
This sequence is already sorted, so no changes are needed.
2)
{ 9, 8, 10, 4 }
Returns: {1, 8, 10, 10 }
The minimum number of changes is two. The optimal way to perform the two changes is to replace the 9 by a 1 and to replace the 4 by a 10.
3)
{ 3, 7, 7, 7, 6 }
Returns: {3, 7, 7, 7, 7 }
In this case, the input sequence can be turned into a non-decreasing sequence in a single operation: by changing the last element to a 7 (or something bigger).
4)
{ 502 , 889 , 916 , 922 , 406 , 362 , 720 , 679 , 556 , 227 , 251 , 483 , 491 , 493 , 969 , 530 , 459 , 710 , 969 , 127 , 911 , 578 , 469 , 376 , 244 , 414 , 384 , 87 , 150 , 975 , 366 , 651 , 215 , 281 , 924 , 620 , 642 , 643 , 651 , 550 , 222 , 901 , 32 , 712 , 745 , 353 , 594 , 204 , 62 , 562 , 682 , 324 , 491 , 150 , 700 , 734 , 915 , 435 , 172 , 64 , 761 , 538 , 66 , 976 , 170 , 989 , 595 , 164 , 983 , 245 , 713 , 204 , 498 , 96 , 268 , 242 , 800 , 861 , 445 , 862 , 774 , 478 , 537 , 265 , 979 , 236 , 998 , 893 , 23 , 170 , 308 , 783 , 59 , 373 , 758 , 228 , 713 , 353 , 391 , 48 , 949 , 455 , 603 , 798 , 903 , 222 , 40 , 702 , 82 , 836 , 915 , 856 , 666 , 804 , 472 , 644 , 391 , 469 , 537 , 413 , 638 , 196 , 196 , 696 , 569 , 953 , 276 , 633 , 657 , 18 , 680 , 958 , 825 , 283 , 755 , 727 , 856 , 146 , 780 , 938 , 334 , 47 , 145 , 999 , 202 , 616 , 642 , 592 , 436 , 530 , 5 , 426 , 726 , 200 , 473 , 646 , 504 , 748 , 278 , 161 , 118 , 310 , 470 , 942 , 944 , 224 , 20 , 799 , 722 , 151 , 88 , 55 , 197 , 584 , 405 , 398 , 551 , 398 , 990 , 987 , 928 , 346 , 412 , 5 , 897 , 236 , 650 , 400 , 336 , 279 , 912 , 453 , 940 , 381 , 394 , 883 , 957 , 413 , 34 , 678 , 563 , 121 , 84 , 112 , 705 , 488 , 861 , 255 , 885 , 202 , 593 , 164 , 547 , 356 , 520 , 443 , 592 , 169 , 195 , 927 , 800 , 106 , 379 , 739 , 487 , 124 , 974 , 795 , 536 , 7 , 824 , 450 , 127 , 907 , 561 , 183 , 746 , 774 , 790 , 982 , 975 , 382 , 498 , 874 , 738 , 17 , 316 , 329 , 538 , 510 , 607 , 689 , 968 , 985 , 779 , 806 , 108 , 752 , 600 , 995 , 110 , 423 , 444 , 237 , 681 , 357 , 771 , 778 , 482 , 560 , 111 , 456 , 942 , 608 , 329 , 31 , 977 , 997 , 711 , 514 , 858 , 317 , 202 , 825 , 301 , 980 , 630 , 760 , 84 , 581 , 754 , 193 , 3 , 549 , 781 , 35 , 257 , 552 , 812 , 738 , 463 , 275 , 546 , 756 , 234 , 226 , 786 , 210 , 574 , 496 , 723 , 432 , 164 , 276 , 608 , 816 , 608 , 590 , 575 , 43 , 170 , 680 , 235 , 173 , 581 , 368 , 559 , 189 , 271 , 371 , 279 , 733 , 997 , 176 , 841 , 230 , 401 , 978 , 440 , 975 , 826 , 514 , 758 , 989 , 142 , 717 , 805 , 101 , 306 , 731 , 143 , 476 , 411 , 729 , 648 , 343 , 96 , 206 , 531 , 366 , 928 , 161 , 451 , 276 , 336 , 291 , 506 , 737 , 268 , 945 , 63 , 93 , 810 , 172 , 434 , 951 , 888 , 238 , 51 , 194 , 968 , 193 , 669 , 730 , 922 , 668 , 424 , 369 , 225 , 955 , 735 , 505 , 467 , 537 , 780 , 803 , 179 , 285 , 891 , 798 , 581 , 305 , 243 , 743 , 476 , 676 , 693 , 715 , 265 , 96 , 908 , 584 , 640 , 928 , 314 , 913 , 947 , 737 , 282 , 524 , 43 , 368 , 380 , 510 , 904 , 511 , 664 , 434 , 148 , 554 , 231 , 728 , 858 , 473 , 470 , 333 , 148 , 515 , 399 , 412 , 610 , 659 , 996 , 601 , 938 , 661 , 514 , 885 , 749 , 795 , 760 , 144 , 514 , 139 , 653 , 769 , 1 , 316 , 202 , 148 , 221 , 432 , 228 , 78 , 905 , 697 , 762 , 404 , 563 , 160 , 168 , 524 , 818 , 515 , 125 , 756 , 175 , 638 , 992 , 923 , 784 , 751 , 66 , 297 , 241 , 70 , 65 , 241 , 737 , 618 , 741 , 957 , 49 , 968 , 34 , 953 , 16 , 147 , 709 , 579 , 307 , 876 , 102 , 124 , 390 , 578 , 231 , 564 , 567 , 222 , 838 , 350 , 324 , 256 , 998 , 916 , 677 , 414 , 509 , 414 , 31 , 249 , 722 , 80 , 216 , 108 , 384 , 231 , 254 , 92 , 809 , 912 , 319 , 263 , 388 , 708 , 192 , 618 , 623 , 759 , 192 , 813 , 108 , 515 , 68 , 458 , 783 , 96 , 223 , 291 , 861 , 254 , 539 , 583 , 685 , 754 , 42 , 420 , 984 , 295 , 864 , 145 , 559 , 182 , 759 , 946 , 890 , 950 , 563 , 864 , 708 , 106 , 676 , 168 , 973 , 743 , 625 , 755 , 191 , 847 , 45 , 51 , 452 , 583 , 633 , 488 , 688 , 26 , 908 , 23 , 321 , 771 , 167 , 231 , 304 , 277 , 176 , 545 , 227 , 90 , 409 , 286 , 196 , 84 , 805 , 168 , 179 , 781 , 922 , 369 , 628 , 318 , 419 , 431 , 900 , 404 , 919 , 587 , 429 , 178 , 609 , 101 , 300 , 128 , 331 , 603 , 404 , 858 , 148 , 982 , 948 , 556 , 620 , 143 , 991 , 424 , 662 , 169 , 205 , 935 , 537 , 184 , 252 , 308 , 966 , 503 , 711 , 884 , 441 , 491 , 61 , 49 , 592 , 360 , 528 , 274 , 315 , 284 , 132 , 462 , 617 , 79 , 369 , 588 , 573 , 359 , 12 , 586 , 528 , 568 , 872 , 416 , 751 , 123 , 723 , 716 , 977 , 785 , 952 , 417 , 276 , 364 , 817 , 219 , 76 , 345 , 492 , 390 , 980 , 975 , 203 , 596 , 405 , 571 , 536 , 329 , 281 , 547 , 914 , 808 , 466 , 785 , 576 , 216 , 259 , 298 , 283 , 235 , 83 , 586 , 651 , 710 , 302 , 820 , 928 , 729 , 516 , 771 , 470 , 495 , 746 , 672 , 442 , 150 , 594 , 977 , 479 , 874 , 875 , 744 , 34 , 340 , 881 , 609 , 907 , 491 , 258 , 542 , 726 , 340 , 479 , 728 , 401 , 780 , 547 , 328 , 508 , 414 , 99 , 977 , 908 , 196 , 1000 , 702 , 345 , 945 , 678 , 175 , 171 , 905 , 271 , 204 , 244 , 503 , 164 , 503 , 993 , 421 , 44 , 718 , 113 , 874 , 798 , 513 , 654 , 696 , 841 , 513 , 110 , 291 , 842 , 369 , 486 , 193 , 70 , 182 , 138 , 100 , 709 , 308 , 4 , 331 , 863 , 599 , 833 , 26 , 453 , 825 , 798 , 848 , 543 , 910 , 722 , 692 , 423 , 727 , 387 , 615 , 239 , 848 , 257 , 432 , 217 , 94 , 625 , 638 , 275 , 114 , 89 , 335 , 773 , 444 , 665 , 635 , 43 , 497 , 12 , 847 , 322 , 809 , 695 , 216 , 719 , 416 , 907 , 493 , 142 , 645 , 459 , 732 , 845 , 67 , 164 , 413 , 160 , 140 , 50 , 434 , 605 , 491 , 121 , 377 , 934 , 785 , 363 , 328 , 282 , 374 , 175 , 955 , 534 , 869 , 170 , 252 , 284 , 428 , 96 , 777 , 72 , 906 , 860 , 268 , 972 , 375 , 680 , 131 , 866 , 82 , 917 , 470 , 572 , 37 , 198 , 505 , 173 , 560 , 833 , 454 , 285 , 7 , 760 , 819 , 875 , 929 , 422 , 510 , 356 , 518 , 638 , 780 , 775 , 497 , 47 , 747 , 872 , 79 , 877 , 737 , 160 , 793 , 559 , 731 , 181 , 756 , 587 , 354 , 668 , 419 , 159 , 952 , 777 , 919 , 122 , 3 , 847 , 544 , 512 , 555 }
Returns: {1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 32, 32, 32, 32, 32, 32, 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, 62, 64, 64, 64, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 66, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 82, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 84, 106, 106, 106, 106, 106, 106, 106, 106, 106, 106, 106, 106, 106, 106, 106, 106, 106, 106, 106, 106, 106, 106, 106, 106, 106, 106, 106, 106, 106, 106, 106, 106, 106, 106, 106, 108, 108, 108, 108, 110, 110, 110, 110, 110, 110, 110, 110, 110, 110, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 111, 142, 142, 142, 142, 142, 142, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 143, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 148, 160, 168, 168, 168, 168, 168, 168, 175, 175, 175, 175, 175, 175, 175, 175, 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, 241, 249, 249, 249, 249, 249, 249, 249, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 254, 277, 277, 277, 277, 277, 277, 286, 286, 286, 286, 286, 286, 286, 286, 286, 286, 286, 286, 286, 286, 286, 286, 286, 286, 286, 286, 286, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 300, 308, 308, 308, 308, 308, 308, 308, 308, 308, 308, 308, 308, 308, 315, 315, 315, 315, 315, 315, 315, 315, 315, 359, 359, 359, 359, 359, 359, 359, 359, 359, 359, 359, 359, 359, 359, 359, 359, 364, 364, 364, 364, 364, 364, 390, 390, 390, 390, 390, 405, 405, 405, 405, 405, 405, 405, 405, 466, 466, 466, 466, 466, 466, 466, 466, 466, 466, 466, 466, 466, 466, 466, 466, 466, 466, 470, 470, 470, 470, 470, 470, 470, 470, 479, 479, 479, 479, 479, 479, 479, 479, 479, 479, 479, 479, 479, 479, 479, 479, 479, 479, 479, 479, 479, 479, 479, 479, 479, 479, 479, 479, 479, 479, 479, 479, 479, 479, 479, 479, 479, 503, 503, 503, 503, 503, 503, 503, 503, 503, 503, 513, 513, 513, 513, 513, 513, 513, 513, 513, 513, 513, 513, 513, 513, 513, 513, 513, 513, 513, 513, 513, 513, 513, 513, 513, 513, 513, 543, 543, 543, 543, 543, 543, 543, 615, 615, 615, 615, 615, 615, 615, 625, 638, 638, 638, 638, 638, 638, 638, 665, 665, 665, 665, 665, 665, 665, 665, 695, 695, 719, 719, 719, 719, 719, 719, 719, 732, 732, 732, 732, 732, 732, 732, 732, 732, 732, 732, 732, 732, 732, 732, 732, 732, 732, 732, 732, 732, 732, 732, 732, 732, 732, 732, 732, 777, 777, 777, 860, 860, 860, 860, 860, 860, 866, 866, 866, 866, 866, 866, 866, 866, 866, 866, 866, 866, 866, 866, 866, 866, 866, 866, 866, 866, 866, 866, 866, 866, 866, 866, 866, 866, 872, 872, 877, 877, 877, 877, 877, 877, 877, 877, 877, 877, 877, 877, 877, 877, 877, 919, 919, 919, 919, 919, 919, 919 }
Submissions are judged against all 57 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class ArraySorting with a public method vector<int> arraySort(vector<int> A) · 57 test cases · 2 s / 256 MB per case