ENG  RUS Timus Online Judge Online Judge
Problems
Authors
Online contests
Site news
Webboard
Problem set
Submit solution
Judge status
Guide
Register
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules
back to board

## Discussion of Problem 1024. Permutations

Some Hints to solve it without TLE
Posted by Grandmaster 24 Dec 2014 04:31
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 (in this example a = 4 considering the array start from 1).
while(var != i) (i = 1 the first index of the array)
{
var = a[var]; ((var)4 = a, var = 3, than 3 = var, 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 = 4
var = a = 4(k = 1)
var = a[var](4 = a)(k = 2) var = 2 after 2 = a = 1(k = 3) (finish)
first k = 3 steps
x = 3
after
i++;
var = a ( var = 1 ) after 1 = a (var = 4) after (4 = a = 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).