CCC '00 S5 - Sheep and Coyotes
View as PDFCanadian Computing Competition: 2000 Stage 1, Senior #5
A square by
field contains several sheep. A coyote enters the field at some point in the south boundary and proceeds to eat the sheep closest to the point of entry, picking arbitrarily if more than one sheep is equally close. The coyote, being sated, then leaves the field.
Your job is to determine which sheep may be eaten by the coyote.
Assume that the southwest corner of the field is located at , the northwest corner at
, the northeast corner at
and the southeast corner at
.
Input Specification
The first line of input gives the number of sheep, between and
. For each sheep a pair of lines follows, giving its coordinates within the field (between
and
).
Output Specification
For each sheep that might be eaten print a line The sheep at (x, y) might be eaten. where and
give the location of the sheep to two decimal places. The sheep can be listed in any order in the output.
Sample Input
6
100.00
100.00
200.00
150.00
140.00
200.00
100.00
300.00
300.00
300.00
300.00
100.00Sample Output
The sheep at (100.00, 100.00) might be eaten.
The sheep at (300.00, 100.00) might be eaten.
Comments
Am I doing something wrong for test case 6, or is this a floating point error?
This is how I tackled the float point imprecision for test case #6:
Since by default floats have a precision of around 24 bits or 7 decimal places (reference), if the decimals get too small the program would not make the precise calculations. To counteract this I shifted the decimals up a few places by multiplying all the values by 10^3. Because I know that the x and y coordinates would not exceed 1000, there was no need to worry about encountering overflow errors.
I've seen a lot of WA's on this problem (especially on test case 6), many of which have the correct algorithm but WA because of floating point imprecision. For example, with Python 3, you likely will not pass using floats (depending on your algorithm) because they are not accurate enough. To work around this, consider using the decimal module as described here and make sure not to use float() anywhere in your program (although I'm sure there are other workarounds). I'm not sure about other languages.
Normally I wouldn't leave "hints" in the comments, but to a beginner who has never heard of the concept that computers can't store decimals perfectly accurately, they could potentially waste hours debugging their conceptually correct algorithm in vain. Hope this helps.
For the output, would you still round to 2 decimal places for case 6? And should the rounding be half-up or just truncated? I'm using the decimals module and it's still not working.
Also why do they have to troll us like this, case 6 wasn't even in the CCC ._.
Your mistake is that you're putting l >= r on line 36 in your latest submission, when in fact l == r gives a valid interval. As a side note, I believe they prefer people asking for help on discord instead of the comments to avoid clogging up the comment section.
It's possible for multiple sheep to have the same coordinates right? And we have to output whether they might be eaten for each of them?
Does the coyote enter anywhere in the "bottom" of the land, the problem does not state where it enters.
Yes
Did a test case get added to this problem?
We added PEG's additional (anti-brute force) testcase and rejudged all submissions.
The old cases make up 50/100 points, so only passing the original cases will still give you 10 points on the problem.
What is the intended time complexity for that test case?
solution passed in 0.133s.
DMOJ judges are too fast, we could kill that by making TL go down to 0.05 or something, but then we'd have to tune TLs for other languages and it's not worth the effort.
There's a hard version for anyone who wants to try their hand at solving the problem with larger constraints.
For those who keep getting WA on case 5, this picture might be helpful.
Each point represents a sheep. All sheep not colored in green might be eaten.
How is this possible, I don't really understand? The bottom most black dot is closer to the x-axis than the others.
if the coyote comes from the right-most part of the x-axis, then that black dot is the furthest from the coyote
Oh, thank you
Why am I getting wa for all cases? I checked the official test data, and my program matches the expected output?
Make sure to format your output to 2 decimal places.
when I submit in PyPy I get MLE, even though it only uses around 5 mb when I submit it in Python? any reason for this?
Yes, the memory limit for this problem is 16M, and even a hello world program uses 30M in PyPy. That's the trade-off between performance and memory usage.
Is case 5 testing for a precision error or am i making another mistake?