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

Edited by author 20.06.2024 13:49

What happens when the order is greater than 1e9? Wouldn't a permutation with cycle lengths equal to first N primes easily exceed order 1e9? For example lcm ( 3, 5, 7.. 29 )

This works correct even with 1000 numbers. (What else compilator wants? ))

#include <stdio.h>
int nod(int a, int b){
    while (a != 0 && b != 0){
        if (a > b)
            a = a % b;
        else
            b = b % a;
    }
    return a+b;
}
int main(){
    int size;
    int result = 1;
    scanf_s("%i", &size);
    int arr[1001];
    bool mask[1001];
    for (int i = 0; i < size; ++i)
        scanf_s("%i", &arr[i]);
    for (int i = 0; i < size; ++i){
        int k = 1, temp = arr[i];
        while (temp != i + 1){
            temp = arr[temp - 1];
            ++k;
        }
        if (mask[k] != false){
            mask[k] = false;
        result =result/nod(result,k) * k;

        }
    }
    printf("%i", result);
}

If you don't feel like reviewing my code at least give me some tests please.
So... um... I think my code should work... I tested it along with an accepted program... and it worked fine... Here's the code:

#define DM 1001
#include <bitset>
#include <iostream>
#include <set>
using namespace std;

bitset <DM> bs;
bool verif;
int n, c, lg[DM], mp[DM];
long long v;
set <int> s;

void recursiv (int a)
{
    bs[a] = 1;
    ++v;
    if (s.find(mp[a]) != s.end())
        return;
    s.insert(a);
    recursiv(mp[a]);
}

int main ()
{
    cin >> n;
    for (int i = 1; i <= n; ++i)
    {
        cin >> mp[i];
        if (mp[i] == i)
            bs[i] = 1;
    }
    for (int i = 1; i <= n; ++i)
        if (!bs[i])
        {
            recursiv(i);
            s.clear();
            lg[++c] = v;
            v = 0;
        }
    for (v = lg[1]; !verif; ++v)
    {
        verif = 1;
        for (int i = 1; i <= c; ++i)
            if (v%lg[i] != 0)
                verif = 0, i = c + 1;
    }
    cout << v - 1;
    return 0;
}

Hi
I try to solve this task by computing cycle for i in [1..n] (k : P^k(i) = i) and multiplying all k[i] (not forgetting about if k[j] > k[i] and k[j] % k[i] == 0 then k[i] = 1)
And i got the WA #7. Where is my mistake?
Sorry for my poor english.

It does not use long long. It does not use any mathematical algorithm like GCD.
See if you can find it.

New test was added, 1158 AC solutions failed.

Here are some hints
1)Try to find the number of steps for every number to the final position and put it into a array
2)then try to find the least common multiple off all elements from the resulted array
let's consider an exemple 1 2 3 4 (the input is 4      )
                          4 2 1 3               4 2 1 3
int var = a[1] (in this example a[1] = 4 considering the array start from 1).
while(var != i) (i = 1 the first index of the array)
{
     var = a[var]; ((var)4 = a[4], var = 3, than 3 = var[3], var = 1(found the last position)
     k++; (is the number of steps that take to bring to last position)
}
lets make the array of k
x[i] = k;  than k = 0;
i++;
this array will look like i <- 1,n (3 1 3 3)
than just find the least common multiple for all elements that is 3
input                output
4                    3
4 2 1 3
and now the sample
5
4 1 5 2 3
the count arraw will look like
x[] = (3 3 2 3 2)
and the least common multiple is 6
explenation
a[1] = 4
var = a[1] = 4(k = 1)
var = a[var](4 = a[4])(k = 2) var = 2 after 2 = a[2] = 1(k = 3) (finish)
first k = 3 steps
x[1] = 3
after
i++;
var = a[2] ( var = 1 ) after 1 = a[1] (var = 4) after (4 = a[4] = 2 = i) finish
k = 3
and so on until the last element
I hope this will help (i'm not very good at expanation but i try).

I always WA at TEST9,who can give me a test like test9 ? other test in discuss were all used.It's right.

In this test n == 1.

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

The answer is 805627284

My algo works with 255 Kb memory and 1ms. what can I improve in code to get ~120 KB, as in best results?

[code deleted]

Edited by moderator 04.12.2019 20:44

var
  a: array[1..1000, 1..10001] of integer; c, d, e: integer;

label 1;
begin
  randomize;
  d := 1;
  Readln(c);
  for e := 1 to c do read(a[e, 10001]) {a[e,1002]:=random(c-1)+1};
  for e := 1 to c do a[e, 1] := e;
  1: inc(d);
  //for e:= 1 to c do write (a[e,1001],' ');
  for e := 1 to c do a[a[e, 10001], d] := a[e, d - 1];
  for e := 1 to c do if a[e, d] <> a[e, 1] then goto 1;
  writeln(d - 1);
end.

kkk, i figured out about the LCMs pretty much myself, but i just keep getting WAs on tests like 4 or 3 and that's sooo embarassing
<code>
#include <stdio.h>
#include <cmath>
#include <set>

using namespace std;

long long gcd(long long a, long long b) {
    return !b ? a : gcd(b, a % b);
}

long long lcm(long long a, long long b) {
    return (a / gcd(a,b) * b);
}

int main()
{

    int n;

    scanf("%d", &n);

    set<int> ds; // a usual stl set which stores the distaces of all elements
    int tmp;
    for(int i=1;i<n+1;i++) {
        scanf("%d", &tmp);
        ds.insert(abs(i-tmp));
    }

    long long res;
    if(ds.size() == 1 && ds.count(0)) res = 1;
    else {
        if(ds.count(0)) ds.erase(ds.find(0));
        res = 1;
        for (set<int>::iterator it = ds.begin(); it != ds.end(); ++it) {
            res = lcm(res,*it);
        }
    }

    printf("%lld", res);

}
</code>
And the worst thing is I just can't think of a straightforward test for which that gives a wrong answer.
5  4 1 5 2 3 => 6
1  1 => 1
5  1 2 3 4 5 => 1
6  6 5 3 4 2 1 => 15
didn't check for ns like 100 and i don't think that's the problem. also i don't think the problem is about malformed longlong operation, cause if i replace that with ints the WAs are all the same.
would really like if someone helped me 'bout that ((


Edited by author 28.11.2011 19:38

In testing my code .. it gets stuck in toggling between 41325 and 24315...and ends in infinite loop.

Can anyone help me with what I might be doing wrong ?

Thank you!
In this forum I knew how solve this task!

We must find lengths of pathes for every element of permutation and count their LCM.

Don't forget about Int64 in Pascal and long long in C++.

Here is my AC solution:

[code deleted]

Edited by author 15.08.2005 07:46

Edited by moderator 04.12.2019 20:48

the solution is achieved using LCM (MCM in Spanish) and long long to express the result

This is my program

[code deleted]

Edited by moderator 04.12.2019 20:51

#include <cstdio>
using namespace std;
 int main()
{
     int const Q=1001;
     long long unsigned k = 0,i,n,a=0;
    scanf("%llu",&n);
    long long unsigned mas1[Q];
    long long unsigned mas2[Q];
    for(i = 1;i<=n;i++)
    { scanf("%llu",&mas1[i]);
     mas2[i] = mas1[i];
    }
    for(;;)
   {
       for(i = 1;i<=n;i++)
     {
         if (i == mas2[i]){ k++;}
         mas2[i] = mas1[mas2[i]];
     }
      a++;
     if ( k == n) { break;} else {k = 0;}
   }
    printf("%llu\n",a);
   return 0;
}

#include <cstdio>


using namespace std;

/*
 *
 */
 int main()
{


    long long k = 0;
     long long i;
     long long unsigned n;
    scanf("%llu",&n);
    long long unsigned mas1[1000];
    long long unsigned mas2[1000];
    for(i = 1;i<=n;i+=1)
    { scanf("%llu",&mas1[i]);
     mas2[i] = mas1[i];
    }
    long long unsigned a = 0;
    long long s = 0;
    long long m = 0;
   do
   {
       for(long long j = 1;j<=n;j+=1)
     {
         if (j == mas2[j]){ k+=1;}
     }
    for(i = 1;i<=n;i+=1)
    {
        s = mas2[i];
        mas2[i] = mas1[mas2[i]];
    }
     if ( k == n) { m=1;} else {k = 0;}
    a+=1;
   } while (m!=1);
    printf("%llu\n",a);
   return 0;
}