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

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

11129 - An antiarithmetic permutation

Post by sunny » Mon Oct 23, 2006 8:49 am

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

Post by Emilio » Mon Oct 23, 2006 4:49 pm

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

Post by sunny » Mon Oct 23, 2006 8:44 pm

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

Post by sunny » Mon Oct 23, 2006 9:02 pm

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

[]

Post by ziliang » Tue Oct 24, 2006 6:53 am

can anyone give me some tips to solve this problem?
不鸣则已,一鸣惊人.

Artikali
Learning poster
Posts: 68
Joined: Wed Sep 21, 2005 5:27 pm

Post by Artikali » Tue Oct 24, 2006 5:50 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

Post by Emilio » Tue Oct 24, 2006 6:16 pm


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

Post by liulike » Thu Oct 26, 2006 9:26 am

How to solve it? thx!

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

Post by liulike » Thu Oct 26, 2006 9:28 am

How to solve it? thx!

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

Post by sclo » Thu Oct 26, 2006 8:33 pm

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

Post by sunny » Thu Oct 26, 2006 9:12 pm

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

Post by liulike » Fri Oct 27, 2006 5:37 am

to sunny:

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

Thanks :D

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

[ ]

Post by ziliang » Fri Oct 27, 2006 7:39 am

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

[ ]

Post by ziliang » Fri Oct 27, 2006 8:27 am

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

Post by sunny » Fri Oct 27, 2006 9:30 am

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

Post Reply

Return to “Volume 111 (11100-11199)”