Problem Statement |
| | You are given an S x S chessboard. In each cell of the board there is a number from 0 to 8, inclusive. Place several chess knights on the board so that the number of knights which attack each cell is as close to the number written in this cell as possible.
Implementation
Your code should implement a single method placeKnights(String[] board). board[i][j] gives the number written in the cell in row i and column j.
The method should return a String[] describing the placement of the knights on the board. It should consist of S strings, each of length S. j-th character of i-th string should be 'K' if you placed a knight in the cell in row i and column j, and '.' otherwise. You can place as many knights as you want.
Scoring
Your score for an individual test case will be the sum of absolute values of (number written on the cell - actual number of knights attacking the cell) over all cells of the board. If your return has invalid format (wrong dimensions, invalid characters in it etc.), your score for that test case will be -1.
Your overall score will be calculated in the following way: for each test case where your score is not -1, you get 1 point for each competitor you beat on this test case (i.e., your score on a test case is less than this competitor's score) and 0.5 points for each competitor you tie with (a tie with yourself is not counted); finally, the sum of points is divided by (the number of competitors - 1), then multiplied by 1000000 and divided by the number of 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.
Test Case Generation
Each test case is generated as follows. The size of the board S is chosen between 50 and 500, inclusive. A knight is placed in each cell independently with certain probability. Then for each cell the number of knights attacking this cells is calculated. Finally, the resulting numbers are modified: some of them are increased or decreased by a random value, and some are replaced completely. Here, for example, is the original knights placement used for generating test case 0 and the resulting board.
For the details of test case generation, see visualizer source code. |
| |
Definition |
| | | Class: | KnightsAttacks | | Method: | placeKnights | | Parameters: | String[] | | Returns: | String[] | | Method signature: | String[] placeKnights(String[] board) | | (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. There will be 1000 test cases in the final testing. |
| - | The match is rated. |
| - | There are prizes for top 3 finishers among attendees of Warsaw regional event and top 3 finishers among virtual participants. See the rules for details. |
| |
Examples |
| 0) | |
| | | Returns:
"seed = 1
S = 6
Probability of knight in a cell = 0.7213811087518659
Probability of a cell changing = 0.44548965891309267
Max change value = 3
Number of cells changing completely randomly = 2
014121
233331
343422
268540
107443
132224
" | |
|
| 1) | |
| | | Returns:
"seed = 2
S = 50
Probability of knight in a cell = 0.6245114806367582
Probability of a cell changing = 0.11624841423653401
Max change value = 3
Number of cells changing completely randomly = 44
11222331423342342443324233122113132222212322415321
32444374454424442555355442544352233323244341545222
24566443854665764576675565554455452363474735473740
23664656664754836566377454343243552586335444765333
44565765353674664667525647363424463674453516463520
44765566735763444564666433354573515554547571747242
36657743656834466665662624625245874665474626365523
25676543652655736677667575653545527784545323707453
56546642243653655527665565755646783866363427254704
43676753836458551633468634451776645874657444454633
45766452545644456565765646545655863565277546555542
24473434466545735647875766766765845633476644664244
44364635266777634465655476065465363677464764737352
13554653236336653444653664426564562654457575583634
31625344256455526663854544674545551365646376585450
34543335564644625543575565644462154666775653563424
35666235236545246635454653783343424375652755426732
12425556645556432647444657744872466747154633675353
32566537656764343346543743563444344565836453463301
25667475684665726350537364744323051667364712664353
23347545576765535334435667676654257374736354663854
33544557663625443516465554764756554555444731555453
34366754787466638457552847364653655564765365535652
25554646265626646545726576655547573257354857466543
15647461555576767555755547166463646347654455416331
44745566356745575807767571344326653561366768245713
44665545657676537575754576444065356436666356656543
25754647557774565755564675566437434554466787535442
26556465644866736372855535346343434544464465654533
33836454755565572646655665275436666574666646528362
24744566577654664585637684665454554544450456475824
54365737585747454738365665746427453557254457727422
23763477446654635366485866767565656437458645463732
42556665457654444356566767585356455565464846687450
15636277337354474446346665474455546355726355677733
35457566538630567254647475867466146552454556868461
37675778651366363457446476465556544455436485765753
34556666515663646357665636044862557682282638576632
25655457574656564788463744662536562566474463746853
32755765665163746562647455565767455532551447468752
33445553664726655666576550545557553735334265846653
33346555556567852655856566443362567444646646866552
25564644574633642456283747755455655556354545667643
44536545764645053762646364234735685152515536475353
25476554567553746355277453534464464557365556565833
65635664553675251433466465455634764376644875556461
37773674565162545353565544644363465645355455464642
45765786664865164477445543342532563265424452746542
22444353555352435333357253313433543432323333552532
53341333232442261133232211210430033243223341323221
" | |
|
| 2) | |
| | | Returns:
"seed = 3
S = 500
Probability of knight in a cell = 0.3318470373115917
Probability of a cell changing = 0.42601570814050416
Max change value = 1
Number of cells changing completely randomly = 402
" | |
|
| 3) | |
| | | Returns:
"seed = 4
S = 102
Probability of knight in a cell = 0.44993285147972173
Probability of a cell changing = 0.40031477561975526
Max change value = 1
Number of cells changing completely randomly = 73
" | |
|
| 4) | |
| | | Returns:
"seed = 5
S = 120
Probability of knight in a cell = 0.11441631375072739
Probability of a cell changing = 0.4888170230214912
Max change value = 1
Number of cells changing completely randomly = 115
" | |
|
| 5) | |
| | | Returns:
"seed = 6
S = 411
Probability of knight in a cell = 0.25588523887612513
Probability of a cell changing = 0.12398752173001011
Max change value = 1
Number of cells changing completely randomly = 97
" | |
|
| 6) | |
| | | Returns:
"seed = 7
S = 218
Probability of knight in a cell = 0.7965925968388816
Probability of a cell changing = 0.29172725412449896
Max change value = 3
Number of cells changing completely randomly = 138
" | |
|
| 7) | |
| | | Returns:
"seed = 8
S = 354
Probability of knight in a cell = 0.584144002270863
Probability of a cell changing = 0.41346774225508465
Max change value = 2
Number of cells changing completely randomly = 46
" | |
|
| 8) | |
| | | Returns:
"seed = 9
S = 357
Probability of knight in a cell = 0.21383164920805495
Probability of a cell changing = 0.4030347221427665
Max change value = 1
Number of cells changing completely randomly = 285
" | |
|
| 9) | |
| | | Returns:
"seed = 10
S = 270
Probability of knight in a cell = 0.14285483385807077
Probability of a cell changing = 0.42990797074348197
Max change value = 1
Number of cells changing completely randomly = 160
" | |
|
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.