861

FlareCDE · 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]

Sheng Cheng · 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 · 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 · 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

Niaz Morshed · 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

Whinii F. · 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.

Dejarik · 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

And here is the output:

Code: Select all

Bye bye...

yatsen · 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 · 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 · 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 · 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.

minskcity · 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

[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 · 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 · 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 · 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

OJ Board

861 - Little Bishops

861 - Little Bishops

861 (Little Bishops)

861 - Little Bishops. Please try this input!

Re: 861 (Little Bishops)

861 (Little Bishops) WA - Please check answers