CT37678

The weights Disorder Count Puzzle

MediumL5 · Recursion RenegadeAcceptance: 0.0%XP: 60

Rekha inherited the apiary at the opal reefs of Shimmerdeep along with its curious bookkeeping system for weights. Time to make sense of it. Task: Print the number of inversions: index pairs (i,j) with i<j but a[i] > a[j]. Input format: First line: n. Second line: n integers. Output format: Print the inversion count (fits 64-bit). Constraints: 1 <= n <= 2492; -1000000 <= a[i],x <= 1000000000.

Example 1:

Input: 1433 1163 735 275 996 1046 169 923 632 405 230 899 478 981 1013 351 685 668 1022 198 729 1137 157 425 92 1313 241 486 167 1116 555 920 1040 48 73 1155 557 860 391 722 813 877 291 367 1142 56 516 397 1363 1402 1364 184 637 921 1425 1171 886 1059 928 380 806 398 124 705 237 356 1200 1179 1102 1062 1124 1136 1108 1035 1401 622 707 819 1164 88 778 1359 154 200 994 282 295 1326 242 650 630 333 644 286 1112 521 57 1057 787 905 1312 1091 431 453 854 437 171 359 916 578 1391 989 965 517 932 873 352 914 1379 510 1279 945 1203 1033 1139 1015 38 127 880 443 1042 1009 1288 15 207 426 699 204 690 1191 748 610 330 361 406 764 728 564 1184 797 562 1123 1012 556 162 1080 1407 307 479 1387 1119 1383 1266 1201 826 1358 143 682 1269 628 1367 1390 20 820 930 540 673 582 457 448 653 1415 611 446 1267 863 572 1…
Output: 513720

Example 2:

Input: 950 210715833 811324792 358951949 322080831 501965641 464998678 653685491 852382004 230534828 464135844 922904170 602182824 645239110 669032491 424017684 339176339 89868897 724901111 259729192 259003987 147030149 199534921 545548706 62890693 769538893 362119144 628907876 699308951 80751143 41789633 426061760 924810764 221614930 118628179 696816642 257467259 446522491 258408754 825800870 916935773 795563409 304053515 987473536 771382916 210014191 153721695 478177934 979413088 186033110 224581173 933188376 281405614 366958773 133974792 666168330 418680587 493700277 76449446 961272137 337688577 240330882 107545511 898567594 900959177 299447244 952926757 888135843 831294432 526069790 595450850 284812876 518079199 672982418 984437372 308913481 102698022 495157971 643510586 152436778 664743797 2…
Output: 224931

Example 3:

Input: 1571 595372705 437521602 586442825 121888670 4710682 822182469 195842832 988429477 102379741 177461776 882904794 424593565 962346870 881822690 390156095 57803740 871131422 882322790 438123870 185217413 40339283 526309620 260094188 535992186 304411812 623702505 437817536 493194549 191799392 838178079 155132452 392016749 336707207 570917614 178445043 531519552 945397732 76423241 324763326 661896495 38067961 651251046 87773658 724620997 61874483 319381078 120072590 655266099 958105744 827944874 418084339 138761927 354346254 611822448 44430236 947444330 348456483 825332622 46474586 150181149 10367839 988856828 31961204 937126283 803990750 484020180 222107608 260687156 159911684 775782718 771288560 430889307 134415290 884319169 705242147 821372882 174943276 316042919 313833880 9977716 669905158…
Output: 615746

Constraints:

1 <= n <= 2492; -1000000 <= a[i],x <= 1000000000.

Loading...
Test Cases:No test cases
No test cases available.
The weights Disorder Count Puzzle - MEDIUM Coding Problem | CodeTikki