11071  Permutation Representation
Moderator: Board moderators
11071  Permutation Representation
Because my english is poor ,
"
(724)
The product of several cycles is evaluated from right to left. The above permutation can be written as
(53)(51)(54)
(1354)(1)
(1)(1354)
"
I don't know what is above saying , Can someone give me a example ?
thanks ,
Last edited by SRX on Tue Aug 15, 2006 4:06 pm, edited 1 time in total.
studying @ ntu csie
Re: 11071 need some explanations
Let's put it that way:SRX wrote:
Because my english is poor ,
"
(724)
The product of several cycles is evaluated from right to left. The above permutation can be written as
(53)(51)(54)
(1354)(1)
(1)(1354)
"
I don't know what is above saying , Can someone give me a example ?
thanks ,
> You are given 2 permutations of n elements
> Following some rules you have to transform the first permutation into second
Let's revise those rules by clarifying the example above.
You are given 2 permutations of n elements "12345" and "32514". And you can form the second permutation from the first one by this operation: (53)(51)(54). What this operation tells you to do? It tells you that:
> (54) element 5 goes in a place of 4, element 4 goes in a place of 5
> after (54) you have 12354.
> (51) element 5 goes in a place of 1, element 1 goes in a place of 5
> after (51) you have 52314
> (53) element 5 goes in a place of 3, element 3 goes in a place of 5
> after (53) you have 32514
Thus the first permutation is transformed into second.
In other words operation (x1 x2 x3 ... xn) tells you that you have to shift all elements by one position to the right (ignoring those elements that are not listed in the operation). And (x1 x2 x3 ... xn) ^ p tells you that you have to shift the elements included in operation by "p".
Consider this example:
Operation: (13459)^2
Initial permutation: 13xx45xxx9xx
After operation was performed: 59xx13xxx4xx
Note: All x are NOT to be moved, only those numbers that are included in the operation!
Re: 11071 need some explanations
tks .Leonid wrote:Let's put it that way:SRX wrote:
Because my english is poor ,
"
(724)
The product of several cycles is evaluated from right to left. The above permutation can be written as
(53)(51)(54)
(1354)(1)
(1)(1354)
"
I don't know what is above saying , Can someone give me a example ?
thanks ,
> You are given 2 permutations of n elements
> Following some rules you have to transform the first permutation into second
Let's revise those rules by clarifying the example above.
You are given 2 permutations of n elements "12345" and "32514". And you can form the second permutation from the first one by this operation: (53)(51)(54). What this operation tells you to do? It tells you that:
> (54) element 5 goes in a place of 4, element 4 goes in a place of 5
> after (54) you have 12354.
> (51) element 5 goes in a place of 1, element 1 goes in a place of 5
> after (51) you have 52314
> (53) element 5 goes in a place of 3, element 3 goes in a place of 5
> after (53) you have 32514
Thus the first permutation is transformed into second.
In other words operation (x1 x2 x3 ... xn) tells you that you have to shift all elements by one position to the right (ignoring those elements that are not listed in the operation). And (x1 x2 x3 ... xn) ^ p tells you that you have to shift the elements included in operation by "p".
Consider this example:
Operation: (13459)^2
Initial permutation: 13xx45xxx9xx
After operation was performed: 59xx13xxx4xx
Note: All x are NOT to be moved, only those numbers that are included in the operation!
I think "above permutation" is (724) , but it actually means
(
1 2 3 4 5
3 2 5 1 4
)
studying @ ntu csie
Re: 11071 need some explanations
a O ( n^2 ) solution is easy to find out , but n<=200000 .
Can someone give me a little hint about what is the
element in element i ' s final position after we do
(123....n)^an (123....n1)^an1 .... (123....i+1)^ai+1
thanks .
Can someone give me a little hint about what is the
element in element i ' s final position after we do
(123....n)^an (123....n1)^an1 .... (123....i+1)^ai+1
thanks .
studying @ ntu csie
 little joey
 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
A little hint:
If you keep a pointer at the currently last element (elements n, n1, ... i+1 are are already placed at their correct position and we don't care about them anymore). Then, we are interested in the number of elements which are in between element i and the currently last element (this can be determined in O(log n)). The next currently last element will be the one one position before element i.
If you keep a pointer at the currently last element (elements n, n1, ... i+1 are are already placed at their correct position and we don't care about them anymore). Then, we are interested in the number of elements which are in between element i and the currently last element (this can be determined in O(log n)). The next currently last element will be the one one position before element i.
Thank you very much , Adrian Kuegel !!!!!!!!!!!!Adrian Kuegel wrote:A little hint:
If you keep a pointer at the currently last element (elements n, n1, ... i+1 are are already placed at their correct position and we don't care about them anymore). Then, we are interested in the number of elements which are in between element i and the currently last element (this can be determined in O(log n)). The next currently last element will be the one one position before element i.
your hint is great and gives me a good thinking to solve this problem within the time limit , anyway , thanks you again
studying @ ntu csie
 little joey
 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm

 Guru
 Posts: 724
 Joined: Wed Dec 19, 2001 2:00 am
 Location: Germany
 little joey
 Guru
 Posts: 1080
 Joined: Thu Dec 19, 2002 7:37 pm

 Learning poster
 Posts: 91
 Joined: Tue May 31, 2005 2:01 pm
 Location: Russia
Have I understood right that "a pointer at the currently last element" is a position of element i in a permutation after we have done (12...i+1)^A{i+1}...(12...n)^An and "the number of elements which are in between element i and the currently last element" is a number of positions that is located between "a pointer at the currently last element" and position of element i in result permutation which contains some element from {i + 1,...,n}?Adrian Kuegel wrote:A little hint:
If you keep a pointer at the currently last element (elements n, n1, ... i+1 are are already placed at their correct position and we don't care about them anymore). Then, we are interested in the number of elements which are in between element i and the currently last element (this can be determined in O(log n)). The next currently last element will be the one one position before element i.
well... got AC using BST, but i cant understand idea of heap.
anyway,
here r 3 cases for fellows:
Output
anyway,
here r 3 cases for fellows:
Code: Select all
10
1 2 3 4 5 6 7 8 9 10
5 4 1 9 8 10 3 2 6 7
4
1 2 3 4
3 4 1 2
5
1 2 3 4 5
5 4 2 3 1
Code: Select all
0 1 1 3 4 0 3 7 1 4
0 0 0 2
0 0 1 3 4
Self judging is the best judging!

 Learning poster
 Posts: 91
 Joined: Tue May 31, 2005 2:01 pm
 Location: Russia
Input:shanto86 wrote:some I/O please,
Output:3
1 2 3
3 2 1
3
1 2 3
2 1 3
4
1 2 3 4
4 2 1 3
3
1 2 3
3 1 2
4
1 2 3 4
2 4 1 3
4
1 2 3 4
4 1 2 3
3
1 2 3
2 3 1
7
1 2 3 4 5 6 7
6 5 1 7 2 4 3
7
1 2 3 4 5 6 7
2 4 5 6 7 3 1
6
1 2 3 4 5 6
3 5 1 4 6 2
9
1 2 3 4 5 6 7 8 9
2 4 9 8 7 1 3 6 5
10
1 2 3 4 5 6 7 8 9 10
1 6 7 3 9 8 4 2 5 10
10
1 2 3 4 5 6 7 8 9 10
4 5 10 6 8 3 2 7 9 1
10
1 2 3 4 5 6 7 8 9 10
9 2 1 7 8 6 3 4 5 10
6
1 2 3 4 5 6
6 4 1 2 3 5
0 1 2
0 1 0
0 1 0 3
0 0 2
0 1 1 2
0 0 0 3
0 0 1
0 0 2 1 4 2 3
0 0 2 0 0 0 2
0 0 1 2 2 1
0 1 1 2 4 3 6 7 6
0 1 0 1 1 0 1 7 4 0
0 1 2 0 0 2 4 3 3 7
0 1 0 0 2 5 0 4 8 0
0 0 0 3 0 5
I think what he meant is you do something like this:
where left, right are the index of the left, right children respectively.
Code: Select all
struct node {
int left, right, val;
};
node A[500000];