861  Little Bishops
Moderator: Board moderators
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
Also TLE
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.
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;
}
}
To:minskcity
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~
If you print the results for all possible input,you will immediately find out the mistake out of your imagination.Hope it helps.
Bye~

 New poster
 Posts: 1
 Joined: Thu May 19, 2011 9:58 am
Bigger Bishops
the question 10237 Bishops is as the same as 861Bishops but with bigger range of inputs...
& here is it's link for interested people
http://uva.onlinejudge.org/index.php?op ... oblem=1178
& here is it's link for interested people
http://uva.onlinejudge.org/index.php?op ... oblem=1178
Re: 861  Little Bishops
i keep getting TLE verdicts.... and it's so frustrating..
i have tried the input
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 ??
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
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 ??

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 861  Little Bishops
The judge's I/O is usually not published.
Either optimize your code and/or try rewriting it in C.
Either optimize your code and/or try rewriting it in C.
Check input and AC output for thousands of problems on uDebug!
Re: 861  Little Bishops
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.
P.S. not sure why would people post bigger bishops problem links here, if not as a hint...
Thank you.

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 861  Little Bishops
Test your code with different inputs and find out.
Check input and AC output for thousands of problems on uDebug!
Re: 861  Little Bishops
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.
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.
Re: 861  Little Bishops
@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....)
(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....)
Re: 861  Little Bishops
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).

 Guru
 Posts: 5947
 Joined: Thu Sep 01, 2011 9:09 am
 Location: San Jose, CA, USA
Re: 861  Little Bishops
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!
Re: 861  Little Bishops
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.
I use C++.
What is the definition of fast enough IO? All possible pairs of n and k execute in 0.15 seconds.