OJ Board

i checked the permutations i generate with a AC code of 10730.
although the permutations are antiarithmetic , i m gettin WA.

You can check out with waterloo's code.
Be sure about the correct output format.

ok, i just checked with waterloo's code.
the permutations are antiarithmetic.
but still WA.

the problem statement says: 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.

can anyone give me some tips to solve this problem?

could anyone give me brief description of waterloo's code?
what is it?
i searched by google but i couldn't find it

How to solve it? thx!

How to solve it? thx!

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.

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.

to sunny:

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

Thanks

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?

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

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