JOIN
 Problem Statement
Contest: Marathon Match 47
Problem: GrilleReconstruction

### 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)

### Available Libraries

Class:Dictionary
Method:getWords
Parameters:
Returns:String[]
Sample Call:val = Dictionary.getWords();

### 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)

 ```seed = 1 N = 5 GCNQE XSRTR EIWTI RCOLV NJLOU H = 1 ```
1)

 ```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)

 ```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)

 ```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)

 ```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)

 ```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)

 ```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)

 ```seed = 8 N = 16 TEGCRTLSSHDSITER TGASCNERPRAASORU TAUASCNHMTIILLND NEIUSMRTRLRVSSER XRCEGTSMLDATRIIO TIUSESOSCEVRDNOS TRRLGLCRSEYNSAAB CESPNCOMCREIAASS EHATRICNCIITACUR LNTITRTIIVSCRSOT LCAEOHXRSAINVNBG OCIINRSLOTEZTWEI DRERASILWTDESCIL DSECGESIMNUEALNG DYTEYSUKCEEARPAS LADSCCUPAEVGVHRN H = 5 ```
8)

 ```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)

 ```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)2010, TopCoder, Inc. All rights reserved.