MosaicProblem code: GX |
All submissions for this problem are available.
Imagine a large mosaic made of glass. It has the form of a large square, of size n x n, made up from unit squares of different types of glass. Different types of glass have different physical parameters, such as the speed of light in the material.
We have a source of light in corner (0,0) and a light detector in corner (n,n). We would like to estimate as accurately as possible the path taken by a ray of light which is directed from the source and reaches the detector, knowing that of all the possible routes, the one chosen by light will be the one with the shortest travel time.
Each type of glass has 3 defining parameters, denoted o1,o2, and ang. In order to calculate the travel time of light along some straight line segment in one specific type of glass, we calculate the lengths l1 and l2 of the projections of this segment onto two perpendicular lines: onto the axis forming angle ang with the horizontal direction (X axis), and onto the axis perpendicular to it. Then, the travel time of light along the given segment is given as sqrt((l1*o1)2+(l2*o2)2).
Input
First, 1500 <= n <= 2000, the size of mosaic. Then, n rows, n numbers in each, describing the o1 values for each square, with the x-th number in the y-th line corresponding to the square with its top left-hand corner at (x,y). Then, in the same way, come n rows of n numbers defining values of parameter o2, and n rows of n numbers defining values of parameter ang. The angle is given in radians, and for each square we have, 0.1 <= o1,o2 <= 100, 0 <= ang <= 2pi
Output
You should describe describe the route from (0,0) to (n,n) by outputting k (k <= 106) and then the coordinates of k midpoints of the route (the points (0,0) and (n,n) should not be output). The route must follow the following rules: each segment between successive points of the route starts on a side of some unit square and ends on a side of this square, and the segment between them lies entirely within this unit square. Successive midpoints must be different from each other, route segments may not run along edges of unit squares, and are not allowed to lead outside of the mosaic.
Scoring
Your score is equal to the travel time of light along the fictional route defined by your solution (summed over all data sets). The goal is to minimize the obtained score.
Example
Input: 2 1.0 2.0 3.0 1.0 1.0 1.0 1.0 1.0 0 0.785398 0.785398 0 Output: 2 0.5 1 1 1.5 Score: 3.650282
| Author: | admin |
| Date Added: | 15-08-2009 |
| 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, 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
how many digits of precision
how many digits of precision are the numbers in the input data going to contain?
i find it a bit ridiculous
i find it a bit ridiculous when a program that simply reads the input data and does nothing else exceeds the time limit
Same for me. Reading all
Same for me. Reading all input with scanf gives time limit exceeded. That is rather ridiculous, especially after all the discussion about this after the last few contests.
Can you please tell us how
Can you please tell us how this problem is judged.. when I had a path going from eg (1,1) to (2,1+1e-6) I was getting WA, yet when I changed this to 1e-5 I got TLE. This suggests to me that the judge is set up rather badly and thinks that the former case counts as going along an edge.
Is the example
Is the example correct?
According to my calcutation the result should be 4.35739
from 0 0 to 0.5 1
-> 1)
cell 0 0
sqrt((0.5*1)^2) + (1)^2) = 1.118
-> 2)
cell 0 1 (acording to the problem statement it's first character in the second line)
sqrt((0.5*3)^2) + (0.5*1)^2) = 2.12 or sqrt((0.5*1)^2) + (0.5*1)^2) = 1.118
(that depends on the angle, we can form angle ang in two ways, depending how we interpret problem statement)
-> 3)
cell 1 1
sqrt((0.5*1)^2) + (1)^2) = 1.118
the resut is either 4.35739 or 2.94317
The only way that I see to get score score of
@stephen Judge has
@stephen
Judge has epsilon=1e-6, so line (1,1)->(2,1+1e-6) is considered as too close ( 1+1e-6 == 1 for judge).
There's no way that judge can timeout, so it's your fault if your program gets TLE.
@pmnox holy shit, I again
@pmnox
holy shit, I again made same mistake..
judge code:
for(int x=0;x<n;x++)
for(int y=0;y<n;y++)
read(angle[x][y]);
so, tables descriptions are in wrong way, should be:
y-th number in x-th line
the calculation is as follow:
given dx,dy:
nx = dx*cos(ang) + dy*sin(ang)
ny = dy*cos(ang) - dx*sin(ang)
l = sqrt( (nx*o1)^2 + (ny*o2)^2 )
so in example, result is: sqrt(5/4)+sqrt(2)+sqrt(5/4)
I tested all 8 posibilites.
I tested all 8 posibilites. (X Y not swapped, Y X swapped)
(ang, ang + pi/2, -ang, pi/2 - ang)
I index all tables with [X][Y].
If I output pair (X, Y) I always get score > 20000 and it doesn't matter which ang I use. I get score bad always
If I ouput pair (Y,X) I get scores < 12000
only one out of 4 posibilities generates score 6000.
This behavious is completly different from what you described.
@Przemyslaw Uzbanski I agree
@Przemyslaw Uzbanski
I agree that your explanation explains the test example . However scores on server seem to be a little bit different.
@pmnox I think, that for
@pmnox
I think, that for optimalising problems, judge code should be public.
I can't release it here, because it would make contest unfair.
But there isn't any kind of 'magic' there, code is really simple.
And I can't assume anything about correctness of your code...
I tried all combination. One
I tried all combination. One of them works. That's just fine work me. In the future I would be usefull to get an working example. Like the simples algorithm implemented in C++. That chooses a path containing (n-1) edges and returning calculated score.
Why is it not possible to
Why is it not possible to submit problems? Timer said 7 hours ago. That it will be possible to do it for 16 more hours?????
The timer has been broken for
The timer has been broken for a while (http://discussed.codechef.com/showthread.php?t=587)
Sorry for this. It wll be
Sorry for this. It wll be fixed as soon as possible.