## 10237 - Bishops

Moderator: Board moderators

ftomi
Learning poster
Posts: 64
Joined: Sun Jan 06, 2002 2:00 am
Location: Hungary
Contact:

### 10237 - Bishops

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

Anderson
New poster
Posts: 6
Joined: Thu Apr 18, 2002 12:47 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
New poster
Posts: 17
Joined: Fri May 24, 2002 4:24 am
Location: Taiwan
Contact:
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?

Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany
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.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
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!

JongMan @ Yonsei

Per
A great helper
Posts: 429
Joined: Fri Nov 29, 2002 11:27 pm
Location: Sweden
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.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:
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!
JongMan @ Yonsei

Marcelo
New poster
Posts: 6
Joined: Sun Sep 30, 2007 7:53 pm