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

brianfry713
Guru
Posts: 5947
Joined: Thu Sep 01, 2011 9:09 am
Location: San Jose, CA, USA

Re: 861 - Little Bishops

Post by brianfry713 » Sat May 19, 2012 12:16 am

For example, scanf/printf are faster than cin/cout. Fast enough depends on the problem, on some there is a large amount of I/O required.

Are you storing all possible values in the program you submit or recalculating them for each input? What happens in your code if the same n and k values are given on many lines in the judge's input file? Are you terminating on n==0 and k==0?
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 » Sat May 19, 2012 12:39 am

As the point here is to find the best algorithm i am not doing any cheating, like storing previously calculated results.

Not sure how many test cases this problem has will think how to improve my algorithm. Will move to use something other than cin but i need to test performance gain (dont think its significant).

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

Re: 861 - Little Bishops

Post by pkrupets » Wed May 23, 2012 7:55 am

Backtracking + caching solves this problem in 0.164sec. Problem is that I am not sure if this is cheating. But I am also not sure how to improve my backtracking any further.

It would be nice to have a better definition on what 3 seconds mean.

hengbinluo
New poster
Posts: 2
Joined: Sun Aug 09, 2015 8:25 am

Re: 861 - Little Bishops

Post by hengbinluo » Sun Aug 16, 2015 6:27 am

pkrupets wrote: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.
My backtracking always exceeds time limit. Try dynamic programming which could run much faster.

Post Reply

Return to “Volume 8 (800-899)”