Discussion @ 1024. Permutations @ Timus Online Judge

T_be_GP What will answer 2 3 1 4 5? I think it is infinity. [11] // Problem 1024. Permutations 19 Aug 2010 14:32

1 - 2 3 1 4 5
2 - 3 1 2 4 5
3 - 2 3 1 4 5

1 and 3 are same

tiancaihb Re: What will answer 2 3 1 4 5? I think it is infinity. [1] // Problem 1024. Permutations 19 Aug 2010 14:56

No, 3-1 2 3 4 5. The digit always mean index for the first line.

T_be_GP Re: What will answer 2 3 1 4 5? I think it is infinity. // Problem 1024. Permutations 19 Aug 2010 15:54

but i can't find answer 3 with LCM?

tiancaihb Re: What will answer 2 3 1 4 5? I think it is infinity. [8] // Problem 1024. Permutations 19 Aug 2010 16:08

2&3&1 is a loop with length 3
4 is a loop with length 1
5 is a loop with length 1
LCM(3,1,1)=3

T_be_GP I can't undertand it : 2&3&1 is a loop with length 3 [7] // Problem 1024. Permutations 19 Aug 2010 16:11

2&3&1 is a loop with length 3

Edited by author 19.08.2010 16:11

T_be_GP Re: I can't undertand it : 2&3&1 is a loop with length 3 // Problem 1024. Permutations 19 Aug 2010 16:17

ok.I understood.

Edited by author 19.08.2010 16:21

tiancaihb Re: I can't undertand it : 2&3&1 is a loop with length 3 [5] // Problem 1024. Permutations 19 Aug 2010 16:25

Say it in this way:
select an arbitraty number n, let i=n;
while( P(i)!=n ) i=P(i);
all the numbers "involved" makes a loop.

in case 2 3 1
select n=2,i=2;
P(i)=3 so i=3;
P(i)=1 so i=2;
now i=n, exit loop;

You can prove the following statement:
if a loop has X elements, then after exactly X permutations, every elements in the loop is on its proper position in EN.

is that clear? Since you are very good in maths, you may prove it yourself.

T_be_GP Re: I can't undertand it : 2&3&1 is a loop with length 3 [4] // Problem 1024. Permutations 19 Aug 2010 16:28

yes my math is good. But i begun to learn programming since 18.
Due to it I am not very good at finding algorythm.
Do you know really good book with examples for learning algorythms.

tiancaihb Re: I can't undertand it : 2&3&1 is a loop with length 3 [2] // Problem 1024. Permutations 19 Aug 2010 16:34

Sorry I only know books written in Chinese.

T_be_GP Re: I can't undertand it : 2&3&1 is a loop with length 3 [1] // Problem 1024. Permutations 19 Aug 2010 16:38

May be it is translation from English or Russian

tiancaihb Re: I can't undertand it : 2&3&1 is a loop with length 3 // Problem 1024. Permutations 19 Aug 2010 16:44

All I know are written by Chinese authors.

Andrew Hoffmann aka SKYDOS [Vladimir SU] Re: I can't undertand it : 2&3&1 is a loop with length 3 // Problem 1024. Permutations 19 Aug 2010 16:47

cormen introduction to algorithms (pdf)
Knuth and other)

T_be_GP wrote 19 August 2010 16:28

yes my math is good. But i begun to learn programming since 18.
Due to it I am not very good at finding algorythm.
Do you know really good book with examples for learning algorythms.

Discussion of Problem 1024. Permutations