861 - Little Bishops

All about problems in Volume 8. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

FlareCDE
New poster
Posts: 3
Joined: Fri Mar 21, 2003 6:31 pm
Location: New York
Contact:

861 - Little Bishops

Post by FlareCDE » Wed Apr 09, 2003 10:07 pm

I'm getting a time out, and for the life of me, cannot figure out why. I rigged the program so it loops through every possible input the judge can give according to the book I have (1x1 to 8x8 board with up to 64 bishops), and it easily completes on my computer in under a second or two with all inputs. Any subset of then should be faster...

[cpp]
#include <stdlib.h>
#include <cstdio>

int findEven(int* board, int numBishops, int boardSize, int currRow, int color)
{
int y,z;
int solutions = 0;
int notFound;
int boundry;
if(boardSize % 2 == 0)
{
if(currRow <= (boardSize-2)/2)
{
y = (boardSize/2)-(currRow+1);
boundry = (boardSize/2)+currRow;
}
else
{
y = (boardSize/2)-(((boardSize-2)-currRow)+1);
boundry = (boardSize/2)+((boardSize-2)-currRow);
}
}
else
{
if(color == 0)
{
//printf("Color 0: ");
if(currRow <= boardSize/2)
{
y = boardSize/2 - currRow;
boundry = boardSize/2 + currRow;
//printf("Row #%d, Left Side: %d bounded on %d",currRow,y,boundry);
}
else
{
y = boardSize/2 - (currRow - boardSize/2);
boundry = boardSize/2 + (currRow - boardSize/2);
//printf("Row #%d, Right Side: %d bounded on %d",currRow,y,boundry);
}
}
else
{
//printf("Color 1: ");
if(currRow <= boardSize/2 - 1)
{
y = boardSize/2 - currRow - 1;
boundry = boardSize/2 + currRow;
//printf("Row #%d, Left Side: %d bounded on %d",currRow,y,boundry);
}
else
{
y = boardSize/2 - (currRow - boardSize/2) - 1;
boundry = boardSize/2 + (currRow - boardSize/2);
//printf("Row #%d, Right Side: %d bounded on %d",currRow,y,boundry);
}

}
}
//printf("\n");
//printf("Boardsize=%d, Column=%d, y=%d, boundry=%d\n",boardSize,currRow,y,boundry);
for(y; y <= boundry; y++)
{
//for(x = 0; x <= boardSize-2; x++)
//{
// if(board[x] > 0 && x < currRow)
// {
// printf("%d ",board[x]);
// }
// else if (x == currRow)
// {
// printf("<%d> ",y);
// }
// else
// {
// printf("* ");
// }
//}
notFound = true;
for(z = 0; z < currRow; z++)
{
if(board[z] == y)
{
//printf(" FAILS.\n");
z = currRow;
notFound = false;
}
}
if(notFound)
{
board[currRow] = y;
if(numBishops == 1)
{
//printf(" SOLUTION.\n");
solutions++;
}
else
{
//printf(" PLACED.\n");
//printf("numBishops-1: %d <= %d : B value\n",numBishops,(boardSize-2)-(currRow+1));
if(currRow < boardSize-2 && numBishops-1 <= (boardSize-2)-currRow)
solutions += findEven(board,numBishops-1,boardSize,currRow+1,color);
}
}
}
board[currRow] = -1;
if(numBishops <= (boardSize-2)-currRow) solutions += findEven(board,numBishops,boardSize,currRow+1,color);
//printf("BACK.\n");
return(solutions);
}

int main(int argc, char *argv[])
{
int boardSize;
int numBishops;
int whiteResult;
int x,y,z;
scanf("%d %d",&boardSize,&numBishops);
//boardSize = 1;
while(boardSize != 0 || numBishops != 0)
{
// for(y = 8; y >= 0; y--)
// {
// for(z = 0; z <= y*y; z++)
// {
// boardSize = y;
// numBishops = z;
// printf("%d x %d, with %d bishops = ",boardSize,boardSize,numBishops);
if(numBishops == 0) printf("1\n");
else
{
if(boardSize % 2 == 0)
{
//even number board, do only white and square
int* whiteBoard = new int[boardSize-1];
int* resultBoard = new int[numBishops+1];
for(x = 0; x < numBishops+1; x++)
{
resultBoard[x] = 0;
}
resultBoard[0] = 1;
if(numBishops >= 1) resultBoard[1] = (boardSize*boardSize)/2;
for(x = 2; x <= numBishops; x++)
{
if(x <= (boardSize-1)) resultBoard[x] += findEven(whiteBoard,x,boardSize,0,0);
else x = numBishops+1;
//printf("Finished with %d\n",x);
}
//printf("\n");
whiteResult = 0;
for(x = 0; x <= numBishops; x++)
{
whiteResult += (resultBoard[x] * resultBoard[numBishops-x]);
//printf("For (%d+%d) = %d, %d*%d, %d solutions found.\n"
// ,x,numBishops-x,numBishops,resultBoard[x],resultBoard[numBishops-x]
// ,(resultBoard[x] * resultBoard[numBishops-x]));
}
//printf("\n");
printf("%d\n", whiteResult);
delete resultBoard;
delete whiteBoard;
}
else
{
//odd number board, do both black and white
int* whiteBoard = new int[boardSize];
int* blackBoard = new int[boardSize-1];
int* resultWhite = new int[numBishops+1];
int* resultBlack = new int[numBishops+1];
for(x = 0; x < numBishops+1; x++)
{
resultWhite[x] = 0;
resultBlack[x] = 0;
}
resultWhite[0] = 1;
resultBlack[0] = 1;
for(x = 1; x <= numBishops; x++)
{
resultWhite[x] = 0;
resultBlack[x] = 0;
if(x <= boardSize)
{
resultWhite[x] += findEven(whiteBoard,x,boardSize,0,0);
if(x <= boardSize-1) resultBlack[x] += findEven(blackBoard,x,boardSize,0,1);
}
else x = numBishops+1;
//printf("Finished with %d\n",x);
}
whiteResult = 0;
for(x = 0; x <= numBishops; x++)
{
whiteResult += (resultWhite[x] * resultBlack[numBishops-x]);
//printf("For (%d+%d) = %d, %d*%d, %d solutions found.\n"
// ,x,numBishops-x,numBishops,resultWhite[x],resultBlack[numBishops-x]
// ,(resultWhite[x] * resultBlack[numBishops-x]));
}
//printf("\n");
printf("%d\n", whiteResult);
delete whiteBoard;
delete blackBoard;
delete resultWhite;
delete resultBlack;
}
}
scanf("%d %d",&boardSize,&numBishops);
//}
//}
}
return 0;
}
[/cpp]
- Flare Araxion

Sheng Cheng
New poster
Posts: 1
Joined: Sun Jun 08, 2003 2:51 am

Post by Sheng Cheng » Sun Jun 08, 2003 2:55 am

Without considering the Time Limit Exceed, I think your code is still wrong. Try testdata 5 1. Your output is 24. But the answer is of course 25.

reiners
New poster
Posts: 9
Joined: Fri May 30, 2003 6:50 pm
Location: San Francisco

861 (Little Bishops)

Post by reiners » Tue Jul 22, 2003 7:18 pm

I'm having the same problem.

Has anyone got their submission to this accepted? My submission runs in less than a second for any given input (I wrote a driver program to check this on all possible inputs), yet it still times out.

Here is my code for anyone interested:

Code: Select all

/*   @JUDGE_ID:   29339ZA   861   C++   "Backtracking"   */

#include <iostream>
#include <cstdlib>
// #include <ctime>
using namespace std;

#define MAXCANDIDATES   100		/* max possible next extensions */
#define NMAX            100		/* maximum solution size */

void dumpSolution(int n, int k);

typedef char* data;			/* type to pass data to backtrack */

long solution_count;			/* how many solutions are there? */

bool occupied[15][15];



void process_solution(int n, int k)
{
    solution_count++;
    // dumpSolution(n, k);
}

void dumpSolution(int n, int k) {
    cout << "n = " << n << "; k = " << k << endl;
    for (int i = 0; i < 15; i++) {
	for (int j = 0; j < 15; j++) {
		if (occupied[i][j]) {
			cout << "X";
		}
		else {
			cout << "O";
		}
	}

        cout << endl;
    }
    cout << endl;
}

bool is_a_solution(int m, int k)
{
	return (m == k);
}

int getMaxFile(int n, int rank) {
    return n - abs(rank) - 1;
}


/*	What are possible elements of the next slot in the Little Bishops
	problem?
*/

void construct_candidates(int m, int k, int n, int c[MAXCANDIDATES][2], 
                          int *ncandidates, int last, bool isCorner)
{
    int i,j;			/* counters */
    bool legal_move;		/* might the move be legal? */
    
    bool fileIsCorner;
    if (n % 2 == 0) {
        fileIsCorner = !isCorner;
    }
    else {
        fileIsCorner = isCorner;
    }

    *ncandidates = 0;
    int maxI;
    if (isCorner) {
        maxI = n - 1;
    }
    else {
        maxI = n - 2;
    }
    for (i = last + 2; i <= maxI; i += 2) {
        int maxJ = getMaxFile(n, i);
        int minJ = -maxJ;
        for (j = minJ; j <= maxJ; j += 2) {
            legal_move = true;
            if (occupied[i + n - 1][j + n - 1]) {
                    legal_move = false;

                    continue;
            }
            if (legal_move) {
                int minRank;
                int maxRank;
                if (isCorner) {
                    maxRank = n - 1;
                    minRank = -(n - 1);
                }
                else {
                    maxRank = n - 2;
                    minRank = -(n - 2);
                }
                for (k = minRank; k <= maxRank; k += 2) {
                    int maxFile = getMaxFile(n, k);
                    int minFile = -maxFile;
                    for (int l = minFile; l <= maxFile; l += 2) {
                            if (occupied[k + n - 1][l + n - 1] && (i == k || j == l)) {  /* diagonal threat */
                                    legal_move = false;

                                     break;
                            }
                    }
                    if (!legal_move) {
                            break;
                    }
                }
            }
            if (legal_move == true) {
                    c[*ncandidates][0] = i;
                    c[*ncandidates][1] = j;
                    *ncandidates = *ncandidates + 1;
            }
        }
    }
}


bool finished = false;                  /* found all solutions yet? */

void backtrack(int m, int k, int n, int lastRank, bool isCorner)
{
        int c[MAXCANDIDATES][2];        /* candidates for next position */
        int ncandidates;                /* next position candidate count */
        int i;                          /* counter */

        if (is_a_solution(m, k))
                process_solution(n, k);
        else if (m < k) {
                m = m+1;
                construct_candidates(m, k, n, c, &ncandidates, lastRank, isCorner);
		for (i=0; i<ncandidates; i++) {
                    occupied[c[i][0] + n - 1][c[i][1] + n - 1] = true;
                    backtrack(m, k, n, c[i][0], isCorner);
                    occupied[c[i][0] + n - 1][c[i][1] + n - 1] = false;
                    if (finished) return;	/* terminate early */
		}
        }
}

void initializeOccupied() {
    for (int i = 0; i < 15; i++) {
	for (int j = 0; j < 15; j++) {
		occupied[i][j] = false;
	}
    }
}


long solve(int n, int k) {
    long totalCount = 0;
    if (k <= 2 * n - 1) {
        for (int cornerK = 0; cornerK <= k; cornerK++) {
            solution_count = 0;
            initializeOccupied();
            backtrack(0, cornerK, n, -(n - 1) - 2, true);
            long cornerCount = solution_count;

            int nonCornerK = k - cornerK;
            solution_count = 0;
            initializeOccupied();
            backtrack(0, nonCornerK, n, -(n - 2) - 2, false);
            long nonCornerCount = solution_count;

            totalCount += cornerCount * nonCornerCount;
        }
    }

	return totalCount;
}

/*
int main2 (int argc, const char * argv[]) {
    int n;
    int k;
	time_t start,end;
	double dif;
	double max = 0.0;

	printf("n, k, time, count\n");
    for (n = 1; n <= 8; n++) {
		for (k = 0; k <= n * n; k++) {
			time (&start);
			long totalCount = solve(n, k);
			time (&end);
			dif = difftime (end,start);
			if (dif > max) {
				max = dif;
			}
			printf ("%d, %d, %.2lf, %d\n", n, k, dif, totalCount);
		}
    }

	return 0;
}
*/


int main (int argc, const char * argv[]) {
    int n;
    int k;

    while (cin >> n >> k) {
		if (n == 0 && k == 0) {
		  break;
		}

        long totalCount = solve(n, k);

		cout << totalCount << endl;
    }

    return 0;
}

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Mon Aug 04, 2003 1:34 pm

first of all, never show your id in board. it may cause great harm. again to all,
i think there is a common recurrence formula for calculating. what is that?
--
thanking for help
anupam :oops: :oops:
"Everything should be made simple, but not always simpler"

Niaz Morshed
New poster
Posts: 12
Joined: Sun Nov 09, 2003 1:27 am
Location: East West University, Dhaka.
Contact:

861

Post by Niaz Morshed » Sun Nov 09, 2003 7:48 pm

Any one can help me saying a formula for this problem ? Thanks in advance :D
The Last Man Standing :-)

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

Post by Whinii F. » Fri Nov 14, 2003 10:13 am

No one can help by saying a formula, because giving out formulas can never help someone :)

Here you have some observations:

Assume a chessboard with black and white squares. If a bishop is on a white square, can it attack bishops on black squares? No.

So you can divide the chessboard into two independant ones.
Hope this was a hint. :)

ps) but, I myself solved this with brute force enumerating with recursion & some discrete math. 8)
JongMan @ Yonsei

Dejarik
New poster
Posts: 32
Joined: Sun Mar 07, 2004 1:23 pm
Location: Barcelona, SPAIN
Contact:

861 - Little Bishops. Please try this input!

Post by Dejarik » Tue Mar 30, 2004 6:26 pm

Hi! I'm trying to solve the problem 861, and I don't understand why I'm receiving Wrong Answer. Please can you check the following input in your accepted programs and report me the solution obtained?

Thanks you very much in advance, Joan

That's the input:

Code: Select all

8 6
4 4
8 15
8 12
8 0
5 1
5 5
5 9
8 10
1 1
1 0
7 8
0 0
And here is the output:

Code: Select all

5599888
260
0
489536
0
25
3368
0
12448832
1
0
867328
Bye bye...

yatsen
Learning poster
Posts: 68
Joined: Fri Nov 23, 2001 2:00 am
Location: taiwan

Post by yatsen » Thu Apr 01, 2004 11:32 am

your answers are right except for the following inputs:
8 0
1 0

your answer is 0, but the correct answer is 1.

Dejarik
New poster
Posts: 32
Joined: Sun Mar 07, 2004 1:23 pm
Location: Barcelona, SPAIN
Contact:

Post by Dejarik » Thu Apr 01, 2004 1:00 pm

How can't I think about it???

The number of ways to put 0 bishops in a NxN chessboard is not 0, it's of course 1: leaving it blank! When I think all the time I spent to solve this stupid mistake...

Thank you very much!

Joan

macin
New poster
Posts: 6
Joined: Tue Apr 06, 2004 6:40 pm

Post by macin » Tue Apr 06, 2004 6:43 pm

why dont you precalculate all necessary 212 input possibilities and output them (should be faster :)
greets
tobias

anupam
A great helper
Posts: 405
Joined: Wed Aug 28, 2002 6:45 pm
Contact:

Post by anupam » Wed Apr 07, 2004 9:57 am

There is a solution using DP and some greedy decision. But, I can't explain them so good. So, I request some ither programmers who have solved the problem to explain the matter.
"Everything should be made simple, but not always simpler"

minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » Sat Jun 12, 2004 7:23 am

My code gives correct answer to all inputs from the posts... Can any body find a case when it fails??? I'm keeping getting WA :oops: [cpp]#include <iostream>
#include <string>
using namespace std;

char help[10][10];
long long aa[10][30][2];
long long ans[10][70];
long pos[50][2];
long p, n, in1, in2;

bool good(const long &x, const long &y){
return x > -1 && y > -1 && x < n && y < n;
}

void recur(long x, long y, long depth){
aa[n][depth][p]++;
pos[depth][0] = x;
pos[depth][1] = y;

for(long i = 0; i < n; i++)
for(long j = 0; j < n; j++)
if(i*n + j > x*n + y){

memset(help, -1, sizeof(help));

for(long ii = 1; ii <= depth; ii++)
for(long kk = -7; kk < 8; kk++){
if(good(pos[ii][0] + kk, pos[ii][1] + kk)) help[pos[ii][0] + kk][pos[ii][1] + kk] = 0;
if(good(pos[ii][0] + kk, pos[ii][1] - kk)) help[pos[ii][0] + kk][pos[ii][1] - kk] = 0;
}

if((i + j + p)%2 && help[j])
recur(i, j, depth + 1);
}
}

int main(){

memset(aa, 0, sizeof(aa));
for(n = 1; n <= 8; n++)
for(p = 0; p < 2; p++)
for(long i = 0; i < n; i++)
for(long j = 0; j < n; j++)
if((i + j + p)%2){
aa[n][0][p] = 1;
recur(i, j, 1);
}

memset(ans, 0, sizeof(ans));
for(long i = 1; i <= 8; i++)
for(long j = 0; j <= i*i; j++)
for(long k = 0; k <= j; k++)
ans[j] += aa[k][0]*aa[j - k][1];

ans[1][1] = 1;
for(long i = 0; i <= 8; i++) ans[0] = 1;
while(cin >> in1 >> in2 && in1 + in2){
if(in1 > 8 ) while(true);
cout << ans[in1][in2] << endl;
}
return 0;
}
[/cpp]

Alexander Denisjuk
New poster
Posts: 35
Joined: Sat Jan 05, 2002 2:00 am
Contact:

Post by Alexander Denisjuk » Sun Apr 24, 2005 12:16 am

I missed the solution
(1 1) => 1
Check, may be also you missed it.
By the way, the solution not only less than 10^15, but fits into int

ulfurinn
New poster
Posts: 1
Joined: Sun Apr 02, 2006 3:36 pm

Re: 861 (Little Bishops)

Post by ulfurinn » Sun Apr 02, 2006 3:55 pm

FlareCDE wrote:I'm getting a time out, and for the life of me, cannot figure out why. I rigged the program so it loops through every possible input the judge can give according to the book I have (1x1 to 8x8 board with up to 64 bishops), and it easily completes on my computer in under a second or two with all inputs. Any subset of then should be faster...
This is a clear indication that the amount of run tests is large enough to generate >10s of total time :)
Think of the cases where you can get an answer instantly, so you don't waste time calculating it... like, when is the answer 0?

marek
New poster
Posts: 1
Joined: Mon May 01, 2006 11:56 am

861 (Little Bishops) WA - Please check answers

Post by marek » Mon May 01, 2006 12:08 pm

Hi

I finally managed to make a solution fast enough but now i'm getting WA.
Please check if these are right. I think i'm going mad already....

Code: Select all

0 1
0
1 0
1
1 1
1
2 0
1
2 1
4
2 3
0
3 3
26
3 4
8
3 5
0
4 6
16
4 7
0
5 8
32
5 9
0
6 10
64
6 11
0
7 12
128
7 13
0
8 14
256
8 15
0
8 30
0
8 1
64
8 7
14082528
8 8
22522960
0 0

Post Reply

Return to “Volume 8 (800-899)”