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

merekaru
New poster
Posts: 1
Joined: Sat May 20, 2006 12:30 pm

Post by 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 :D

noone
New poster
Posts: 2
Joined: Thu May 25, 2006 8:07 pm

Post by 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
New poster
Posts: 2
Joined: Thu May 25, 2006 8:07 pm

Post by noone »

nevermind, silly me. they should be all "0" :-D

icesoft85
New poster
Posts: 4
Joined: Sun Mar 26, 2006 5:51 am
Contact:

Also TLE

Post by 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
Learning poster
Posts: 57
Joined: Fri Nov 03, 2006 3:33 pm

To:minskcity

Post by 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. :D
Bye~

farzad.sharbafian
New poster
Posts: 1
Joined: Thu May 19, 2011 9:58 am

Bigger Bishops

Post by 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 :D
http://uva.onlinejudge.org/index.php?op ... oblem=1178

yoojioh
New poster
Posts: 5
Joined: Sun Apr 29, 2012 6:47 pm

Re: 861 - Little Bishops

Post by 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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 861 - Little Bishops

Post by brianfry713 »

The judge's I/O is usually not published.
Either optimize your code and/or try rewriting it in C.
Check input and AC output for thousands of problems on uDebug!

pkrupets
New poster
Posts: 6
Joined: Wed May 16, 2012 1:51 pm

Re: 861 - Little Bishops

Post by 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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 861 - Little Bishops

Post by brianfry713 »

Test your code with different inputs and find out.
Check input and AC output for thousands of problems on uDebug!

pkrupets
New poster
Posts: 6
Joined: Wed May 16, 2012 1:51 pm

Re: 861 - Little Bishops

Post by 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
New poster
Posts: 5
Joined: Sun Apr 29, 2012 6:47 pm

Re: 861 - Little Bishops

Post by 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
New poster
Posts: 6
Joined: Wed May 16, 2012 1:51 pm

Re: 861 - Little Bishops

Post by 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
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 861 - Little Bishops

Post by brianfry713 »

pkrupets, are you getting TLE? Are you using JAVA? Is your I/O fast enough?
Check input and AC output for thousands of problems on uDebug!

pkrupets
New poster
Posts: 6
Joined: Wed May 16, 2012 1:51 pm

Re: 861 - Little Bishops

Post by 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.

Post Reply

Return to “Volume 8 (800-899)”