11129 - An antiarithmetic permutation

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

Moderator: Board moderators

liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am

Post by liulike » Fri Oct 27, 2006 3:04 pm

Cool..
sunny wrote:let n=13,
first consider 2 0.
now, you've 2 insert 4 and (4,2,0) forms an arithmetic progression. so, insert 4 in the middle of (2,0) so the sequence will be : 2 4 0.
then, it's 6. two arithmetic progression with 6 are (2,4,6) && (0,3,6).
since i put all odd numbers right of 0 and there cant be any (even,even,odd) or (even,odd,odd) progression so, the odd differenced triples can be ignored. so, 6 should be inserted between (2,4) & the sequence will be: 2 6 4 0.
now, u've 2 insert 8. among the two progressions (4,6,8 ) & (0,4,8 ) the (0,4,8 ) is the most differenced one. put 8 between (4,0). as 6 & 8 will be in two different sides of 4, there cant be (4,6,8 ). the sequence will be:2 6 4 8 0
thus, for 10 : 2 10 6 4 8 0 (between 2 and 6 )
thus, for 12: 2 10 6 4 12 8 0 (between 6 and 0 )

the odd numbers can be put on a same way : 2 10 6 4 12 8 0 1 9 5 3 11 7

ziliang
New poster
Posts: 19
Joined: Sat Sep 30, 2006 2:50 pm

[ ]

Post by ziliang » Fri Oct 27, 2006 4:46 pm

still dont quite understand..

but will try to figure it out :wink:
不鸣则已,一鸣惊人.

ziliang
New poster
Posts: 19
Joined: Sat Sep 30, 2006 2:50 pm

how?

Post by ziliang » Fri Oct 27, 2006 5:00 pm

wow~ got it. really a cool way.

but how do you prove it correct?

I mean how do you prove that correct when you insert 8 between 0 and 4 that 4 6 8 will not form a progression?


sunny wrote:let n=13,
first consider 2 0.
now, you've 2 insert 4 and (4,2,0) forms an arithmetic progression. so, insert 4 in the middle of (2,0) so the sequence will be : 2 4 0.
then, it's 6. two arithmetic progression with 6 are (2,4,6) && (0,3,6).
since i put all odd numbers right of 0 and there cant be any (even,even,odd) or (even,odd,odd) progression so, the odd differenced triples can be ignored. so, 6 should be inserted between (2,4) & the sequence will be: 2 6 4 0.
now, u've 2 insert 8. among the two progressions (4,6,8 ) & (0,4,8 ) the (0,4,8 ) is the most differenced one. put 8 between (4,0). as 6 & 8 will be in two different sides of 4, there cant be (4,6,8 ). the sequence will be:2 6 4 8 0
thus, for 10 : 2 10 6 4 8 0 (between 2 and 6 )
thus, for 12: 2 10 6 4 12 8 0 (between 6 and 0 )

the odd numbers can be put on a same way : 2 10 6 4 12 8 0 1 9 5 3 11 7
不鸣则已,一鸣惊人.

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

Re: how?

Post by sclo » Sat Oct 28, 2006 10:33 am

ziliang wrote:wow~ got it. really a cool way.

but how do you prove it correct?

I mean how do you prove that correct when you insert 8 between 0 and 4 that 4 6 8 will not form a progression?


sunny wrote:let n=13,
first consider 2 0.
now, you've 2 insert 4 and (4,2,0) forms an arithmetic progression. so, insert 4 in the middle of (2,0) so the sequence will be : 2 4 0.
then, it's 6. two arithmetic progression with 6 are (2,4,6) && (0,3,6).
since i put all odd numbers right of 0 and there cant be any (even,even,odd) or (even,odd,odd) progression so, the odd differenced triples can be ignored. so, 6 should be inserted between (2,4) & the sequence will be: 2 6 4 0.
now, u've 2 insert 8. among the two progressions (4,6,8 ) & (0,4,8 ) the (0,4,8 ) is the most differenced one. put 8 between (4,0). as 6 & 8 will be in two different sides of 4, there cant be (4,6,8 ). the sequence will be:2 6 4 8 0
thus, for 10 : 2 10 6 4 8 0 (between 2 and 6 )
thus, for 12: 2 10 6 4 12 8 0 (between 6 and 0 )

the odd numbers can be put on a same way : 2 10 6 4 12 8 0 1 9 5 3 11 7
There's a slight modification that is easy to prove why it works.
Recall that (even,even,odd) or (even,odd,odd) can't be an arithmetic sequence. First, initialize the list with 0 to n-1, then we consider moving all even numbers to the left of the list, and all odd numbers to the right of the list.
Now, recursively, compute the left half of the list (even) and right half of the list (odd). To compute the left half, we first divide each number by 2, then we would get a similar subproblem. To compute the right half, we subtract 1 and then divide each number by 2, then we would also get a similar subproblem. In order to print the correct output, we must remember the original numbers. The algorithm has runtime O(n log n). The reason why it works is because if a sequence is antiarithmetic, then multiplication and/or addition each term by a constant would make the sequence stay antiarithmetic (in other words, solution to subproblems are valid). And also (even,even,odd) and (even,odd,odd) can't be arithmetic, so the 2 recursively computed sequences could be concatenated to form a single sequence (in other words, the 2 subproblems are independent). I'm sure it is less than 30 lines of code.

I can't quite prove that sunny's algorithm is correct, but I'm quite sure that mine is correct from the above.

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Post by sunny » Sat Oct 28, 2006 12:11 pm

i admit that sclo's algorithm is smarter than mine.
but i can prove the correctness of my algo.
when inserting 8 between (4,0) there cant be any progression like (8,6,4) cuz 8 is on right of 4.
look between the numbers 6,8,10,12... are inserted. it's like: (2,4),(4,0),(2,6),(6,0).....(2,k),(k,0),(2,k+2),(k+2,0).......
as 8 is inserted between (4,0), 6 should be between (2,4). so, 6 is on left of 4. so, there cant be any progression like (4,6,8 ).

boshkash1986
New poster
Posts: 21
Joined: Tue Jan 10, 2006 12:25 am

Post by boshkash1986 » Thu Feb 22, 2007 1:01 pm

thanks to sclo explanation of the problem I got AC and here is my explanation of sclo code with example if it could help

n = 10
first recursive call with seperation of even and odd to left and right
2 4 6 8 0 1 3 5 7 9
divide each even by 2 and each odd by ((odd-1)/2)
1 2 3 4 0 0 1 2 3 4
second recursive call for the left part(i will ignore the right part for simplicty (you will do exactly the same))
seperating even and odd
1 2 3 4 --- we get-----> 2 4 1 3
divide the each even and odd as described above
1 2 0 1
third recursive call on the even side
seperate the sides
1 2 ---we get ---> 2 1
and we end here for this branch of recursive call
so if we trace back the origin of the last two numbers (which are 2 and 1) we will find that they are 4 and 8 and so we get the antiarithemtic permutation

of course anyone can trace back the numbers to their origin
i hope i am clear and thanks again for sclo algo

wallace
New poster
Posts: 10
Joined: Thu Feb 26, 2009 4:03 pm

Re: 11129 - An Antiarithmetic Permutation

Post by wallace » Mon Sep 07, 2009 10:20 pm

I am difficulties to write the function !
can someone help me?
look:

pseudocode

void myfuction(int start, int end, int vecto){

if(end - start == 1)return;

separates_ side_even_ and_ odd();
myfuction(start,index_vector_even,even)
m = (length_even+length_odd)/2;
myfuction(m+1,index_vector_odd,odd)
join(even,odd);

}
thank you!

Post Reply

Return to “Volume 111 (11100-11199)”