OJ Board

Amazingly I found a couple places of improvement in my code above that resulted in about a 45% faster program. I updated the code in my post above, I edited 'tile' slightly by adding an extra else statement, and I also edited 'getMax' slightly by precalculating the startup maxvalue at the current ...

This is my java code without my GUI stuff with it to view the squares once completed.


public BSP(int squareSize) {
this.squareSize = squareSize;
squareGrid = new int[squareSize*squareSize];
amounts = new int[squareSize];
solution = new int[squareGrid.length];
calcDist = new int[squareGrid ...

Hi poixp,

You did a good job with the techniques you supplied. I have enjoyed this problem for quite some time and my solving program uses most all of those to find minimal solutions. My tip is to remove #5 in your list as there are minimal solutions that don't use a square of size 1, which are 19 ...

(x,y) xth row yth column is correct.

If you have an error then it is probably related to something else in the logic part of the code.

everything looks good, just make sure the program uses the cordinates given as row column and not column row.

The few places I ran into RE with this problem was reading the goal cordinates in the wrong order. I also missed the fact that goal cordinates can have 2 digits. The last place I had trouble with RE was related to reading the cordinates wrong, and happened when the program would check a square that ...

O(n)? I don't see any relationship between the numbers and their answers, other than the fact that at some point when you reach an odd prime number that hasn't been used in the factors of the previous answers its answer will be p-1 p-1 0. What am I missing that makes this problem easy to calculate?

I think they finally got around to fixing it cause I got accepted now :). I however don't understand why my implementation of a priority queue for A* got WA. I assume it's because it returns a non lexigraphic solution. Shouldn't the priority queue be sorted by depth+heruistic, and if that is equal ...

Kinda weird, but my code keeps getting RTE now. I have changed my code to make it A*, and im fairly certain it works. Has the input set changed at all? And if it has is there an error in it? Can you guys submit again to see if you get RTE as well?

Care to elaborate any? Binary search of what?

Yes, thats implied in the problem and my thoughts above. My major problem is how to exactly figure out the minimum angle needed to kill all ghosts for any test case after the intial setup is complete like in my last graph. It can turn out to be a lot more complicated than the one in the test case.

I have been trying for a while now to find the best way to do this problem. :o.

The way I am thinking about doing this problem is as follows:

Read a ghost's posistion, check and see if this ghost is independent from all other ghosts. I define independent as that its angle between its two points ...

I also tried but the hueristic I came up with only reduced the end node count by about 3%. Not enough to improve time by much, specially since it takes extra implementation to add in the hueristic.

Well I improved upon my program, and made a BFS solution that can solve the 53 step maze in ~11s. Not sure if Ill be able to improve it without fully understanding how to add the hueristic function into my program without killing it :) (I have tried adding some hueristic but so far it doesn't work ...

Ok I have a decent understanding of how A* works. Another helpful site I found was http://www.policyalmanac.org/games/aStarTutorial.htm . The problem I am having now is figuring out how to use it for multiple goals, which I don't see being easy to do.