Problem Statement |
| | You are given a square map of S x S cells. Each cell is a square area of certain terrain type, with side of length 1. Terrain types are denoted with digits from 0 to 9, which describe the cost of passing through this terrain, per unit: 0 is the easiest to cross, and 9 is the hardest. The cost of passing through the square is calculated by multiplying the Euclidean distance travelled with the terrain type. When you cross a border between two terrain types, you incur additional cost of (difference of terrain types)^2.
There are N items located on the map, and N target locations to which these items have to be delivered. Items are identical, so each item can be delivered to any location, but each location must have exactly one item delivered to it. You can carry at most capacity items at once. You automatically pick up an item if you stop within 10^-3 from it and still have capacity to carry it, and you automatically drop off an item at a target location if you stop within 10^-3 from it while carrying at least one item and no item has been delivered to this location yet.
Your task is to enter the map at any place along its border, pick up all items and deliver them to target locations, and exit the map at any place along its border.
Implementation
Your code must implement one method getPath(String[] terrain, double[] locations, int capacity):
-
terrain gives the map of terrain types in the area. terrain[i][j] describes the type of terrain in the square with coordinates [j, j+1] x [i, i+1]. Characters '0'..'9' represent types 0..9.
-
locations gives the list of items and target locations for them. For N items and N target locations, locations will contain 4*N elements. First 2*N elements will describe positions of items: ith item is located at coordinates (locations[2*i], locations[2*i+1]). Next 2*N elements will describe target locations: jth target location has coordinates (locations[2*N+2*j], locations[2*N+2*j+1]).
-
capacity gives the maximum number of items you can carry at once.
The return from this method will describe a path you want to take. The path is a sequence of points within the map connected by segments; i-th point of the path has coordinates (return[2*i], return[2*i+1]). The path must satisfy the following conditions:
-
The path must have between 2 and 4 * S^2 * (number of items) points, inclusive.
-
All points must be inside the map. Coordinates must be greater than 0 and less than S.
-
The first and the last points of the path must be within 10^-3 from the outer border of the map.
-
All points of the path must be at least 10^-3 away from internal borders between the cells of the map (even if cells on both sides of the border are of the same terrain type).
-
Consecutive points of the path must be at least 10^-3 away from each other. (Euclidean distance).
-
Each segment of the path can cross at most one boundary between cells of the map, i.e. the Manhattan distance between cells to which consecutive points of the path belong can be at most 1.
-
After the path is walked, all items must be picked up and all target locations must have an item delivered to them.
Example
An example solution for seed 1 can be seen in the image. The items is shown with green dots and the delivery locations with red dots. The example path is shown in blue.
Scoring
For each test case we will calculate your raw and normalized scores. If your solution returned invalid path (some points outside the map or too close to the borders, not all items picked up and delivered etc.), raw score will be returned as -1. Otherwise, raw score will be the total cost of the path, calculated as sum of costs of passing through terrain done on each segment of the path (for each part of the path which passes through terrain of the same type its cost is the length of the part, multiplied by cost of this terrain type) and additional costs of changing terrain types. The normalized score for each test (except those that failed and scored a -1) is 1,000,000.0 * BEST / YOUR, where BEST is the lowest raw score currently obtained on this test case (considering only the last submission from each competitor). Finally, your total score is equal to the arithmetic average of normalized scores on all test cases.
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: | TerrainCrossing | | Method: | getPath | | Parameters: | String[], double[], int | | Returns: | double[] | | Method signature: | double[] getPath(String[] terrain, double[] locations, int capacity) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The time limit is 10 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 terrain types T will be between 2 and 10, inclusive. |
| - | The number of items N will be between 5 and S*S/10, inclusive. |
| - | The carrying capacity capacity will be between 1 and 10, inclusive. |
| |
Examples |
| 0) | |
| | | Returns:
"seed = 1
Size of terrain S = 5
Number of terrain types T = 3
Terrain:
00100
01102
11000
01011
01001
Capacity C = 2
Number of items N = 4
" | |
|
| 1) | |
| | | Returns:
"seed = 2
Size of terrain S = 20
Number of terrain types T = 4
Terrain:
21100121112211001001
21110012222110001111
11211112222221111211
01222112211221212111
11221111111121112211
11121000100111111111
11111011210111211121
11211112221122112211
11111112221111123221
11122211221100122222
11122211222101101122
11211121211110111121
11111121122111111111
11211121222111211112
11211011221211111112
11111121111111011112
11111221011111011211
11110111111211100121
11101111112221100211
12211211222210001221
Capacity C = 2
Number of items N = 10
" | |
|
| 2) | |
| | | Returns:
"seed = 3
Size of terrain S = 30
Number of terrain types T = 6
Terrain:
343311232343322233322333232223
333222232333322233323333332333
343222223333332333234333333322
543333233333333223344333343222
443333322223344334443332332222
443322233233233333333332232223
333322223344323333333232222222
333323322344333333222232222222
333323322233322222222222232223
323323322232321112222222222234
333323322232322222322222221233
233322322232222233333333322233
123332222332232234433333333334
223332122322232233332333333222
233321112322332233332333333223
333222222222222233322332322123
333233222322332334332222232233
333234323333332343331233333343
222234322223332233432233333332
222233322223432233432333343333
233344322223332223443333333232
233433333333232224444432223332
234432233433332234334333222233
223332343333333223333233332222
223343443333343234444333343222
234443332334343334444333333322
334443333334333334444333322223
323322233344332234443323332334
222222333333322234333222334433
222332323332222244333223333432
Capacity C = 3
Number of items N = 15
" | |
|
| 3) | |
| | | Returns:
"seed = 4
Size of terrain S = 50
Number of terrain types T = 10
Terrain:
67666667666566666676654577763457776555667887466664
66776766766666456667654467765446664556766777667764
66666677666676444446643456665334433456765656666774
55676677887776433334545556665444333567764445777864
55676677886776433445654456776555333445655567787643
44475567775676544556664456665556555455555566776554
54466666665566656666565446655466456776656655675565
54566776566666667655553335655566567776766667776667
44457786544555556643343334566676577876676667788876
45557887655665677754454554457776677775666766666663
77656687666776578866544444567765567777655655565663
57644576655776456657765435666555666666644565666665
68744556664566566546656445665666665677544566777665
78756556775456666445666445675565665567544555676555
57655668875345656556767545675665666667544566555568
56654567776456657776777644565544555666446666666556
56644556888777667776677654565543456775456556776667
55555555678877766665665444445534678786566556675556
56666554556666776556664344444446776666666666664345
46555664345566666567775455564447665445567665664455
36543454444578887666676677665566566556566777665455
67654555444577678655665788866666566666556788765443
66766566445576457755555778776556667777645566665533
46776566334675344555556667666666676777655555676555
56677665446775454565566566566555687657755454565454
77788755545453454555566666577755787778866555654465
56787655643333454555677776676655577778866677764466
66676655654556764444577776655555567788856677764456
46666555644578865566567765444567655678767766776566
56556555554567986677678754455666765667777644566666
65555443566556776667577755555655565666677633455566
64455454688754554577556765545655565545577632344455
64454455787743556787667754556654455445676534576444
54545455687754567787767764666654454345765445677543
45534444576555555677666655654554456566655565677654
67655554565566656666565566555665556677544455666556
66766776566677766676555665455766667777654455555557
44567777667676555666555666455655667767654566555666
34567655666666665545557777554556556755555676566677
45557644565567765544567777654446645767766565556675
55456655566668865554454555554457765677754465555566
54544554446668854564344554556566765567543444454465
54655554446666744555344444566677765556553455445565
65666555556655656655555445665678755667554445654567
76676566655444567666544566677656665456666678764357
87576566765445677555533477776434555566666678874458
87676566756556766555544577775445655665666667766558
77787545556667656666776688754455655566555676566557
56777655555556566677877677545555545554446677677665
55445544564555676587875555456544657664356766787544
Capacity C = 10
Number of items N = 250
" | |
|
| 4) | |
| | | Returns:
"seed = 5
Size of terrain S = 39
Number of terrain types T = 5
Terrain:
033321132200302103230020322313012323222
020113221221113010133103303300301222203
112012102330322321330032100103312000000
131021233011102100133101322321120110203
310012201001012202322120330032011231132
122003201200123110332322130100311410210
322331310111332110020200332313011003312
302330230123012331100133123000023003111
332020001312330030133220311122222021331
212020101020221101130032300330301010011
123330022322211011301323220202302113221
210312203222010322301223331032003033132
323010213113032203220100032002102320231
010030123023212322300231032011012102220
223313033101030000322212100000303122103
112220203010202203131102232331310210213
023033100113233330323303221322323323221
311203133300023121210321012102212021132
031003331131213023033230003122313121101
210322001222330203033332330013030022202
132310022132202311200032022101002123001
011120113322130113112112222300321102333
031023332122023320103020332001012130121
311003103333332113131010201013023302301
223031000110023120013311030330322013200
031200022221320122133332100313112133322
022313332121133102010302222322132032330
201232330322302330233021021133112210211
110221131322100333020020310303323021111
022221322232202210103113222231021013032
232230301020300130200023201131210030203
312010231023223123311333223030223003200
232101201231132130131032332231013223023
132200133013320201020030002232000220002
221033032133310033101023210113313103203
000330200112102033201101002330013100211
000213013333103232201330023033301212220
310310010212232321212222223032102001210
333113101202130222332130310033003321312
Capacity C = 8
Number of items N = 30
" | |
|
| 5) | |
| | | Returns:
"seed = 6
Size of terrain S = 43
Number of terrain types T = 5
Terrain:
1111123332223322222223322222333322122323322
2222233322232222112233322222332222122232322
2222233222222222122233322221222222122222222
2233222222222233222333321221122222223322222
2233222222122332223333321221112222123322222
3332221122222332223333321222122222222222233
3332222222222222233333222232122332222212233
3332332233333333333322222333223333222211223
3322333333333333322222223333223233222211233
2222233233233223322222222332222223232222233
2122222222222223322232222233222333222222222
2222222121122223333233222222222232222222222
2233222222222222322233222222222222222222222
2233222222222222222232223322222222223222222
1223222233222222222222223333332222222221232
2222222233222221122222222333332222223221232
3222222233322221222222222333322222233321122
2222221223322332112222233333321122333332222
3222221233222332112222222333332222323332111
3322222223222333112222223333332222222221111
2232211222222222223333223333333222332222112
3332111122322211123222222333333322333333222
3332111222222222122122222222333322333333322
3322111222322222122123222223322322323333333
3332212222322222222223332222222222222232222
2222222223322222222223432222223322222222222
2222222222222333222223332222223322232223332
2122211222222333222223332223222333332233333
1233322222233233222223332233222223322222332
2233222233333333222223333332222233222323332
2333222333333332222223333322222233222222332
2222222233333323333222232222222233221112221
1221121123333323333212222222223322221111222
3221122222222222333322222222223322222221122
3222222222333322233322122222122333222222122
2233221222222322222332223333212332212222222
2333222322222222212232222233223333212222232
2222232222122322321222221122233332212222223
2222332112223333322233222222233332222332222
2222332112112222333333332222223332222332212
2233322112111223333333332222222222223322212
2233222112222223233332223222222222222322222
2222322123222222222222322221123332212212231
Capacity C = 6
Number of items N = 7
" | |
|
| 6) | |
| | | Returns:
"seed = 7
Size of terrain S = 14
Number of terrain types T = 10
Terrain:
55434665556756
45655654566778
46666654565788
56655676665687
55554676566676
56666765566677
66767766677677
45777765565556
33577754544666
43578865556777
43567775557876
45556764568975
66556775468887
44656866467786
Capacity C = 7
Number of items N = 11
" | |
|
| 7) | |
| | | Returns:
"seed = 8
Size of terrain S = 27
Number of terrain types T = 8
Terrain:
344544534343556455434445445
554544555455555555545544444
555545544455555556545433343
333434445544555666444433344
222334455434456765445544334
233444455333346643345554334
444455454224456544444544323
434455444334565455554555444
444544344444554345555544445
334444455555443344445434444
433344455544443343345445543
543344544433333444344445655
554455545434445544445445665
555545445455556655555334455
444444456665445655554334444
554344445665333566664344456
553333334555333344554333454
343334444433443344444443345
233345444334443444344443344
433445544444555443454343345
444345444334565544554343334
654344434323455655543343322
555444344333555666533344323
554332345534445455443344432
333333345544445445543333543
434444444334555545544434554
443434444233556545534444554
Capacity C = 9
Number of items N = 42
" | |
|
| 8) | |
| | | Returns:
"seed = 9
Size of terrain S = 30
Number of terrain types T = 8
Terrain:
333453544556643543444432333455
333443443467654544344444444444
544443333466654444444445544444
544444333455534444445455544444
554555444445444555444445545444
654555533455555565454335555445
543444543455555554444434555445
333333444444444433334544555555
433333444444444333333444665565
544434434455544334323334565555
534434334445445444333344455445
333344333455445554334455444445
233455444444445565444555443333
345555554333434565433445544455
555555554344444443333445555545
654445565444344432233444555544
555444455444344443344333434545
334433444544345444455432234443
334444544554566545543323344333
344544444543466555654444444444
434665333443466546654544555445
545666543455445445654544544333
345655443444433445655554534333
455543334443333455545544434444
554444434333444444554444433343
333455444434443333444444433344
334454433344443333456544545444
333454433454344444456555544433
443454332343334444566656543334
444553332233444444455665444222
Capacity C = 3
Number of items N = 70
" | |
|
| 9) | |
| | | Returns:
"seed = 10
Size of terrain S = 25
Number of terrain types T = 6
Terrain:
2112342323421343321113211
3123332222321232222232221
1343211223432333332233311
2333321233321332112233323
2123331322222322224344333
3232331232112322224343223
3332322134224343234443211
2223343234234333112233233
2222243324333322322321232
2221133323333443432432132
2233222222223322333433232
1222223233212211232222133
3311222233322322322221222
3211222232211333332123333
3232312223312123332123433
5332322222311232323233322
4333322122312332223232233
4441112232322331122332343
3432332232232431222122244
4423342232132322222122222
4432344212232223332122122
2333333312221112243223232
1322322323222133333323432
2333222233222213332223431
2132221223312222222113231
Capacity C = 2
Number of items N = 37
" | |
|
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.