| | Notes: Many elements of this problem may not resemble reality, have somewhat more randomized
luck than usual, and are made up for the sole purpose of producing a fun introductory marathon-style
challenge.
Problem Description
You are planning to setup fish traps to catch some fish while attending TCO, and have been informed
by some locals that the bottom of a large waterfall is a great place, since some fish are inevitably carried
downstream and go over the falls. Being a bit of a data enthusiast, you theorize that by keeping track of
counts of fish for several days ahead of time, you may be able to get some sense of where fish are most likely
to be caught. (A description of how the river is modelled and fish locations are generated is given later
in the problem statement below.) Because you don't want to miss any of the TCO action, you will only setup
your traps once, and will collect them after three days.
Submission Description
You should produce a single method, placeTraps, which receives a single parameter
String[] data. Each element of data represents the fish seen across the width (W) of
the river for a single day. Each character indicates the number of fish seen at that location, up to
a maximum of 35. (A = 10, Z = 35) It is possible that any location may actually see more than 35
total fish, but since your traps can't hold more than that, you stop counting after 35.
Your method should return an int[] indicating the location(s) where you would like to place
traps to collect fish the next day. The length of the return should be between 1 and W. Each value
should be between 0 and W-1, with no duplicates. Any invalid return will score no points for the test case.
Scoring
The raw score for a given test case will be fish-caught / total-traps. Note that each
trap will catch a maximum of 35 fish, as you only collect once at the end of the three days.
The overall score
across all test cases will be the sum of the relative scores for each test case. Your relative score
for a single test case is given by YOUR / BEST, where YOUR = your raw score on that case and BEST =
the highest score anyone achieved on that test case.
Test Case Generation
- The width of the river, W, is chosen (uniformly) between 20 and 200.
- An upstream (empty) river length, L, is chosen (uniformly) between 5 and 100.
- A number of rocks is chosen (uniformly) between 5 and W*L/10.
- The location of each rock is chosen (uniformly) as a random point (0..W-1, 0..L-1).
- If any location is chosen where there is already a rock, or that is directly adjacent to
another rock (up/down or left/right), a new location is chosen.
- A number of days of data are chosen between 4 and 20, which will be used for the data provided to your code.
Three additional day of data will be generated as the "ground truth" against which you will be tested.
- The remaining steps are performed for each day's worth of data, including the three days against which your trap placement will be tested:
- A number of fish is chosen (uniformly) between 5 and 100.
- Two values, M and S, are chosen (uniformly) such that M is in the range 0..W-1 and S is in the range 2..W/4.
- Each fish is generated with a starting position selected for a normal distribution with mean M and standard deviation S.
- If any fish is generated outside the bounds of the river, a new location is chosen.
- Each fish travels down the river. If at any point it meets a rock, it moves one unit to the left or right (at random, unless against the edge of the river).
- This simulation continues for each fish until it goes over the waterfall and lands in it's final location (0..W-1).
- Note that only the value of W is given (implied by string length) as part of the input to
your code. The other data is used for generating the location of fish over the waterfall on each
day, but is not explicitly provided.
Notes and Local Testing
- A local tester is available here.
- The time limit per test case is 60s, and the memory limit is 1GB.
- There are 10 example tests, 50 provisional tests, and there will be 1,000 system tests.
|
