Problem Statement |
| | Paint cells of an H-by-W grid of numbers, such that every
h-by-w subgrid contains at least Kmin and at most Kmax painted cells. A
painted cell in row r and column c earns you grid[r][c] number of points. Your task is to
maximize the total number of points for a given grid.
Below is a solution for example 0 (seed=1) with H=8, W=8, h=3, w=4, Kmin=0 and Kmax=5. The
painted cells are shown in blue. Note that each 3-by-4 subgrid contains at most Kmax=5 painted
cells. The raw score for this solution is 125.
Implementation
Your code should implement a single method
findSolution(int H, int W, int h, int w, int Kmin, int Kmax, String[] grid).
The method should return a String[] containing your output grid containing H
elements of length W each. The i-th character of element k corresponds to the grid cell in
row k and column i. Each character of the output grid should be either 'x' (painted cell) or '.'
(unpainted cell).
Scoring
Your raw score for a test case is the total number of points of painted cells ('x'). If your
return was invalid (incorrect number of elements, illegal characters used, a subgrid containing less
than Kmin or more than Kmax painted cells), then your raw score on this test case will
be -1.
Your normalized score for each test case (except the ones on which your raw score was -1) is
YOUR / MAX, where YOUR is your raw score, and MAX is the largest raw score currently obtained on
this test case (considering only the last submission from each competitor). Finally, the sum of all
your normalized test scores is multiplied by 1,000,000 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.
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 2000 test cases in the final testing.
- The match is rated.
Constraints
- H is the height of the grid. It will be chosen randomly between 5 and 50.
- W is the width of the grid. It will be chosen randomly between 5 and 50.
- h is the height of each subgrid. It will be chosen randomly between 2 and (H-1).
- w is the width of each subgrid. It will be chosen randomly between 2 and (W-1).
- Kmax is the maximum number of painted cells that each subgrid is allowed to contain. It will be chosen randomly between 1 and (h*w-1).
- Kmin is the minimum number of painted cells that each subgrid is allowed to contain. It will be chosen randomly between 0 and (Kmax-1).
- grid is the H-by-W grid of numbers represented as a String[] containing H elements of length W each. The i-th character of element k corresponds to the number in row k and column i. Each number will be chosen randomly between 0 and 9.
- (All generated values are chosen uniformly at random.)
|
| |
Definition |
| | | Class: | PointsOnGrid | | Method: | findSolution | | Parameters: | int, int, int, int, int, int, String[] | | Returns: | String[] | | Method signature: | String[] findSolution(int H, int W, int h, int w, int Kmin, int Kmax, String[] grid) | | (be sure your method is public) |
|
| |
|
| |
Examples |
| 0) | |
| | | Returns:
"seed = 1
H = 8, W = 8, h = 3, w = 4, Kmin = 0, Kmax = 5
60856174
75928915
89719086
16627659
32982909
13815950
55717858
91260290
" | |
|
| 1) | |
| | | Returns:
"seed = 2
H = 22, W = 33, h = 13, w = 9, Kmin = 55, Kmax = 61
468459076060978557166072240289000
946779048318924409987128989678137
709018324104969266866513417367362
135740377191947836724494768732051
469817173111465936082041421188670
970220027957680836294892613976477
946878632989704700204095773454334
253265579195169246863323676645981
718296968437668894764955843741491
323514225551994805972366643994406
224878346638603902325363349739790
863809067167524915128999000491905
562358155559765816575514675584134
935398692635558145586778875439435
100397774814610454692017313005515
166432729007631170955802073796557
970851345961022670273171497268811
692256831209416988073185943929291
297234808243762165695615490334474
033685710325506785062396460700452
833161206988682774465864952182599
362345907615714077184556963251338
" | |
|
| 2) | |
| | | Returns:
"seed = 3
H = 24, W = 49, h = 14, w = 42, Kmin = 210, Kmax = 332
2113640049290018425929623105271770055406654520442
3174589277432615704375224236571021301427013801121
6414838857672695672613592820611873674232271788402
5509117934792926959917485299516236940433418682164
7650622227779920313581757218023429545664435247111
0905233216048796612118489416078775237490045887365
7117209150427664178506170783326254587873246638448
0925281307731895307499226324418478225115823363705
9013534433201214783377918379728524677418197068739
3141165231809693918573627037791262172948080503668
3520693551161858637593179579951098511870876210378
3032828803107382698300854972290782759497445950545
2228829657355489628125802459366569818058705202530
8787556552892560543255451638791141057547831061928
6126074408520984668264761613458610704996711103381
1793578275032900426918857901021305310038977607180
9614824076863551867897419304908377582435812669563
4882182735841315994657568930393307489112973572587
5550126836018098376050323800681623738316115917238
3570666791112665311371495150005884576961765038514
0798994480399010987640618884053357752247115434492
9663774980599544676323817529141165716060885162940
1932519276655488941102983279121823940716245710992
6647721731790857942447224418233589433101750331730
" | |
|
| 3) | |
| | | Returns:
"seed = 4
H = 26, W = 19, h = 3, w = 3, Kmin = 0, Kmax = 5
5638067933468291081
9111396943185190951
0846723801690235984
4832887130587801759
8135546487251008966
2864965273538711032
5348977730867414221
8564976813528223829
4981006590062398342
7791819872575149991
6021146374199119147
4913502481032495346
6687155634127489579
7842455388436433254
5970501141150550251
5803243824131564546
5710204519575210976
2734410169014707414
3909006194346261465
1291304590453235286
8485800522097976287
5789853320358964218
7307291300280915676
1271523185664870551
5423400237302743925
7694956005485092647
" | |
|
| 4) | |
| | | Returns:
"seed = 5
H = 25, W = 20, h = 12, w = 7, Kmin = 24, Kmax = 61
52006564852856808853
37996205647269484171
38538179755920669710
81746165871379994887
28370480470479889556
57613678601844436556
56366594417862971117
06078743163901985959
06023508831993834737
87798050948963242440
56648038290800826752
31626201338048348862
79374684817504874050
41553664433353903957
44508701575905355987
18075076552972293684
67477765758284438701
25291006305158551920
00252717376508511703
30121382751897153473
73024621186703200965
65878744671004565289
99892527694636185599
66170355034462338977
67124133886860393370
" | |
|
| 5) | |
| | | Returns:
"seed = 6
H = 39, W = 10, h = 31, w = 2, Kmin = 7, Kmax = 43
4262072355
3811107896
4405315071
9004925617
7004585528
7299593191
9197538512
4598216281
5093224959
8231642878
0514964549
8915673978
4735333645
1652930906
6169682181
7155038097
4011035070
6827108771
8919543832
8332103538
3384091497
2982059974
7212565607
0878318066
6013234595
9756307224
4049497996
3251826023
9961211836
9170315383
7905693870
3631985043
0300170495
5142696532
9591584943
8330482616
7987551263
8292906669
5947877906
" | |
|
| 6) | |
| | | Returns:
"seed = 7
H = 19, W = 19, h = 14, w = 16, Kmin = 110, Kmax = 201
0600295375950991849
4549486262712635697
4643760045888489214
6892988117858525539
9975437107023304051
5978625554229600777
7928752265374865539
4000971710572799563
8417920431233303759
1488855613328416880
8178743918246024526
2016716428910731605
9302506988286710561
1329512058468807504
9329009734207727136
7461311604823422062
3280534650460185247
5469679499628694824
2791248306383106950
" | |
|
| 7) | |
| | | Returns:
"seed = 8
H = 16, W = 33, h = 5, w = 11, Kmin = 7, Kmax = 14
480344279549980812135547108046189
800445004121832103135234565166653
983109318370686804734738464381866
244114678643490015365410574039692
331807154530181988507465839325891
722074168632829851230564179902002
152594710294394687488893212709293
457495891611690503049265270027416
070551972722524009444075702767129
615458308653247906969025875725402
782428599534386649265684179583140
353829124662107384070622813745832
948435868797980063824126011479371
981525397334163298757744813065285
764863792214877820869523344454169
789865766668485852278285336578303
" | |
|
| 8) | |
| | | Returns:
"seed = 9
H = 45, W = 34, h = 24, w = 26, Kmin = 279, Kmax = 423
9662213425267880123417666559204537
4161658629849653832889134995231219
4703742734415484883070172877611310
4967677246439113767776623225478885
8034255759054135119506314749566194
0182966702822966851901278995731344
8234757316302959676577346010484150
2896216215916043687725644770390427
5078372683392430268749069289714421
3406122279721084467800782750346544
6430088724333767951371216100533778
6253112231139643103499365775002532
8569773908826382876616204868812416
8673389587397644565037477413969300
9331188252708956357397355737218626
0670932709358296022128034029285205
9702460945250364949431340019294335
4019632779818237644882579690858219
2985048571314707312272839296333915
5492962750033853565859874069805312
2704693072819911976657101816576502
4870977673720718770119444487837527
6212720275673679835300050469826211
5247248885844426848494024325230084
3754193015923413259331419827114344
0561795505716039203383283607716906
5703499551814615120819285129225459
0451361699634822336608791602176011
8797873312031646102091432257061929
3426027139932033654322975652507406
1330719404309687437251305941647084
6224576618074939799460622160774711
0823990678278717983581207842955852
6106486017365355984006936445221279
6911579648561060687982572749448125
0034887400837914236945326726639454
5648339987723205154714108128359407
2829587240126651858773079672392260
6687615857125720106855025060638424
2477387506133281138694825937989956
7681204849681540989133160719683787
0551790164253955465647738398316871
0550252551243842663323685189511438
7569517705897244222508638490620548
3556441733866708644571154989817200
" | |
|
| 9) | |
| | | Returns:
"seed = 10
H = 18, W = 13, h = 2, w = 7, Kmin = 2, Kmax = 11
0394865898218
0157800550045
4489485252519
4050211933712
9491777405014
2402763685859
3486154934543
6640601938697
3836135332254
9279946965924
1501365751585
3073066776254
8167544160449
2304915200800
4085421283533
2659177826540
6980275223993
0108233955278
" | |
|
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.