Park tourProblem code: KX |
All submissions for this problem are available.
The Chef is strolling in a large nxn square park composed of small unit squares. Some squares are occupied by trees, and the rest is free to walk through them. The Chef wants to lose weight and hence wants to walk a lot. Your job is to create a visiting route which should be as long as possible. The route should be a closed curve with no self-intersections, and is defined by describing the sequence of squares through which it passes. From one square, the route can only proceed to a square which shares a common edge with it. The route enters and leaves each square in the central points of two of its edges. If those two points lie on opposing edges of the square (N - S or E - W), the fragment of the route within the square is a straight line segment of length l=1. Otherwise, if the two points lie on adjacent edges, the route within the square is an arc of the circle (1/4th of the full circle of radius 1/2, centered at the common corner of the edges) and its length is l=pi/4.
Input
In the first line of input there is an integer n (100 n 800), denoting the size of park. The following n lines of n characters each describe the park: the character '*' represents a square with a tree, and the character '.' means that the square is empty.
Output
First, an integer k (0<k), corresponding to the number of lines of the subsequent description of the output. The following k pairs of numbers should describe the squares of the route: i1,j1 ... ik,jk, where i is the row number (counting from 0) and y is the column number (counting from 0) of a square.
Correctness of the output
For each i<k, squares i and i+1 of the route should share a common edge, and moreover the first and the k-th squares should also share a common edge. The route may not make a U-turn at any square, and may not lead through any squares with trees. The route should not self-intersect or touch itself. The route is not allowed to lead outside the park. Note that it is possible for the route to be twice in the same square (i.e. once enter from N exiting due E, later enter from S exiting due W).
Example
Input: 3 ..* ... *.. Output: 8 0 0 0 1 1 1 1 2 2 2 2 1 1 1 1 0 Score: 0.897598
Test distribution
n will be chosen uniformly from the range [100,800] range. The number of trees will be chosen uniformly from the range [n2*alfa,n2*2*alfa), where alfa = 0.1 for 1/3 of the testcases, alfa = 0.02 for 1/3 of the testcases, and alfa = 0.004 for 1/3 of the testcases. Positions of trees are chosen uniformly at random.
Scoring
The score is given as l / f, where l is the total length of the route and f is the total number of squares without trees.
| Author: | admin |
| Date Added: | 30-11--0001 |
| Time Limit: | 10 sec |
| Source Limit: | 50000 Bytes |
| Languages: | ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.0.0-8, CPP 4.3.2, CS2, D, ERL, F#, FORT, GO, HASK, ICK, ICON, JAR, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PHP, PIKE, PRLG, PYTH, PYTH 3.1.2, RUBY, SCALA, SCM guile, SCM qobi, ST, TEXT, WSPC |
Comments
SUCCESSFUL SUBMISSIONS FOR THIS PROBLEM:
Fetching successful submissions
Is judge data not uploaded
Is judge data not uploaded yet? I get Internal Error.
This is fixed.
This is fixed.
" i1,j1 ... ik,jk, where i is
" i1,j1 ... ik,jk, where i is the row number (counting from 0) and y is the column number (counting from 0)"
should be j, not y, ya?
Yes that should be 'j'.
Yes that should be 'j'.
What compiler options do you
What compiler options do you use for the C++ compiler? I am especially interested in knowing if you use -O2 or something similar. Also, how fast is the server?
Is scoring for this problem
Is scoring for this problem correct? I currently have 6 points in the ranklist, but my solution is very trivial. Shouldn't I have 5+eps points with such solution?
Points are not updating when
Points are not updating when a new high score is submitted. Please fix.
hi
hi
hi
hi
hi
hi
My score of 3.2e-5 seems
My score of 3.2e-5 seems incorrect. Please verify. Is the total score the sum of individual test case scores?
I think (at least based on
I think (at least based on the other contests) it is an average, though a current top score of 1.347 seems strangely high if that is the case. So I wouldn't mind this being clarified as well.
I see, if it's the average
I see, if it's the average then the scores make sense.
Another strange thing.
Another strange thing. Rankings show my score as 0.867, which is correct if the top score is actually 1.347. But the list of submissions shows 0.88 although this was the latest submission - nobody submitted after me.
Your sample test case doesnt
Your sample test case doesnt follow your test data distribution constraints.
n*n = 9 here so ideally we shouldnt have had 2 trees ;) [ max 1.8 ]
Ajay: it doesn't say that the
Ajay: it doesn't say that the example has been chosen randomly using the same distribution as the actual tests. It obviously hasn't since n < 100.
Admins: the scores in the scoreboard are still wrong.
Oh yes, I missed that
Oh yes, I missed that completely. Thanks.
I think we've been more than
I think we've been more than just patient so far. Is this discussion intentionally ignored by admins? Any kind of response would be appreciated. Why do relative scores in submissions list differ from those displayed on the rankings? The latter seem to be correct.
This will be fixed soon. As
This will be fixed soon. As of now, the value in the ranklist is correct.
When will the solutions be
When will the solutions be made public, if they will be, at all ?