Problem Statement |
| | Your friend an interior designer asked you to help him design a lighting scheme for a series of apartments he's working on.
The apartment map is a square of S x S cells. Each cell is either empty or occupied by a wall.
You have to place several light fixtures in the apartment. All fixtures are identical, each one casts light from a single-point source and can illuminate an area of the apartment shaped as a circle. The walls block the light, and the inside of the walls can't be illuminated. If a light fixture is placed on the wall (i.e. on the border between empty cell and wall cell), all its light is blocked by this wall.
Your goal is to place light fixtures so that the area of empty cells illuminated by them is maximized.
Implementation
Your code must implement one method setLights(String[] map, int D, int L):
- map is the apartment map. map[i][j] describes the square in row i and column j: '.' denotes empty space, and '#' denotes a column.
- D is the distance from the light fixture to the furthest point which can be illuminated by it.
- L is the maximum number of light fixtures that can be put in the apartment.
The return from this method will describe the points at which light fixtures should be placed. Each element of the return is a String which describes one point and is formatted as "X Y". X and Y are floating-point coordinates of the point (X corresponds to columns dimension, and Y to rows) written in fixed-point notation with exactly two digits after decimal point.
Scoring
For each test case we will calculate your raw score. If your solution produced an invalid return (too many light fixtures placed, fixtures placed outside of the apartment etc.), raw score for this test case will be 0. Otherwise, raw score will be calculated as follows. For each empty cell of the map, it will be split into 100x100 square sub-cells of equal size. The center of each sub-cells will be tested to check whether it is illuminated, i.e. whether there is a light source at distance at most D from this point for which there are no walls between this point and the light source. The raw score is the number of illuminated centers of sub-cells, divided by the total number of sub-cells in empty cells.
Your overall score will be the average of your raw scores over all test cases, multiplied by 1,000,000.
Tools
An offline tester is available here. You can use it to test/debug your solution locally. You can also check its source code for exact implementation of test case generation and score calculation. That page also contains links to useful information and sample solutions in several languages.
|
| |
Definition |
| | | Class: | Lighting | | Method: | setLights | | Parameters: | String[], int, int | | Returns: | String[] | | Method signature: | String[] setLights(String[] map, int D, int L) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The time limit is 20 seconds per test case (this includes only the time spent in your code). The memory limit is 1024 megabytes. |
| - | There is no explicit code size limit. The implicit source code size limit is around 1 MB (it is not advisable to submit codes of size close to that or larger). Once your code is compiled, the binary size should not exceed 1 MB. |
| - | The compilation time limit is 30 seconds. You can find information about compilers that we use and compilation options here. |
| - | There are 10 example test cases and 100 full submission (provisional) test cases. |
| - | The match is rated. |
| |
Constraints |
| - | The size of the map S will be between 10 and 50, inclusive. |
| - | The number of light fixtures allowed L will be between 2 and 20, inclusive. |
| - | The value of D will be between 2 and 10, inclusive. |
| |
Examples |
| 0) | |
| | | Returns:
"seed = 1
Size of the room S = 5
Room map:
##.#.
.....
...##
.....
....#
Light distance D = 3
Max number of lights L = 2
" | |
|
| 1) | |
| | | Returns:
"seed = 2
Size of the room S = 50
Room map:
.....#......#.......#.........#.#..........#.....#
...........#...#.........#........#....#..........
......###.........##.....#.#.....#..#..#...##.....
.......#....#....#........#..#.................##.
......#.#..#.............................#......#.
.#..............#.....#.#......#.....#...........#
......#..........................#....#..#........
....#..................#......#....#.............#
....................#...#..............#......#...
##.#.......#..........#.......................#.#.
.#..................#.#..#..#....#..........#.....
..#...#...#....#......#..........#.........#......
.........#...#....#............#..#....#..........
.#......##.................#.......#..............
..#.#................#......##.............##.#...
.............#...............................#....
#...#.............................................
..#.......................#.................#.....
#............#............#....................#..
...........#.............#.#.#................#...
#...#..#..#............#.#.............#........#.
..................#...........#..#...#.....#......
................#.#..............#......#.........
.....#.......#.#..................#.......#.......
..............#.#.#........#......#...............
.........#.........#...#..##..##.........####....#
......#....#...##..#..........#...................
.................................#.........#.....#
.....#.#...........................#.............#
.....#.............#...................#....#.....
...#.........#........##..............#...........
.............#......#.........#.................#.
#..#..........................................#...
..................#.........................#.#...
...#...#......#...#..#...........................#
#.........###..............................#......
#..............#.#........#..#.#............#..#.#
..........#............##..#.#.....##..........#..
.#...........#.#...............#......#...#......#
............#..#....#..#.#......#..#..............
........##..#....#..........#....#..#.#....#......
..#..........................##.........#.......##
............##.......#..........#..............#.#
..#..............#......##...#............##......
.....................#....#.#..##..#.#..#......#..
......#.#......#........................#.........
....#.............................................
##................................#............#..
#....#....#....#..#..........#..#......#.....#....
.....#.........#...#...........#.........#........
Light distance D = 10
Max number of lights L = 20
" | |
|
| 2) | |
| | | Returns:
"seed = 3
Size of the room S = 18
Room map:
...#..#...#.......
#..#...........#.#
#....#....#..##.#.
.....#.#...##.....
..#...#...#...#.##
#..##..#..##.....#
.......#....#....#
.#..........##..#.
#........##.......
..#..#..........##
.#.....#...#..##..
#.....###.........
..#.......###...##
#.......#.###.##..
.##..#..##.#..#.#.
.##..##...#.##...#
...##...#.#.#.....
..#...#.#..#..#...
Light distance D = 2
Max number of lights L = 18
" | |
|
| 3) | |
| | | Returns:
"seed = 4
Size of the room S = 21
Room map:
##..#.....#..#....##.
#.......###...##..#.#
..#........##..##.#.#
###..##......##..##..
.........#.....#.....
...#.......#.......#.
...#.#...###.##....#.
......#....###.......
#..##.###......#.....
##..#.....#.#.#...#..
##..#.......#.#...#..
....#.#........##...#
.#..........#...#....
......#.......#......
..#..#.....##........
#...##............#..
..#......###..##.#...
......#....#..#.....#
.#.....#..#..#.....#.
...#.##.#.#..#.#..##.
..##.......#......#..
Light distance D = 2
Max number of lights L = 11
" | |
|
| 4) | |
| | | Returns:
"seed = 5
Size of the room S = 39
Room map:
#..........##....#....#.#...#....#.....
..#.......#..............##.......#..#.
..#...#.....#.....#...#............#.#.
.#.###..#..#.#.#..###...#.##..##..##...
....##.#.....#...##.#..#..#.#..#.#..#..
#........#...........###...#.#........#
#..#.........#....#.#.......#...#...##.
...#.###..##.#.#..#......#..##..#.....#
..#....#.........#.....#..##.........##
.........##.##.........#..#......##.##.
.##.##..#.#..##....#...#....#..#.#...##
...#.....#.##...#........#...###.#.##..
..##....#..#.....########.....#...#..#.
.####......#..####......#.......#..##..
#.#.#.........#...#..##..###...........
....#...#...#..#.......#..#.#.....#..#.
..##......#.......#...##.#.#..#......##
.#..#.#...##.....#.....#....####.#.....
......#.....#..#.....#.....#.#..#.##...
##.........#.#.#.##...##.......####.#.#
##..#..#..#...#.#..#..#....#.###.#.#.#.
.....##...#..###.....#....##..#.....##.
#.##.....#.###..#.###.##...#.#..###....
.#.#.........##...#.#..#..##..#....#.#.
##........###..#..#.....#....#......###
..#......####......##..##.#..#.##....#.
.##....#..##......#...##..##...#.#...#.
........#......#.#.....#....##..#......
...##.#..#....#........#......##....#..
.#.#.......#...#..##..#.....#..#...#.#.
#.#..##.#.#.#.......##.#......##......#
#....##.........#......#............#..
..#.#.#..##........#.....#......#..#.##
..........#..##.#....#..#.#...#.#.#..##
.##.#..........###...#..#.......#...#.#
...#.....#.#..###..............#....#.#
#..#.#.#....##.#..#.##.#..#..#....#.#.#
.#.....#...#.....#..##.....#....#..#..#
#...##..#...#.#.#..#.##...##...#.......
Light distance D = 5
Max number of lights L = 4
" | |
|
| 5) | |
| | | Returns:
"seed = 6
Size of the room S = 43
Room map:
............#.......#...........#..........
.#......#.........................##.......
................#..#.....##................
........#.....#......#.........#.#.........
..........#.#..............#.......##...#.#
...........#...#......#..#..........#......
.#.#.........#.....#.....................#.
........#.##..........#.................#..
.......#.#................#..#.#......#....
#.#.#..........................#...#.......
......#.....................#........#.....
.....#.....#.......#....#..................
...#.......#.......#.#............#.#...#..
.......#..................##......#........
......#...#..............#........#.....#..
...#.#........#........................#...
..#.....#............#...........#.....#...
...................#.......................
..........#........#.......................
...#.#............###.#....#...#......###..
..........#.......#.........#......#..#..#.
#..#..#..##........####..#.....##..........
.....#...#...#......................#.....#
...#...............................#.#...#.
.....#..................#................#.
..........#...........#.........#......#...
..........#............##......#.....#.....
.....#........#........................#...
..#.........#.......#......#.........#.....
..#..............#......#.#................
.....#.....#.#..........#..#..#....#..##..#
..##.......#.......#..........#.......#....
......#..#.......................#.......#.
..........#.......................#.......#
#.....................#....................
....#.....##...........................#..#
..#..##.#.#..........#...#..#..............
....................#.#....................
..........#.............#....#....#........
#....#.....#........#......................
......#..#.................................
......#......##.#...#..##......#.#.........
.....#...............#.#...........#.......
Light distance D = 5
Max number of lights L = 3
" | |
|
| 6) | |
| | | Returns:
"seed = 7
Size of the room S = 14
Room map:
............#.
.#.#.##...#...
..............
.#..#..######.
...........#..
..........#.#.
##............
...#..##......
..#...........
..#.#..#.....#
.....#.##.....
..#..#...#.#..
#...#.#.......
.#........#...
Light distance D = 10
Max number of lights L = 9
" | |
|
| 7) | |
| | | Returns:
"seed = 8
Size of the room S = 27
Room map:
..#.....#..................
.#....#....#...#..##.......
..........#..###......#....
......#.#..#.##.##.........
#.....##.##.......#...#....
##.##..#................#.#
.#.#......#..#.....#.......
..#.....#.##.........#...#.
......#..#.#.....#.........
...#.####.#.......#....#..#
#..#.............#.#...##.#
..##..##...............#.##
..............#.......#..#.
#......#....#....#.......##
....##.#......#..#....##..#
.#..#.#...#.#.......#...#..
#.#..#.....#..#.....#......
..#...##......#...##.#.....
...##.....##....#........#.
..#.#....##..#..###.#.#....
.#.#.#.....#..#......#.....
##.#......##...#..#...#....
....#........#....#........
#...##......#........#..#..
#...........#.......#....#.
#..#..#............#.....#.
#...#..#..#.#........#.#..#
Light distance D = 8
Max number of lights L = 18
" | |
|
| 8) | |
| | | Returns:
"seed = 9
Size of the room S = 30
Room map:
#..#..#..##.##.##.....#.......
#..##....##.#.##..#.......###.
#....#.#..##........##.##..#..
......#.#.#...##......#.##..#.
#....#...##...##......#.##..#.
#....#.#....#.......#.#.......
.......#............#...#..#.#
#.#....................#......
.....##...#.............#..#..
.....#......#.......#...#.....
.#.#.#...#..#...#.#......#..##
#..........#....#.#..#...#...#
..#..#...#....##.#.#.###.....#
....#...........#......#.#.#..
........#.......#.##......#...
.......#...##...#..#..#.#.#..#
....#.........#.#........#.##.
...#.....#.#.#.#...#.#...#.#..
..#......##..#....##...#..#...
.#........##.###..##.#.###.#..
...#.....#.#.......#...##.....
...........#.#..##......#.....
....#....#...........##..##.#.
#......#.............##.......
#..........#....#.....#....##.
...#......#.##....###........#
......#....#.#..#.##......#..#
...#..#...#.#.##..............
.##......#.............#...#..
.......#.....#.#..............
Light distance D = 8
Max number of lights L = 10
" | |
|
| 9) | |
| | | Returns:
"seed = 10
Size of the room S = 25
Room map:
#.....##.....#......#..#.
..####.##..#.#.#.##....##
...#...##..............#.
.#..##......#......#.....
.......#.#..#..##.#...##.
....#..#.....#...#..###..
.#.......#.#...##....##.#
##.......##...#...##.....
..#.#.#.#...###..........
........#....#...#.#....#
.#.#........#....#..#.#..
.##..#.#..##.#..#....#.#.
#..#.....#......#........
....#..#.#.#....##.#..##.
..#.....##...#...#.....##
##.#..#..#....###..#.#...
....#..#..##.#....#.##.#.
...#...#....#..#..#.#.#..
.##....##..#......##..#..
...##..............#.#..#
..##...###....#...##.####
.#.#....#...........#....
.####.#.#..##...#..##.#..
#....###..#...#..#...#.##
...##..##......#....#.#..
Light distance D = 6
Max number of lights L = 13
" | |
|
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)2020, TopCoder, Inc. All rights reserved.
