JOIN
Get Time
long_comps_topcoder  Problem Statement
Contest: TCO Announcement Fun Round
Problem: WaterfallFishing

Problem Statement

    

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.
 

Definition

    
Class:WaterfallFishing
Method:placeTraps
Parameters:String[]
Returns:int[]
Method signature:int[] placeTraps(String[] data)
(be sure your method is public)
    
 

Examples

0)
    
Seed = 1
Width = 20, Length = 10
....................
...................X
....................
....................
....................
....................
.....X.....X...X....
.........X....X.....
..........X.X..X....
.....X.....X........

00116073202010000000
00000000000001104120
00000000002013000000
211270A5B6405I007220

0037M0Q9P9908J20H580

1)
    
Seed = 2
Width = 40, Length = 15
....X....X.....X....X...................
X.........X..........................X..
........................................
.........X...........X.....X.........X.X
..............X....X............X.......
.X..X...................................
......X...............X.................
..X.................................X...
..................X...X.................
X......X..X.....X.................X.....
.......................................X
.......X.....................X.......X..
..........X....X...X....................
......X...............X.....X...........
....................X..................X

00000000000000000000010010020144090C30K0
0K0R0M00D2043200000000000000000000000000
0000010020010000000001000000000000000000
000000000000101002210309956404820D071080
0000000000000000010000000012011103030090
0000000010001100120201012102001406020040
00000000000001001001020313210048060C2080

01010201C10BEVH08S4A0I0F9910012000000000

You can see the fish available to catch on day 1 as an example:

2)
    
Seed = 3
Width = 80, Length = 25
..........X................................X.........................X.X........
.X...X.X........................................................................
..............X....X.................X.X...............X........................
...............X..........................X.X...................X.....X.........
X..............................................X..X......X.X.X..................
.....X..........................X................X............................X.
............X................X.........................................X....X...
..X........X...X......X....X.......X............................................
...X......................................X...............................X.....
....X..........X....X...................X...........X.....X.....................
........X....X...X..................X...........................................
....X..................X................X..X......X.....X...X...................
....................X............X..........X.......X..X........................
..X.............................................................................
.................................X.............X..X............................X
.....................X............X....................................X........
.........................X.X.............................................X......
........X....................X......X.X...X...........X............X...........X
...X.................................X..........................................
...................X....................................X.X.....................
X....X...........X.....................X...X..............................X...X.
..X..........X.......X............................X.........X......X....X......X
.........X.X..X..X....X.........................................X...............
...............................X.......................X.................X......
..X.........................................................X................X..

00000000000000000000000000000000000110100100011000020210030001220030421200343010
00000000000000000000000000000000000000000000000000000000000000010230222930194090
00000000101000002000030100202060770810601930057060020310130200100200600000100000
03002061101001013030400050403020120400100000000010010000000000100000000000000000
000000000000000000001001103030505A0F50A05E10150011000100000000000000000000000000
00000000000000000000000000000000000000100000000000000000130002110310400010041000
03002011105023001010010120000020310000000000000000000000000000000000000000000000
0B0180A4305050037010010100100000000000000000000000000000000000000000000000000000

00001002001000001030100100002010000000100000000001000000010001210760A73730851010

3)
    
Seed = 4
Width = 100, Length = 30
.........X...X..X...X................................X..............X....................X.X..X..X..
..............X..X.X...............X.........X..X......X........X.......X......X.X..........X.......
..........X..X.............X..........X..................X................X.......X............X....
..X....X................X...............................X....X........X............X......X..X......
......X.X.......................X..........X......................X......X.....X......X.........X...
................X..X..X.X............X.X...............X....X.................X...X.................
.................X..........X................X...X.................X....X....X...X...............X..
.X...X....................................X..............X....................X......X.........X....
........X............X..X.......X.....X.........X.....X..........X.............X.......X............
.X.X................X..X.X..........................................X............X......X...........
.............X.....X....X.......X.....X.............X...........................X.........X..X.X.X.X
...X..............X.X....X.............X....X.............................X..X.X....X...............
.............................X......X.X..X.......................X.X...............X.......X........
......X....X......................................X.X...X.................X..........X..X.....X..X..
X................X..X.....X............X...........X...............................X................
........X....X................X................X.X...........X.......X...X...........X......X.......
..........X...............X...........................X.X...................X.......X......X........
....X....X..........X.....................................X....X........X..............X............
...........X.......X.X..X.................X..X...X................................X.X.......X...X...
....X...X................X.............X................X.................X..X..........X...........
...........X........X........................X..X..X................................................
.X.......X.....................X..............X............X.......X..X....X.X....X..X....X.....X...
X...............X.........X...X...X......X...X..X.........X.....X.........X.........X..X............
...................X....X.......X...........X.......X...X..................................X........
.................................X.X....................................X.........................X.
..........X....X...X.......X..........X.......X....X............X....X..............X...............
..............X.....X.X.......................................X...........X............X............
......X..X..................X.......X...................X.......X..............X......X.............
........................X..........X.....................X....X...X......X..........................
.........X............X...........................X....X.......X............X.X........X............

0000000000000000000000000000000000000000000000000000000000000100000000011000010210000310020001010104
0000000010000000000000000001000200100100300200020000020020202210000010010000000000000100000000000000
0000000000000000001000000000000000000100000000010000011000000000000000000000000000000000000000000000
0000000000000000000000000000000000000000000000000000000010001000100100133010010303030100120001030302
0000000000000000000000000000000000000000000000010000000010104120020130060002020101000100010000000000
0110000200001000101000000100010000100000000000000000000000010000000000000000000000000000000000000000
0000000000000000000000000000000000000100001100000200031010101000110000121000000002000010010001000001
00000002000021001110020301100100005003006004010B0402031020401040220100120022020111000000040000000000
0000000000000000000000000000000000000000000000000000000000000100000000010000020000000000000000000200

001000020000200010010102000001000010000000010001000002001000110010012001100004010101034038102E0A0C06

4)
    
Seed = 5
Width = 156, Length = 68
5)
    
Seed = 6
Width = 82, Length = 14
...........................................................................X......
.................X..X...................X.X.......X.............................X.
.............................X................X...................................
.............................................................X..X.....X...X.......
....................................X......................X......................
.....................X.........................................X..X...X...........
X.X...............................X........................X......................
.............................X........................................X........X.X
................X....................................X..............X...........X.
.......X.......X...........X.......................X...........X..................
........................X.........................................................
.......................X.X......................X.................................
..................................................X...........X..............X....
..........X..............X......X..........................................X......

0000000010000000000100101000000202010100010011000201103001000000020501013100203101
0000000000000000000000000000000000000000000000000000000000100000000204021410203102
0102121031020130334200602050202201010101010001010000000100000000000000000000000000
0000000000000000000000000010C09B08010000000000000000000000000000000000000000000000
0000000000000000000000100000000001000301000001020203201000003002310202002300507101
0000000000010000000000000010000000010201010032030301005212006301090407042100608201

0402136053020450356010903060204102000203020110030200302002200502260204030100802101

6)
    
Seed = 7
Width = 112, Length = 97
7)
    
Seed = 8
Width = 105, Length = 47
8)
    
Seed = 9
Width = 41, Length = 62
9)
    
Seed = 10
Width = 46, Length = 27
............X.................................
...........X......................X...........
..................X.........X.............X.X.
...........X....X..........X....X.............
...X......X.........................X........X
......................X....................X..
...X.........................X....X....X......
..............................................
...........................................X..
........X...........................X.........
X............................................X
.......................X............X.........
.....X......X.........X..................X....
.......X................................X.....
X..........................................X..
.................X............................
...X............X..........X..................
....X....X.....X..............................
........................................X.....
..................X.X.X.......................
..............................................
..............X...............................
X...................................X.........
....X....X.X.....X...........X..X.X......X....
..............................................
......X...X.......X......................X....
.......X...........X........................X.

0000010000000100010037015360605407030673103003
0000000000000000001001001160403206050146001300
0000000000000D03D2B052000000000000000000000000
0000000000000000000000000020006203020212105401
0000000010000101000010001000000100000000000000
0230042054001902404001010230101201000000000000
000000000000000000000000000010210604077910G404

000004003001020140601301628090DG0E0A099410D000


This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2010, TopCoder, Inc. All rights reserved.