Hello everyone!Exiting to be starting a new set of challenges!Is there an upper bound to the size of the problem, such as the maximum dimentions of the board or the length of the longest solution path?

11 posts / 0 new
Last post
For more complete information about compiler optimizations, see our Optimization Notice.

I was hoping for a reply from the Judges before now. I don't feel I can put off coding any longer, so I'm going to code a solution using 15-bits for each board dimension, so a co-ordinate will fit within a signed int. I hope that's a large enough range.

I've passed your question to the judges.See if they can provide a reply by Monday for you.

The maximum number of circles may also helpful.

Sorry for a delay in our reply. Long weekend holiday!

Please review the "Input Description" section and "Input file example, gridin.txt" which indicate the problem size and the # of circles.


I've reviewed the description several times, and find just this text indicating the size of a particular problem instance:

The first line will be two integers denoting the dimensions of the grid, number of rows and number of columns.

As far as I understand, that doesn't give any bounds the overall problem (all instances). Can you please state the precision required, or the maximum size of the board.

At the very least we should know if the row/column coordinate will fit in a short or if an int or long is needed. However, I imagine that abritrary puzzles > 32k will be unsolvable.

The bounds are quite large for this problem (something thatwould fit into 32-bit integer). So, please try to solve this problem for an arbitrary large size grid pattern to validate your results.


Can I beg you to be more accurate about the problem description? If the bounds fits in a 32-bit integer, is that signed or unsigned? Does this mean the board could be 2^32-1 large? That sounds absurd to me, and difficult to code on languages without unsigned types. The amount of memory required might also be prohibitive.In the previous challenges, the problem was under specfied, but these were cleared up in the few days following the start of the challenge. It's 2 and a half weeks into the challenge and we still don't have a clear idea of the size limits of the problem.
You mention arbitrarily large sizes - the only solution there is to use arbitrary length arithmetic. Surely you don't really mean that?

We are sorry for the confusion everyone.
There will certainly not be any boardswith sideslarger than 32767 so you can use signed (or unsigned) short (16-bit) integers for the (x,y) coordinate centers if you wish. I would use typedef in C for example and allow yourself to time your program with int's and short int's to see which is faster.

Even a thousand by thousand grid problem is quite intensive. You are correct. Billion by billion grids are not in scope for this competition. We certainly did not mean to imply arbitrary length arithmetic. Feel free to use signed or unsigned short's or int's. Those will handle the test problems.

Leave a Comment

Please sign in to add a comment. Not a member? Join today