Page 1 of 1

10237 - Bishops

Posted: Sat Apr 27, 2002 9:29 pm
by ftomi
I have no idea about the solution.
Can you help me?

Posted: Tue May 28, 2002 3:18 pm
by Anderson
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!!

Posted: Sun Jul 21, 2002 6:24 pm
by Shih-Chia Cheng
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?

Posted: Tue Jul 23, 2002 11:18 pm
by Adrian Kuegel
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.

Posted: Sat Dec 27, 2003 4:46 pm
by Whinii F.
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. :)

Posted: Tue Dec 30, 2003 1:34 pm
by Per
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".

Posted: Wed Dec 31, 2003 3:16 am
by Whinii F.
Hi, Per! :D

After correcting a SILLY SILLY VERY SILLY mistake in the size of the array, my program got AC. :) How silly I was :oops:

Thank you very much, again.

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

Posted: Thu Nov 08, 2007 4:01 am
by Marcelo
Anybody can explain Adrian's message?
I tried, but I dont understand his variables...