OJ Board

Someone who got AC, how fast does your program run on the input produced by this program?

My program (currently the fastest on the ranklist) takes 6.5 sec on my Pentium-II 400.
My program is currently the second on the ranklist ;) And it runs < 0.1 sec. on this test.
My program's complexity is ...

- Do a brute force for the first king's path

But isn't it O(2^30) ?

Can somebody help to solve this problem? I don't know algorithm faster than O(2^30)...

I don't know how you can come up with 100 000000 such a big number.
Consider we have 50 knights where every one can walk 50 steps.
Maximum number of covered square < 50 x 35000 = 1750000
Even you sort all the 1750000 squares in a qsort, the number of operation should be < 1 0000000 (although ...

I used hash, but my program is too slow. I think a best algorithm should has about 100 000000 operations, isn't it? If you've done this problem can you send me solution? pserega@r66.ru

Hi, everyone!
Can you give me some hints how to solve the problem. My algo is too slow. How can it be done?
Thx

Dear Jury!
What is the tricky input tests of this problem?
Only 5 AC of almost 1000 submits!!!

Oops...
Sorry, it will be on 08.11.2003

Don't miss contest of Ural server on 01.11.2003 !!!
Visit this link : http://acm.timus.ru/schedule.aspx

I' ve solved this problem, but my algorithm works too slow.
My result is the worst in statistics.
But some people got AC faster than 1 sec/ Can somebody explain me how to solve it faster?
Thanks!

I used the following algorithm:

ans(a,b)=a+b-gcd(a,b);

ans(a,b,c)=a+b+c-gcd(a,b)-gcd(a,c)-gcd(b,c)-gcd(b,c)+gcd(a,b,c)

ans(a,b,c,d)=a+b+c+d-gcd(a,b)-...-gcd(c,d)+gcd(a,b,c)+gcd(a,c,d)+gcd(a,b,d)+gcd(b,c,d)-gcd(a,b,c,d)

I cant proove it for dimension higher than 3, but for dimensions 1,2 or 3 a ...

Some tests:
1
3
3 6 2
0 0 0
answer is: 6

1
5
1 2 3 4 5
0 0 0 0 0
answer is: 10

1
4
10 13 11 5
-4 -2 4 8
answer is: 28

1
452 467 18 454 28 70 43 152 56 24
345 544 5645 78 455 5666 789 764 53 3
answer is: 13544

Hm, i do the same thing, but still WA.
Can somebody prove that greedy method give the correct answer?

I can't understand, why my algorythm is wrong. I've checked it many times. Can somebody give me test cases.

I used the following algo:
Let K-the maximum number of mission for one game. I find first increasing subsequense of length K, delete it from original sequense. Then repeat it.

Both codes got AC.
How did you got PE?