Problem Statement |
| | A pattern is created by filling cells on a square grid with digits. A freshly filled cell gets a value of 1, and the four cells adjacent to it (vertically or horizontally) get +1 to their values if they are already filled. Thus filling the same cells in different order creates different patterns of values.
You are given a String[] targetPattern that you want to create. targetPattern[i][j] will be '.' for cells which can't be filled, and digits '1'..'5' for cells which should have a value in them.
Your task is to return the sequence of cells to fill in order, so that the resulting pattern is as close to targetPattern as possible. The "distance" between patterns is defined as the sum of absolute values of differences between values in the same cells. Elements 2*i and 2*i+1 of your return represent row and column of the cell that should be filled i-th. All cells in your return must be distinct. You can fill only the cells of the pattern marked with '1'..'5', and you must fill all of them. Thus the number of elements in your return should equal 2*(number of '1'..'5' cells in targetPattern).
Your score for a test case will be the "distance" between targetPattern and the pattern obtained by filling cells in order of your return, increased by 1. Your overall score will be calculated as follows: for each test case 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) 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). Invalid returns are given score of 0.
The test cases are generated as follows. The number of columns W and rows H in targetPattern will be chosen between 10 and 100, inclusive. Then, between 10 and 30 random diamonds of '?' characters are placed on the grid. A diamond with radius w0 centered at (i0, j0) is a group of cells (i0+i, j0+j) for abs(i)+abs(j)<w0. A diamond can be partially outside of the grid. Finally, all '?' characters are replaced with '1'-'5' characters in one of the following ways (chosen randomly with equal probabilities): either all cells are given random values, or they are filled using the same process as used in your return, with cells filled in random order.
A visualization tool is provided for offline testing. It also allows manual play. |
| |
Definition |
| | | Class: | DigitsPattern | | Method: | recreate | | Parameters: | String[] | | Returns: | int[] | | Method signature: | int[] recreate(String[] targetPattern) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | The memory limit is 1024 MB and the time limit is 10 seconds per test case (which includes only time spent in your code). There is no explicit code size limit. |
| - | There are 10 example test cases and 100 full submission test cases. |
| |
Examples |
| 0) | |
| | | Returns:
"seed = 1
H = 10
W = 10
targetPattern =
.232.24313
.134123332
..1..31513
.2....413.
222..23251
1351251413
4335422352
1414233414
4251243..1
212332....
" | |
|
| 1) | |
| | | Returns:
"seed = 2
H = 50
W = 23
targetPattern =
.......................
......................4
.....................51
....................115
...................5233
..................51544
...................2453
.5..................515
543....2.............34
5452..342.............4
331..51244.........3...
.5....215....5.........
.......2....532........
.............2.........
.......................
..4....................
.......................
.......................
.......................
.......................
.......................
.......................
.......................
.......................
.......................
.......................
.......................
.......................
.......................
.......................
.......................
.......................
.......................
.......................
.......................
.......................
....2..................
...212.................
..45234................
.2342324...............
135143325....2...5.....
5344233555..532........
434311252.542323.......
.4222521.54214315......
..25322.4423153133.....
...113...35132414......
....4.....235545.......
............322........
.............4.........
.......................
" | |
|
| 2) | |
| | | Returns:
"seed = 3
H = 29
W = 99
targetPattern =
.213...............2412533......124412232252544......4413233251233224....15343..1222434............
..2...............353433323......4451311152235......4535353251552354....1355122342551544...........
.................52424322532......11233333335........5314241..42313....324134535151225541..........
..................353222151........134432215..........43522....232....24545522134331343551.........
...................1514434..........2132233............152......1....1533225234112231344432........
....................3.151.........4..34343..............5...........2244554153134241334245.........
.......................1..............413..........................5553324355245343312214..........
...3...................................4............................42431151241455443123...........
..253...............4................................................443352443533413523............
.35242.............531................................................2434542522213424.............
1525452...........41342................................................331433523..232..............
33554141.........1142244................................................1312541....1...............
222241424.......315423513................................................55121.....................
5412243143.......2321434....................................4.............143......................
43441421344.......32544...................1................141.............5.......................
533351343315.....5535515............11...151..............33344....................................
35213411545.......23423.............141...3..............5154221...................................
2542411431.........131.............31414................343112113....................4.............
531211543...........1...............151................22443522521..1...............315............
34421225.............................3..................422321355..141.............31545...........
2243253..................................................2222451..42213...........1555232..........
.22144....................................................42235..4134331........1435115325.........
..244......1...............................................351..213241142......1144533213..........
...2......415...............................................2..25435132424....1124234535...........
.........25415..............5...................................144331435....4142322512............
..........454....................................................4324334....1452421555.............
...........2.............................1........................31245......4145441...............
........................................354........................522........35341................
.........................................3..........................3..........143.................
" | |
|
| 3) | |
| | | Returns:
"seed = 4
H = 83
W = 52
targetPattern =
............................................14212...
.............................................143....
..............................................1.....
....................................................
....................................................
....................................................
....................................................
......................................1.............
.....................................223............
....................................25423...........
...................................3242133..........
..................................141254123.........
.......................2.........33334313521........
......................213.......2152151351441.......
.....................15412.....135152435235252......
..............1.......223.....32525151241431423.....
.............233.......1.....2143225325151542221....
............21521...........145151513343141235343...
...........1344423.....2...15214144415242533512413..
..........225131523...123.1513542431341531432541413.
.........25242442412.1352151353151235151435221254412
........12351351314523532442531342352514513432513143
....2..235125415333251315315324522513152322534244514
...2142141541431415142543152123335135413534253223351
..25233525135153451515131415333153242151253133151232
.212451352431521315141532523515413242513442414522344
2435215321245245432353354141252144354152431541245422
151233235423321425144221423451454312251421513452122.
23235443224134513341342422334341413532452515132443..
4435314324524323142351352452242432515122424145123...
3241352123235244251422532334141533141524525422351...
22241425414531425153542253145143152541522141441251..
313541531324135125131342232422515143332444254235133.
4253152152523425413451543241531335152251521421414521
15225154243422341351253141.2235432525134153134351424
2352353322525153351453323...243221341542515335135252
424124131331441413532414...1542543124142241251512313
123452443353223151412333..14231232435432543243133452
2513413515152423351525131..2514434142131325315245142
43331513524435252251514531..223451535253523443312512
322351514132315242151431441..31244314234212521535152
214324132531451245315413525325331325252253515231242.
424515245335223432531435313312.3441413514133233531..
251432413312452235252424135133..1351324415431351541.
2222515225351325241251313522452..1434322531425144142
25431514512345131235145431541341..315413432522531341
4124515142423145434224225231413232324235214134314453
2351331515432412425432421443535253152151524454151313
3143532241351525133151532251222515243415242212434423
4313153453223352351515253425335153225141523543134251
1524321243315131532334132514152512452335214124514142
4145323525424235224152251442521435321533244542245324
2413534134151352415224415132134124143251413344123512
1441415223224522352245141445345341..321453214244123.
342515143535231343351344231314151....2521532321542..
15135225213135252514421525335251......15325244512...
2432243143542242343415314215312........214142423....
414415435142154214133133525213..........2535231.....
13522331251533134134534424152............22213......
3524453332524133.25142151441..............252.......
141242144131442...141341513................1........
41541541425251.....2525413..............1...........
2431532345252.......15213..............151..........
3214131514141........152..............25143.........
43254251514133........1..............3124123........
152423252235412.....................124244522.......
32525412435142.....................33325222512......
.131414542142.....................3145424151452.....
..3415131431.....................215243254252212....
...151..252.......................3221313212542.....
....1....1.........................33242543512......
....................................324521313.......
.....................................3124433........
......................................24521.........
.......................................222..........
........................................2...........
....................................................
....................................................
....................................................
....................................................
....................................................
....................................................
....................................................
" | |
|
| 4) | |
| | | Returns:
"seed = 5
H = 59
W = 83
targetPattern =
..........................22214324355....5544334431541531535445112.................
.........................1322423421245..554211212422155523423532223................
........................12134354224512541515121341144425544453434335...............
.......................4111554524353551122541443514114323134223231244..............
......................415445442335435245423115435111521142255444145145.............
.....................13551143121315114115432413113211353335424523533321............
..................3.14345544312313521124112141125311131332343211412231.4...........
.................412.324433124532145343413523224231431152121434355232.115..........
................12134.5554531332552422411552223141114552344453323235.24444.........
...............2421454.43141224152435113413141352353333214451523144.1341254........
..............425355444.221153431321134311145513341443224133155551.152421213.......
.............32551231524.3322435451354442412244511351533213455213.31155321432......
............3244551235443.35254552314211151453411552314313124231.3511544453524.....
...........112422122351154.222124553255342342542333555422215252...44214143415......
............34133553535434..5322344125134212522253515424223443.....123422344.......
.............22124314411121..4254212345332443533213212323245514.....5432451........
..............34412225323142..155.123553431331513454224334552315.....15554.........
..............112413514535114..4...423253414334241324551355435552.....132..........
...............4325321234145........5543214435243345235331543134.......2...........
................41343245153..........445455152344225231151555151...................
.................454512513............111444252541541212534551543..................
..................4122522..............134533535534221232425453454.4...............
...................41222................44533433413553144242241525533..............
....................341..................12221111244335245215524322514.............
.....................2.....................4314453444153141125522253555............
............................................5212335354133254131452235555...........
.............................................5232154544244352432411311345..........
..............................................5125214355414523254541534224.........
...............................................3..2344233515225414134352223........
...................................................4515313141323331125211554.......
....................................................4345331244135133443515444......
.....................................................4252524133325351424422412.....
......................................5...............2523541531345315251441331....
.....................................442...............4245553353535122513315553...
......................................5...............515354213412352133412255441..
.......................................................4345335431251214533335241...
........................................................22125314325532325321521....
............4............................................325325125411131252213.....
...........415............................................1214524343354522511......
..........13315............................................54345515522441122.......
.........2211532...1....................2...................423234115522242........
........554135553.354..................551...................5411335152341.........
.........3415155.21533................41543...................33555552145..........
..........54423.3524242..............5235324...................513222553...........
...........313.425243525............544521244...................3515121............
............3.22554351551..........52132241531...................22253.............
.............3125534113412........3315432325413...................252..............
..............55122543214..........25212534243.....................1...............
...............215423542............413455144......................................
................3513141..............5111211.......................................
.................11215................43213........................................
........3.........113..................124.........................................
.......411.........2....................5..........................................
......24355...................................4....................................
.....3454221.................................334...................................
......14533.................................44425..................................
.......245...................................312...................................
........1.....................................5....................................
...................................................................................
" | |
|
| 5) | |
| | | Returns:
"seed = 6
H = 36
W = 34
targetPattern =
........154342253434112552515545..
.......21234534534144425122135415.
......1222252432423211144153512214
.....11312433214332452515444344432
....141444445152553354311553533231
..21213143442412221243451515312413
.335515555355243124321345522322442
5231421444351125443142425411541411
.23155112532521435.152145554444154
.32..2235431123244..35351222515534
335...1212554432552..2521142515333
1343..12223334535251..45341423555.
53124334131244234412543312125124..
3122125134141252143543521341512...
31444313114254134112325531245222..
232523113533133235214211553211545.
5245225552515152345241451423342121
5125512551323442541514251255215455
1132122223443322344354112452324223
2323514222541541154554235522545315
3451453234432221511145125111551243
1124115513242343211354152133214251
2321352441542253143444351434534251
5252441143534353241421451435124551
.543225425353142111314532335515515
..31321342123135323343314514315313
.544151433415511255224143442323433
.445253121341344133332442211155231
4512431451241324423351351442333241
.151312231525453121522242341553413
..2512331114332133135253.351542212
...3152523343255451534415.12122555
....5132341155343242311415.3521432
.....1221143225533311422131.121445
3.....5111443254514521522442.25325
.......22535242252442141423...3235
" | |
|
| 6) | |
| | | Returns:
"seed = 7
H = 54
W = 98
targetPattern =
...................1455531543213134415112153423111533521133335343...13321435421145511153232113....
..................335512445235315423444143152544411224434522441423.4354524352135132312232253452...
.................1342211541311254434232112224351231145244131155435115345313333242352242221543453..
................312343411452115212413531525235555234255435335235441244421251135333545511521444252.
...............12534141522355314144352132434255311113534452122444.34324151321445132421332242411423
................331345232411351534455513314531114352443151243445...551522255454541331352455222243.
.................2453541334313351553324314513142121335142241345.....411434345213444354513215252241
..................24155344214155344243445321335244431441455155.......22321155423243311434243313351
...................422541352112554214431535545334311322322555.........232335354352552..35245152434
....................1455114225343143252521115345312355432243...........1153151145414....2413223244
.....................33144125142333145422121414251233133544.............3213433115513....541353351
..1...................234554142543242131152341232323531422.............443531515154453..4154351325
.512...................2512512551523135244..5431334414235.............1321224325211211122441342531
33322...................41553223234454542..4411513335213.............11111312242145211242232544214
535522...................233533541341532..5114515235345.............523313211123145212144234134352
2235211...................2211133325314..4323431245511.............5322531311443451353551154533423
54115451...................43133155112..154321433124533.............342125254345113125554..2545312
332511334...................3233413321.32321231532223145.............5553125213451444352....113141
1242554235...................5324114553321442323533234533............325112235321154211....5133345
12153134515...................4523522124421233512153522141..........352445544455455421....44142411
415134111115...................2312115545224515324134533152........114425214311124132....244513123
2542553324534..................114533143425352243214123432........154342232412342343....2344255111
55433233421542................145254554223554523134515324........215215553414333121....31435223253
135343352225311..............254153324231415322215114115........432353121214122544....444552135535
3522231515255223.......2....214554121125445351514152552........521232232123114323....5231454121512
13354342451251145.....151....1235235342111313341221345........414455543331431111....33542414535224
125452235123454113...33125....31334524434151325512343........121232541512412454....311435411511141
2511512334442222424.3415214....15443414415.241122433........1511532424142533342...4331132235541211
142512223451254522...25235......243554313...3335154........432152434423531212332.43545552523115352
55434241421435424.....252......4.4242343.....24531........5341531314211354531315233541451211553123
4344521514512442.......2......521.32323.......233........55312152531454355211121131454532552342312
212333253441425..............42535.535.........3........541331414124521231435541234113551324545333
53541345541354..............3453153.4..................4243252441215412113153431425422544425541122
1533435322154..............321311123....................514231545251551413313252532445512355412422
434435335523.4............45524341412....................4231341545133224533351351.121345213432434
54223123541.114..........2524324244415....................3445444441453554414235232542221545345541
5111315551.54551........551151314122545....................452432354452253523213544534311232225255
553245254.1323123......45442551321335353....................32544435141121453532211541225544143222
122412421135532251......525121244314254......................1153555131243544111335244424224421231
2342441522213342234......4115242344313........................45353535245521451352322431423152535.
33411444153553151443......12225153454..........................531553444215443253223133335122532..
254141142234352252315......255423351............................2434512535244323153312435144453...
3313323455442544235421......1431352..............................5221155531141344155542245.555....
14512511433325521213335......21244................................43534153325212214234532...5.....
541233545213211532543414......151..................................242343211125335234214..........
2253155443125235542525112......2....................................2413444145224132244...........
.5523455522122244223444453...........................................1.153125334231433............
..44213231345222123513215...............................................2114113455255.............
...431313151132213122321.................................................21141251332..............
....3234355513242312353...................................................432223233...............
.....44334325445234325..............5......................................2125124................
......125543442545134.......................................................13443.................
.......5342153232115.........................................................551..................
........25233415233...........................................................3...................
" | |
|
| 7) | |
| | | Returns:
"seed = 8
H = 30
W = 49
targetPattern =
........2.212324141.....24123........221423412242
.......3123435123433...3215413......1544141235313
......142541515334322.315312413......221525442541
.....141441425134221513515353431......33312432343
....33351251524154331512332325243......4145321422
...2315325223514325424234521441421..1.32233154124
....15333154232421333354134513313..14424515412541
....2431531415245314143151234532..232224252145313
...1522514525251245443151453123..1445142135314153
....15143331223541322341432152..25221534523342522
.....144151533241441351342522..223435214313451251
....14215141515141..313..142..1513521542141243514
.....34313..15252....2....1.314252154124534513341
......133..1.222......1....1345135421452213151513
.......2..252.1......322..33133413435213425243353
.........14131......12452125315251423523451531322
........3324532....135143252442235221443135124313
........252212....1351514421344213534425241534453
.......22154423..24524245243351442322321.24231323
........3532252432141523315123441521433..15254312
........124152142541341514225152335224..323123524
.......2352514331225313324431425212522.2135251351
........12223415434244254145431344523...252415142
.........325253131515143153125432341.....24141532
..........23433..235235144135131232.......1542413
...........122....1224152243154251.........21523.
............2......32452135423351...........312..
....................323334125212.............2...
.....................151..25152.......1..........
......................1....141...................
" | |
|
| 8) | |
| | | Returns:
"seed = 9
H = 74
W = 55
targetPattern =
.........22142354552144434452455513423.................
........25531435334552154544413123343..................
.......322242155232333525452243233322..................
......34331534441414531131511524122511.................
.....2425355122255124352231343352241251................
....233455134245543453134224135152321334...............
...52121545211345232232152215424333125533..............
...145153311344332444535413243551253453255.............
..32451223333533214552341134331145215525411............
.4433544432351243232221114433423142233422452...........
5421455542133111314341253345144324434322223............
154244235224234445143453255121143533524525.............
41154422443133145124134534113433242321231..............
5433154143521332341451353413115313521551...............
3114255555424511253554415125243335424343...............
25544313525141432535411541324253134233334..............
4535244452115535233111444141214154351254...............
114233315254133425522532213212422132113................
54315332343313243312255555434431332323.................
3313312342354414111115254323221353354..................
441455532454555135431341145431525412...................
.1534524315442525433225455112235111....................
..13221453144443442133..2251213145.....................
...551124252212314253....41235331......................
....515151242225524.......543344.......................
.....2214352213232.........1224........................
......35343442314............2.........................
.......252213152.......................................
........5433131................2.......................
.........25354............5...321......................
..........332............455.43144.....................
...........2............15433531213....................
.......................1135122441325...................
......................515415243543312..................
.......................411552253145233.................
........................513222413554535................
.......................55212332213353221...............
......................4345512343343235441..............
.....................423134535114132212542.............
....................12342141154511254255133............
...................2335252213525412212124354...........
..................313335555423111454435114435..........
.................25342551432332245515125444554.........
..................333431121532521423441551334..........
...................3514335123221241433413523...........
....................34533212243221413231331............
.....................2124111311212445353533............
......................4431122443422442554315...........
......................43545512324231545524215..........
.....................1545244221325244343111235.........
....................122531451152125334445442243........
...................21111313112354453224434241245.......
....................122544312512331145335533311........
.....................4244551231154411255234442.........
......................23142..5513221554542331..........
.......................114....235..451355412...........
........................2......1....3131552............
.....................................14122.............
......................................144..............
.......................................3...............
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
.......................................................
" | |
|
| 9) | |
| | | Returns:
"seed = 10
H = 41
W = 84
targetPattern =
2414131422........2142342324141313212..142........2214222.1331421...................
13332452422......24241222351532524335244133........25313.251541523................1.
441531315151....2135134352142142452531424313........123.21333431521..............332
3223454415151....2515351253533151413152151512........2.2535222432541............3251
14514131513441....2231353213534224242253334351........213131435413151..........22313
313243351532423....2524252432152514453315322251........4335424224451......2...145153
2354151423522512...33431351444141414151513425142......3151241515212......313.2243231
24134152313153351.33321413514245335251514321251......3151451335232......124124341453
3541531444542132.31513454213512415313525325331......2431512451433......1445244124141
331434513423531.1252353134251451341.141354252......3125243523522......25221515242423
32513214132213.32514212515315214532..1524322......1245252331312......213444143345414
3125443335342.315144534132531441414...22241......13512331244.2......1541521413532241
154313153123.31435312242542352541322...321......1541352442332......13315152541341543
41314251452.2152142342451315231233523...2........21533153232......234523335315124331
2452541431.245332431531335324143542441............325142251......1521254141241451524
213531513.22131451523535134144252223232............1334142........225223513532415313
.3224432..442524141531343522531314544152............14522..........31352244335151322
..14131..32241515253151412353153414125133............123............2531532351515434
...333..2415342514415331454315151532514132............2..............215313123423312
....1..122431512323522541422524442152252512...........................32142525325133
......154425425324125141532513312531542413.............................2445342142234
.....134131423233453153243135153525343152...............................124124542443
....335235234124522443134241241231423431....................2..........2541452215141
...142125151535135125144125434454421323....................221........22422414351414
..231353251514141432241533343124242513....................25252......152154225314531
.235244153324245224445415214144321513....2...............3134132....232423254235224.
252242151331252135212325143142515342....231.............315153512..14315352213131413
122533233532333524353421..335135131....24142......2....13335213543235434143423334531
42324535123535125313532....1432333....3154151....212..341431524222152213514135252243
1353413223512424425131......12323....134415152..14251413351515135331525143344133521.
252223442334224131252........323....1512423421413531324431515144135324252525134223..
.2314525352443525251.......2..2....2314514145342515344521432241524241521341245331...
..25142131252235222.......321.....2533324442412424412244252345223515425423352143....
...141423523141352.......21451...3125152521242432134234153133244525231241252422.....
....3353514524332.........312...1425242124541454431525152145314221315242432152......
.....14215324412...........2...25231415253132243145322435413542542432451..241.......
.....4134141513...............31344544151244251251314524215131243254122....2........
....2243541513...............21421414141541542534253141254143442141243..............
...1521421513.................245433145241432341251341352334141444541...............
....143..313...................2212543151541312451453253151525414212................
.....1....2.....................24313133231342421412432141413314133.................
" | |
|
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.