10237 - Bishops

ftomi · Post by **ftomi** » Sat Apr 27, 2002 9:29 pm

I have no idea about the solution.
Can you help me?

Anderson · Post by **Anderson** » Tue May 28, 2002 3:18 pm

If you consider the problem ,which is about Root instead of Bishop,
maybe it is easy.
now ,you could rotate the board by 45 degrees , then youn could consider the Bishop like a Root.
Good lucK!!

Shih-Chia Cheng · Post by **Shih-Chia Cheng** » Sun Jul 21, 2002 6:24 pm

Anderson wrote:If you consider the problem ,which is about Root instead of Bishop,
maybe it is easy.
now ,you could rotate the board by 45 degrees , then youn could consider the Bishop like a Root.
Good lucK!!

hmm...I rotate the board by 45 degrees and then don't know what to do next...
Can you explain how to use DP to solve this problem?

Adrian Kuegel · Post by **Adrian Kuegel** » Tue Jul 23, 2002 11:18 pm

You extract from the rotated board all Fields of one colour. For n=4 you have:

Code: Select all

   .
  ...
  ...
   .

Let this figure be B.
You add to this figure points to make a rectangle, the added points are A.
In this example you have a 4x3 rectangle. Imagine you have placed k-r rooks on points in A and r rooks on points in B and they are in nonattacking positions. Let A_k-rB_r be the number of possibilites to place the rooks in this way. If you want to add another rook, you have (n-k)*(m-k) possibilities. If you placed the rook in figure A, you have (k-r+1) identical placements, if you placed it in figure B, there are (r+1). So you have the equation:
(n-k)*(m-k)*A_k-rB_r = (k-r+1)*A_k-r+1B_r+(r+1)*A_k-rB_r+1
If you know all A_kB_0 and A_0B_1, you can calculate all A_0B_k.
With this equation you can solve the problem, but it is a bit difficult, I needed several hours.

Whinii F. · Post by **Whinii F.** » Sat Dec 27, 2003 4:46 pm

1. Can anybody verify some inputs & outputs?

input wrote:10 18
8 5
8 8
8 7
30 38
30 9
30 10
30 0
0 0

output wrote:1024
1444928
22522960
14082528
1459678371142772586080904047004955072918158573568
198564604657832714496
11540432810453797635840
1

2. I'm curious about the judge's limit with the resulting number. Is it true? Did anybody get AC with 64bit integers?

My long long int program works elegantly for all sample cases, but it resulted in WA. So I inserted a line like
[cpp]assert(sum < (long long)1000 * 1000 * 1000 * 1000 * 1000);[/cpp]
and look! I got SIGABRT at once.

And actually my program causes overflow in cases like 30 38..

So I pasted in my VERY-VERY-slow bigint routine and converted all the procedures (boring work) and got WA in 9.773 sec.

I'm confused!

Thanks in advance.

Per · Post by **Per** » Tue Dec 30, 2003 1:34 pm

Yes, long long is sufficient to get AC.

Your I/O are correct (though my program overflows on the three big ones, so I don't know about those), but I see you have no odd n among them, so you could try the input "5 5" which should give "3368".

Whinii F. · Post by **Whinii F.** » Wed Dec 31, 2003 3:16 am

Hi, Per!

After correcting a SILLY SILLY VERY SILLY mistake in the size of the array, my program got AC.

How silly I was

Thank you very much, again.

Happy new year! Looking forward to see you in Prague!

Marcelo · Post by **Marcelo** » Thu Nov 08, 2007 4:01 am

Anybody can explain Adrian's message?
I tried, but I dont understand his variables...