Problem Statement |
| | Grille cipher is a technique for encrypting a message by writing its letters onto a sheet of paper through a pierced piece of paper called grille.
To encrypt a message, the grille is placed on a gridded (for convenience) sheet of paper. The letters of the message are written in the cells of the grid which are located under the holes of the grille in order from top to bottom, from left to right. If the length of the message is greater than the number of the holes of the grille, the grille is rotated, and the rest of the message is written in the same way in the cells which are still empty. Finally, the grille is removed, and the rest of the grid is filled with random letters to complicate breaking the cipher. The encrypted message can be decrypted by using the same grille and reading the characters visible through its holes in the same order.
You have intercepted a sheet of paper with a grid of letters on it which looks like it's a message encoded with a grille cipher.
Your task is to construct a grille which decodes the grid into a message which makes as much sense as possible.
You will be given a String[] grid which represents an NxN grid of 'A'-'Z' characters. You must return a String[] which represents an NxN grille, with '.' denoting a hole in the grille and 'X' denoting unpierced paper. Your grille can have at most H holes in each row and each column.
The grille you return will be scored in the following way. First, the message is retrieved by concatenating the parts of it which are read by applying the grille straight, rotated 90, 180 and 270 degrees clockwise in order. For each grille position, the letters of the grid which are placed under the holes of the grille are read in rowwise order, the letters of one row being read from left to right. After that the message is partitioned into dictionary words and unused letters. The partition is scored as follows: each maximal contiguous sequence of dictionary words not separated with unused letters adds (number of characters in the sequence)1.1 to the score, and each unused letter subtracts 0.33 from the score. The score for a test case is the maximal score over all possible partitions.
Your overall score will be the sum of your individual scores, divided by the greatest score achieved by anyone for that test case.
Test cases are generated by choosing grid size N randomly between 5 and 50 and filling an NxN grid with 'A'-'Z' letters. Each letter is chosen randomly accordingly to the distribution of letters in the words of the dictionary. H is chosen randomly between 1 and floor(N/3).
The visualizer
is available. |
| |
Definition |
| | | Class: | GrilleReconstruction | | Method: | bestGrille | | Parameters: | String[], int | | Returns: | String[] | | Method signature: | String[] bestGrille(String[] grid, int H) | | (be sure your method is public) |
|
| |
|
| |
Notes |
| - | For more details on the test case generation and scoring implementation see the visualizer source. |
| - | Any kind of invalid return results in a zero score for this test case. |
| - | The memory limit is 1 GB and the time limit is 20 seconds (which includes only time spent in your code). |
| - | The source code size limit is 300KB. |
| - | There are 10 example test cases and 100 full submission test cases. |
| - | You can get the dictionary at runtime by calling the library method Dictionary.getWords() that returns the list of words ordered alphabetically. |
| |
Examples |
| 0) | |
| | | Returns: "seed = 1
N = 5
GCNQE
XSRTR
EIWTI
RCOLV
NJLOU
H = 1
" | |
|
| 1) | |
| | | Returns:
"seed = 2
N = 22
ISDBOIIUMROASELAARTEPN
CINIRLUANGSAOMRATRREEK
SLASNTAFIROTIOZTBRREEN
TGUNSFIESEBNSISINANIAI
AORIINPTIZQOIMSAIUGORR
NMTRONSYEINIERSINAAKHI
ELIGTVDLIOSNHNRXSEAUPA
DIROSSTNJHSTAHLUNSURKE
AMHOTNKEAINEYSOAESNANN
EESZIONVAPTUSEGSNEOAOW
SIIICEALUCYHCEEUIDCOHB
MRATPMNGRESIFBCGCGUVPG
CTSUTATOETRNEHSOLPQESS
TMGUIOTACSSKFPPODSEDYZ
LDCDLPCNAUIEGNAGURNMGD
RAIROSBDPEPLELAEETSNHU
LMISUNYIGFTBBSPDHIERDS
UETRTSUECHCCEKNFBPTDBM
EUPERFCNCURAEETOTERTWE
RTSRDOASROIEYTTTKHLNGS
YARRLEAEIRYDRIEPIYUYAR
THHESMSLUEPRSKGYASAGGD
H = 5
" | |
|
| 2) | |
| | | Returns:
"seed = 3
N = 24
NNTDNOLSDATFFNRTCIICOIEN
OSEULAYSCPOESVENVIDSLOUR
OSSNEEPCVHRBTKOFTNMGFNOI
HOSGNJESNLNPGSMDSRAWIIEE
YITPHGAIMOEUPKREISGYASWJ
REAETRELEIOLQGITAIINIELM
YWONVKESHOTMRNGUSEOETKVI
LLAYTGGRATKSVEDEOECBMNDU
EBITVBCMSORUIEBNGTVRRNOE
OESAGAMINIIGINWSLTERISHU
TRYIRITCRLTIRIEGSESSTFPS
HLSSCAMAACIBWCEYEGTACTRP
SSCEMTISCRDOUARGGMSAPNUC
IEGRULGLILUOSQGEBRHBOTEK
DPARNAAKLIUEPRSRIGDRNASA
ONYRESKTAEEOXLOPRHIKMSIE
ISMXSADTRKFELRNUIEGTLMPM
SCCSRGAETASRAPBESBDOKKOI
AETRRICTNINNPUOITSCISNIN
LSLTNSCNLCTNUSENIYAOSNLE
PHASESUPSECNLDIOSENRSEEV
STTBUTAIILMISDIUTELEOELA
LIOLLREINMTTVLALSLSIEOSC
UOCBANREAELKBRTLEAISEWGT
H = 3
" | |
|
| 3) | |
| | | Returns:
"seed = 4
N = 26
ACOIISONSOPOEEBIESENESMRCC
NTSRPVKCGIMRRATEWLAEGOIOAL
LFINABSNMAASPILOCEIABLNGAE
OGIOBPRLNTUTYUSOLMOLEDLTPF
RAIESRDEPEXONFAASSLFEPREMG
EAFTGAMAYENFENHOITMETDFFEE
EIAIUCGRARDOUFSDECRIEETNGC
LSHEYGBAAMUGILIPIAEIPOOCSN
YONSSSARTDPZOESMHENSIVESER
USNSNNRENAGARUCSTUNEEWTCMR
TUAALEIPEINCCCTRAESEANIFRP
YSMTTAOETCRISEOGLRRNYSETRO
NLOSWECAODINUTTAEIETOSCRBS
NNATRSSCSUNERTRBNTERPUSKAA
EODEIIIDHSOSOSUIPIENDTNOZN
SSITNNTEUMTMEROIXGTLOPNILA
SENISLNLAIIITLUEAUTSOIYTIC
OICPOKNSRSHSESNSOTNRTRINPL
NORAGINULPLWIFDIRDDRTMUSRE
CARAIPECTHITEEFCTOEKNNSINW
AVRARIZRNSMAVOLENRUDMBLRDY
INSJIISHEBAIELIAHAHREIEHTN
SIRTLAEDNTHRTAENBMWIMNLRSK
EDTNINCLOTITUHOSNSEUAISRSA
SVNZIATTTTAEOEISDRIAERCRGR
EUETVNTSGDEETRORRRFAPAINRA
H = 8
" | |
|
| 4) | |
| | | Returns:
"seed = 5
N = 25
LADMATYRERTRIFGEMITRETCNL
IVYRSRESGEHSCOFESTDRNWFLC
DACEHCOOALPUSAURINSUNLOER
FIUTOOKEIIDRDIFRVSSPAEPLA
MCLEVUMDFLEEEVNNLABIFBISP
EAEUCDLATNNRGHNAIOLLVZUTS
EITOROTDLTSUANTTUFNDTAABE
KNDNETGBSENESOONBISRUIARI
DIELCBILPIEYTAOGUAELPSWSA
TRHNCSEENEPRATCCIMBISTOOL
IIRIKTIOTSHIHSACABUAATRWV
LLSTSDREASSUNCEEANGIISIAR
IFRLNANIREAZONFOANORSVLEM
EHUUELAIYEENDSASRGASGLONT
NNVKRTLYESIEESDEADTRRBCEL
NEAZIISDSLHANGRENOIPEUEFI
ASAASDLEEMALIOESIUNDALTSG
USUASCLETKTTHTODMECMGSEEB
OKSRHVMITIILCBTPRLCLNGLIL
CMECNNOKPEDAABNOSESUPLNIR
CEOPPTEDHPTARMNWTUMBOOSRS
YNDRPOIRTEAFPPAITLEJSSIIL
HHTTMGNICPTTGMLQEISISRCDA
SESCLESKGTHETALASIOTPIENL
NIWMANTUOLRTKVRRWOSEIAUAN
H = 1
" | |
|
| 5) | |
| | | Returns:
"seed = 6
N = 39
OTKEEPASEOSUATIMOPBRHIVITPPRLPTISTSCARL
REEALUAHEPENNSNTEHESRAAIGPISTEDSOIEIHYG
EIORNDULUEIILEOSLELEBNDORTPRLSCUSSSEGYT
RSSMLUEATHSSRDDAVMETOTSGPSEEZOLMIHSEOTE
IEOTOUOIHSNOBKORSRAIPLRSLIEPMNNLRORSIRO
GECPIDMHHKFELSELSERISATRCUENFSIEOARCAPR
LLSUTNNNANTANNPSKASTSSIPRYLTRSUVARAOCMA
OSSBPPEEAROIRLAUSDMAMILSEEEIEBOMTBLSDRI
RSCECRCONPNSETSPESLSTSOUYTHOEFREROSSTNA
RACIERROUTRTDRESCCNSHPFDAENYZDSETETOLIA
SGRMSBBUERDSIVTSOOECGHEDSNTENETUASEAEAA
WENDDEEYACLNSOTSEEDOPEMTSENBTGIILIEATEM
EESMUGSRIAANIAGHLIHOUTOTETETOERCLLISPNR
IRSCSIIPSPEVEEXISSDLEOGYTHETONRMSDTODSC
RIRIMRMNTMIACLNDHVRUSLISIEYSEEAELMIMSRB
CTELHCDOSFHMLTSENTORRSPMEISOEERUBALANTE
ESEHRFATHLLMUNEEDLONETSODENLPEEEILCLEEO
ESOEECPLPASNVPURLZRRYMESRPLAOPEORNRCUSS
IAILEEATSEIIIIIALSELXEAEANEOSFASHRIEIEU
NHASTIRHAIMBACATREIZSIACEPNSUSGGVSSAOEA
OLTRHDHMTPCSCCKHOMSALEAEIFODHOMOEUSERTT
CEEPINOAAIHRAOEISECGAIEAOPRSASSOERLEBEI
TDDONGUMEYELEEHUBHMLLUINLNBUNSINEPRHPSN
DSTNESBEEMOLSIUCZMTABRBLAAGUVUEPARLSPAA
DINTRDISVTLISSTAEOXRSITSTSTGVETEGEAYTHT
YVNLRSSUYPNENLOSALENIHOEEYFRBEIQLAARMSG
IIDRONANAHLDOISEGAKLEGOOHUNAIOWREGOLAVS
FTIECUUSINURMOCECEKYARBETROIMSNERLSOILS
ZTRUSOITGIISCUROEEASFKEERSNEIIISRSUCORG
CIIEITRLGIGLSUMOPSOPOETHPROLTPRTSEILEEU
AEMDIAFABPRDSUCSHBRTOLIMYMSLRECDSUSDFDA
VRHLNLDSSDENQTUEETOIIBIESRFIIAISMOCPPRE
DENSDRGUAFRRABRRRRPNJFSPIOLDTRLDOEOTNST
ONCEOGUACLIEGADMISNEYSLPEIEGBRIYFEEZSSE
LIDRCRBLNWLASAASCIQTNRNIWOTYROGTSACAASL
ETSSSANODTOETNPZRRUSGTAMRPNSAOSRTIEPERS
CEUSLPARDTRFNDCCCCICILROLALHYHNTVRTSBTM
ETRLAMDEBCEQTAWDLSRTMIEIWCNSOATFNPYNEHN
PPCCASDONCOODKPEAYIRSACELAAATDLBETHLIAR
H = 10
" | |
|
| 6) | |
| | | Returns:
"seed = 7
N = 19
NIVENSSNNYLSROBOUTN
RGIHBYMOICBOPNTUARO
RPOENYHEECSGEOLSEET
CTISMGSIBTNRFTUTSLN
SLAISNNLOIDNIBPTNHU
LSOTSODUHCISRCNUORE
DNSHSTAEMAOSNIANCOB
IGEELPROSOASOGSOUTS
SAARIAGHXHDESMDEODU
VSRELALPIRPEGMIYRSU
OAAMCEORTMFIEEUFETN
COMOVYRESEPFROEPEON
GZGUIENCIAKINAESENR
FSPABYNRTAFMTTPURTO
IOCLUEALYAENBLIEUEO
OHILSUNGLMCTTTEEGTP
OTIMESEFEIBUETUEOEE
TSEOTDANMOLEERUSGAR
RDNRPEIOYSISIEGIHNN
H = 1
" | |
|
| 7) | |
| | | Returns:
"seed = 8
N = 16
TEGCRTLSSHDSITER
TGASCNERPRAASORU
TAUASCNHMTIILLND
NEIUSMRTRLRVSSER
XRCEGTSMLDATRIIO
TIUSESOSCEVRDNOS
TRRLGLCRSEYNSAAB
CESPNCOMCREIAASS
EHATRICNCIITACUR
LNTITRTIIVSCRSOT
LCAEOHXRSAINVNBG
OCIINRSLOTEZTWEI
DRERASILWTDESCIL
DSECGESIMNUEALNG
DYTEYSUKCEEARPAS
LADSCCUPAEVGVHRN
H = 5
" | |
|
| 8) | |
| | | Returns:
"seed = 9
N = 45
EUTESDNTOOSWPIHMOORDASLTESSSKHTTIDCPNUIAMXOPL
SYOMIARZEASVIVVITAIUHECOOOCLAHAINONTAEIEWICTM
BOLOBRLALIRSDDSEOABIRPNNTSEBUKMPNDEENNACUHUYD
WEISMIHSVAEUSDISEEUDYRENDSIRNARTDTTRNGRASUAAP
ACLEOREEGDEASAYDTYSRRCONREBSHITRCDLHMOCEINOAY
MDLGSRESBEIOKCSTIEFNCFHCNNEISTAOEDOPAADUCRNBS
PAAOLANETRMLSRSEATOTOARBLOTPMEVSNLRTCTYRIIIEE
REPNYPSISEEBRCESSINNUIBEORLSITASSKCPLESAILIYS
SYNEOCLEPUMTSFAGSIEEDENRITINSAEAUASSTLXYSDRTL
RDSMSERTPDSMVSPECIONZTSOEIRTADISSIAEYUNHDMLQS
EACGUKCAIARAGIIRLARRSNTHMCATUPNUEESSLITEUIMHT
EENSIDEYSCGEIFRAIGIIPDSSNTAHRLAISDLTANDOLOUGH
EDLMIKCNRNCIEGCYBGAONBMATEUPNAESOLRPSNDOOTSEO
BITATTPEDNITEEMDPISYBEEUETTUOBSZSTSEREFGESNBT
YDDYNDRALRBLDSSELIEAIADCOLSILESYSRTTOTGENBRUP
ERRRSLINPEGSEMNAAHSOIIBDCUENLSRLOCDSNBLTOGCSF
LMOSEUEPAHJSOLETTSNLLOENONFENDDRAFETRYIARTTSI
EPINSTNRSSRMMBCLGEGTOMRNUELIANASVLAUTNBDHAEYO
ONDMYGSTCINRRSPOEDNXLUTACFHNNNFAIRREINSSAHSND
VSORRDCWLUTCRMEOCPUIEEETCNTIFDKSLSWGIVMIAGUAR
ILNGTSYOATACAAATESIOMOIEOOOCLYIIDTOOTTRVLAOET
MDDNEIOECZSLEIITSACOALEFCYYVITAPISECEYLIETRSU
OTTITLLNTMOABCIELSYENTASLZKNINUMGLTAAEDSIUENN
OBHOAIPILULSAMTBQDTDCOONOSREDINRFGAPAHIMLUOGH
MEMOIRTRURDTOSETPEOARGIGSDLLGEXIDOLNIVOTGTLTE
SMSUMDMCDLAPUCRLRHONEYEIDRMRRXBOERERSCDIPSONN
TOIIKMINOIACEEYRSHEIAREHIINOAFALOHREILETIALES
GVSYTTDEISNONOMFRPOKIIOAOSAOSITARVECIALLNEONS
PLNESBHENPRLGIFEEAPADSSIERSLNOSNYMASOILORYUAI
ADAIRHGOPZFEETNCISAIROTEFISIERIINNCOOYSHRNOIT
NELNGTAUGNIGCNDPSTIITMGTUENSRRSSCDCBAHIUIYARF
UOOTARCIINAUYCHLDSCEHBISCPCOITETSGBIEUSOINEDN
SELETCRNVLPEGCBAEAEHDESIRETYIISUTEIIOMRERAEET
DROOEPEOOLORMSYIROTEEZSLNICGEIUZBOIPEGMOESTAR
UEPORTOADNRNUICMENNGPPETCEYAIGNGYECPNTSPAHIAI
SWYDNTTRLRCINRSISRLSFTUSOVOOSTOOOFSSTEGAGRGOS
EETLUNRCPCRNRATSRRGILASICWIELSPGUEMIDRSCTSNTS
ENNBELTWTBERNHMKRSCRENLIKTNUSOTMMPIPALEINPRTG
NERLTOVNSLRBCEAMCSSIIIIDNHIPPNURUESSFLRRPILAF
CSPSDEHGSARCTSNAANJNOTIYAANMNSEENTCEMSATOFYNN
EANNEDEELIANLOTORCTHLIRUULOYTSSICDVMIOCSERCUS
PBOASCOLSAALOPNIOAOEEMHTNOVILOECMNOGSUUIRVCNN
TGTEREYIMLOSEFEEOPCTAMCEDHTSTOOIYGNGAHNRNAIEE
ICAIIAGISCRNISTMEIENERHWMHZETIEUCWUNTHSSUEBWE
OEARESOCSRITRGLLTPOSCAAASIHWPKNDUAANMIATISSUI
H = 10
" | |
|
| 9) | |
| | | Returns:
"seed = 10
N = 18
RACENGCYCOSHAMUINR
NLLUIGWLSEFABNICME
MEUSEAVHNEDGNEHLAE
IOILEIOPNXEAOCNAEL
NUGEMAESANUIBVVLGA
CMITOIEZRHIEOIEAIN
OETSALNFUTMBRURHER
CINALISNEEROLGGEUI
EOEEVHTDOLROOOWIEB
RDFSLELOOUPMODTGWI
ARMBROSISTSHTSMKOB
IISFTOOMHECCXYAWAS
NNNIEOUSNGOALERCKL
RSPATISOPIESTLAUNU
EIRENLLOEEKNAIQAEB
NYLSDNOBAFAISSHEND
NREUSSLKIOWMASEGOV
IVOPNTNEIAGPAFTRIS
H = 4
" | |
|
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.