861 - Little Bishops

[merekaru]

My WA Program agrees with your answers, but i believe the input 0 1 is incorrect because n(1<=n <=8) and k(0 <=k <=n^2).

Anyone else?

Btw got AC, try to submit your WA program's output for every n and k, mine got AC right away. Probably the judge misjudge-d me for using MSVC

[noone]

can you guys post the result of these testcases? I'm having big problem calculate these inputs. thanks a ton

Code: Select all

8 59
8 60
8 61
8 62
8 63
8 64

[noone]

nevermind, silly me. they should be all "0"

[icesoft85]

Hi!

I'm having the same problem. I test my solution program with all possible inputs and it runs in less than a second.

My solution won't process a solution for a given input n, k more than once (I store solutions in a table), and it processes all possible solutions in less than a second.

However, when I send it over the Online Judge I get TLE.

Why can this be happening?

Thanks for any help.

Code: Select all

#include <iostream>
#include <stdlib.h>
#include <stdio.h>

using namespace std;

int pos[101][2];

long table[20][20];

int n;

int k;

int bw;

long count1;

bool isValid(int level, int x, int y) {
	int b1 = y - x;
	int b2 = x + y;
	for (int i = 0; i < level; i++) {
		int b = pos[i][0] - pos[i][1];
		if (b1 == b)
			return false;
		b = pos[i][1] + pos[i][0];
		if (b2 == b)
			return false;
	}
	return true;
}

int m[30][30];

void countSols(int level) {
	if (level >= k) {
		count1++;
	} else {
		int pt = (pos[level - 1][0] * n) + pos[level - 1][1];
		int li = -1;
		for (int p = pt; p < n * n; p += 2) {
			int i = p / n;
			int j = p % n;
			if (li != -1 && n % 2 == 0) {
				if (i > li) {
					if (i % 2 == bw)
						p++;
					else
						p--;
					i = p / n;
					j = p % n;
				}
			}
			if (isValid(level, j, i) && p > pt) {
				pos[level][0] = i;
				pos[level][1] = j;
				m[i][j] = 1;
				countSols(level + 1);
				m[i][j] = 0;
			}
			li = i;
		}
	}
}

int main() {
	cin>>n;
	cin>>k;
	for(int i=0; i<20; i++) {
		for(int j=0; j<20; j++) {
			table[i][j] = -1;
		}
	}
	while (n>0 || k>0) {
		if (k == 0) {
			if (n == 0)
				break;
			cout<<1<<endl;
		} else if (n == 1) {
			if (k == 1)
				cout<<1<<endl;
		} else {
			if (k > 2 * (n - 1)) {
				cout<<0<<endl;
			} else {
				count1 = 0;
				if(table[n][k]>-1) {
					count1 = table[n][k];
				}
				else {
				if (n % 2 == 0) {
					int tk = k;
					long cuenta[80];
					long cuenta2[80];
					cuenta[0] = 1;
					cuenta2[0] = 1;
					for (k = 1; k <= tk; k++) {
						count1 = 0;
						bw = 1;
						int li = -1;
						for (int p = 0; p < n * n; p += 2) {
							int i = p / n;
							int j = p % n;
							if (li != -1) {
								if (i > li) {
									if (i % 2 == bw)
										p++;
									else
										p--;
									i = p / n;
									j = p % n;
								}
							}
							pos[0][0] = i;
							pos[0][1] = j;
							m[i][j] = 1;
							countSols(1);
							m[i][j] = 0;
							li = i;
						}
						cuenta[k] = count1;
					}
					count1 = 0;
					for (int i = 0; i <= tk; i++) {
						count1 += (cuenta[i] * cuenta[tk - i]);
					}
				} else {
					int tk = k;
					long cuenta[80];
					long cuenta2[80];
					cuenta[0] = 1;
					cuenta2[0] = 1;
					for (k = 1; k <= tk; k++) {
						count1 = 0;
						bw = 1;
						for (int p = 0; p < n * n; p += 2) {
							int i = p / n;
							int j = p % n;
							pos[0][0] = i;
							pos[0][1] = j;
							m[i][j] = 1;
							countSols(1);
							m[i][j] = 0;
						}
						cuenta[k] = count1;
						count1 = 0;
						bw = 0;
						for (int p = 1; p < n * n; p += 2) {
							int i = p / n;
							int j = p % n;
							pos[0][0] = i;
							pos[0][1] = j;
							m[i][j] = 1;
							countSols(1);
							m[i][j] = 0;
						}
						cuenta2[k] = count1;
					}
					count1 = 0;
					for (int i = 0; i <= tk; i++) {
						count1 += (cuenta[i] * cuenta2[tk - i]);
					}
				}
				table[n][k] = count1;
				}
				cout<<count1<<endl;
			}
		}
		n = 0;
		k = 0;
		cin>>n;
		cin>>k;
	}
}

[pineapple]

Ah~
If you print the results for all possible input,you will immediately find out the mistake out of your imagination.Hope it helps.
Bye~

[farzad.sharbafian]

the question 10237- Bishops is as the same as 861-Bishops but with bigger range of inputs...
& here is it's link for interested people
http://uva.onlinejudge.org/index.php?op ... oblem=1178

[yoojioh]

i keep getting TLE verdicts.... and it's so frustrating..

i have tried 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 it gives me answers in less than 0.5 sec, but the verdict is always TLE...
where can i get the real test cases? or, should my program be faster than this?

Oh, I'm using JAVA, so can it be a problem ??

[brianfry713]

The judge's I/O is usually not published.
Either optimize your code and/or try rewriting it in C.

[pkrupets]

Is this problem solvable by backtracking or should I stop wasting time and move to dynamic programming? Old judge accepts my solution, new one doesn't. Would be nice to know if it's possible at all to use backtracking to solve this problem.

P.S. not sure why would people post bigger bishops problem links here, if not as a hint...

Thank you.

[brianfry713]

Test your code with different inputs and find out.

[pkrupets]

Nice statement.

I have data which covers all test cases: n [1...8], k [0...n^2]. It takes 0.15sec to run them all on my laptop.

So I am not sure what this requirement means: max time 3 seconds. Max time of what? 1 test case? 1'000'000'000'000 test cases? 1'000'000'000'000'000'000'000'000'000 test cases?

My code doesn't work above 8 as it's not a requirement of this task. And I know it won't perform there as it's not designed to do so (any pruning optimizations won't do any good as in case n=30 and k=5 if I place 5 on black to get to 3 seconds I need to speed my code ~100'000 times). Thus the idea to use DP.

[yoojioh]

@pkrupets i think the test case has more than 1500 test cases,
(i experimented with while(i < 1500){ i++; ~~ } )

i think the harder problem --
http://uva.onlinejudge.org/index.php?op ... oblem=1178
is for the dp solution, and this one is for backtracking practice,

but i also could not get ACCEPTED with backtracking....
(my solution takes less than 0.2 sec on my laptop, but the judge apparently is much slower....)

[pkrupets]

Well. If you couldn't pass then how do you know that your assumptions are correct? We can assume the opposite actually (like some or all of your assumptions are wrong).

[brianfry713]

pkrupets, are you getting TLE? Are you using JAVA? Is your I/O fast enough?

[pkrupets]

yes i am getting tle.

I use C++.

What is the definition of fast enough IO? All possible pairs of n and k execute in 0.15 seconds.