## 11129 - An antiarithmetic permutation

Moderator: Board moderators

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

### 11129 - An antiarithmetic permutation

i checked the permutations i generate with a AC code of 10730.
although the permutations are antiarithmetic , i m gettin WA.
Last edited by sunny on Mon Oct 23, 2006 8:42 pm, edited 1 time in total.

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain
You can check out with waterloo's code.
Be sure about the correct output format.

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET
ok, i just checked with waterloo's code.
the permutations are antiarithmetic.
but still WA.

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

Code: Select all

``````Each line of the input file contains a natural number 3 ≤ n ≤ 10000.
``````
but i got AC just after i changed my program for a input of n<3.
so, there are cases where n=1 or n=2.

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

### []

can anyone give me some tips to solve this problem?

Artikali
Learning poster
Posts: 68
Joined: Wed Sep 21, 2005 5:27 pm
could anyone give me brief description of waterloo's code?
what is it?
i searched by google but i couldn't find it

Emilio
Experienced poster
Posts: 163
Joined: Sun Oct 17, 2004 8:31 pm
Location: Murcia, Spain

liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am
How to solve it? thx!

liulike
Learning poster
Posts: 52
Joined: Wed Jul 30, 2003 10:56 am
How to solve it? thx!

sclo
Guru
Posts: 519
Joined: Mon Jan 23, 2006 10:45 pm
Contact:
This is the only problem that I don't know how to do yet.
Here's what I know, the number of solution is too small to do backtracking. So we need some O(n log n) solutions. I think that even O(n^2) will tle. The idea would be to look into some special properties of the solutions.

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET
My solution is like O(n^2) while the loop is for even numbers.
It worked really fast.

I considered a permutation where all even numbers are left of 0 & odds are on right. Suppose, u've to insert pk. It can always be in the middle of most distant (pi,pj) without forming an arithmetic progression.
Suppose, the so far generated sequence is 2 6 4 0.
So, 8 can be inserted between 4 and 0. then the sequence will be: 2 6 4 8 0.
The same patterned permutation will also be antiarithmetic for the odd numbers.

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

What the relationship between pi, pj and pk. Could you give out some detailed explanation about your algorithm?

Thanks

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

### [ ]

i think the O(n^2) algorithm will not get a tle

first,calculate the permutation for N=10000

then,for the case n<=10000,the solution is the subset of the former permution,from which you just need to printf the element that is smaller than or equal to n.

then we just need to compute 10000^2 times.
and in my computer,10000^2 will not exceed 1 second.

but i still dont know how to solve it...

anyone give some help?

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

### [ ]

to sunny:

when inserting 8,would you consider 4 and 6?

obviously,8 is between 4and6, and , 4and0
then,there will be no place for 8

i think i dont quite understand your method

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET
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