11071 - Permutation Representation

All about problems in Volume 110. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

11071 - Permutation Representation

Post by SRX » Mon Aug 14, 2006 7:23 pm

:oops:

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 , :D
Last edited by SRX on Tue Aug 15, 2006 4:06 pm, edited 1 time in total.
studying @ ntu csie

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Re: 11071 need some explanations

Post by Leonid » Mon Aug 14, 2006 8:25 pm

SRX wrote::oops:

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 , :D
Let's put it that way:

> 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!

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

Re: 11071 need some explanations

Post by SRX » Tue Aug 15, 2006 5:46 am

Leonid wrote:
SRX wrote::oops:

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 , :D
Let's put it that way:

> 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!
tks . :D

I think "above permutation" is (724) , but it actually means
(
1 2 3 4 5
3 2 5 1 4
)
studying @ ntu csie

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

Re: 11071 need some explanations

Post by SRX » Tue Aug 15, 2006 4:05 pm

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....n-1)^an-1 .... (123....i+1)^ai+1

:oops:
thanks .
studying @ ntu csie

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Aug 16, 2006 3:33 pm

Hmm, yes. This one's getting on my nerves too. Can't think of anything better than O(N^2). A little hint would be very much appreciated...

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Wed Aug 16, 2006 4:58 pm

A little hint:
If you keep a pointer at the currently last element (elements n, n-1, ... 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.

SRX
Learning poster
Posts: 63
Joined: Sat May 14, 2005 8:13 am
Location: Taiwan

Post by SRX » Wed Aug 16, 2006 6:25 pm

Adrian Kuegel wrote:A little hint:
If you keep a pointer at the currently last element (elements n, n-1, ... 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 !!!!!!!!!!!!

your hint is great and gives me a good thinking to solve this problem within the time limit , anyway , thanks you again :D
studying @ ntu csie

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Wed Aug 16, 2006 7:53 pm

Thanks, Adrian, I think I understand what you mean.
Won't be 'trivial' to implement in C, I fear... realy should learn C++ some day. Or do you have some suggestions on how to do it with 'simple' data structures?

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel » Wed Aug 16, 2006 9:58 pm

I used a binary tree data structure represented in an array like a heap, so my solution can be implemented easily in C as well.

User avatar
little joey
Guru
Posts: 1080
Joined: Thu Dec 19, 2002 7:37 pm

Post by little joey » Thu Aug 17, 2006 8:58 am

Thanks Adrian, I finally got it!
Simple enough, indeed, but I never thought of using a heap this way. One learns something everyday!

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia

Post by StatujaLeha » Sat Aug 19, 2006 6:01 pm

Adrian Kuegel wrote:A little hint:
If you keep a pointer at the currently last element (elements n, n-1, ... 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.
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}?

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Sun Aug 20, 2006 4:26 pm

some I/O please,
Self judging is the best judging!

shanto86
Experienced poster
Posts: 160
Joined: Wed Jul 30, 2003 8:10 pm

Post by shanto86 » Sun Aug 20, 2006 5:08 pm

well... got AC using BST, but i cant understand idea of heap.

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
Output

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!

StatujaLeha
Learning poster
Posts: 91
Joined: Tue May 31, 2005 2:01 pm
Location: Russia

Post by StatujaLeha » Sun Aug 20, 2006 7:57 pm

shanto86 wrote:some I/O please,
Input:
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
Output:
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

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Location: Vancouver, BC, Canada
Contact:

Post by sclo » Fri Aug 25, 2006 8:41 pm

I think what he meant is you do something like this:

Code: Select all

struct node {
  int left, right, val;
};

node A[500000];

where left, right are the index of the left, right children respectively.

Post Reply

Return to “Volume 110 (11000-11099)”