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 » Sat May 20, 2006 12:33 pm

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 » Thu May 25, 2006 8:13 pm

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 » Thu May 25, 2006 8:20 pm

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 » Fri Sep 22, 2006 9:44 pm

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 » Mon Feb 12, 2007 5:44 pm

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 » Thu May 19, 2011 10:06 am

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 » Sun Apr 29, 2012 6:50 pm

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 » Mon Apr 30, 2012 10:40 pm

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 » Wed May 16, 2012 1:56 pm

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 » Wed May 16, 2012 11:44 pm

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 » Thu May 17, 2012 1:13 am

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 » Thu May 17, 2012 12:54 pm

@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 » Thu May 17, 2012 8:13 pm

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 » Thu May 17, 2012 11:22 pm

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 » Fri May 18, 2012 12:05 am

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)”