861 - Little Bishops

[brianfry713]

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?

[pkrupets]

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]

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]

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.