NumberGrid
TCO11 Championship Round · 2011-05-07 · by narri
TCO11 Championship Round · 2011-05-07 · by narri · Dynamic Programming, Math, String Parsing
Problem Statement
Problem Statement
NOTE: This problem statement contains subscripts that may not display properly if viewed outside of the applet.
A number grid is a rectangular matrix where each cell is a digit between 0 and 9, inclusive.
Given a number grid G, an encrypted grid E with the same dimensions can be generated using the following procedure (using zero-based indexing):
for(i=0;i<rows;++i){
for(j=0;j<cols;++j){
Ei,j = 0
for(r=0;r<rows;++r){
for(c=0;c<cols;++c){
if( (r equals i) or (c equals j))
{Ei,j = Ei,j + Gr,c}
}
}
}
}
Note that this means each cell in E is the sum of all the cells in G that positionally share the same row or column. (The cell in G with both the same row and same column is only counted once.)
An example number grid G is given below:
------------- | 0 | 1 | 3 | ------------- | 2 | 5 | 7 | -------------Performing the above procedure yields the encrypted grid below:
---------------- | 6 | 9 | 11 | ---------------- | 14 | 15 | 17 | ----------------
The cell in row 0, column 1 of E, for example, is calculated by taking the sum of all cells in G with either row 0 or column 1 (0 + 1 + 3 + 5 = 9). Note that the '1' cell is counted only once.
Given an encrypted grid E, reconstruct the original number grid G if possible.
The encrypted grid is given in three separate String[]s. hundreds gives the digit in the hundreds place of each cell in the encrypted grid, tens gives the digit in the tens place, and ones gives the digit in the ones place. In each of these String[]s, the j-th character of the i-th element represents the cell in row i, column j.
For example, if the encrypted grid appeared as follows:
------------------ | 106 | 72 | 5 | ------------------ | 14 | 135 | 17 | ------------------
The input would appear like this:
hundreds
{"100",
"010"}
tens
{"070",
"131"}
ones
{"625",
"457"}
If there is exactly one valid number grid G that yields the given encrypted grid, return a String[] representing G, where the j-th character of the i-th element is the digit in row i, column j. If there are no possible number grids, return a String[] containing exactly one element: "NO SOLUTIONS" (quotes for clarity only). If there are multiple distinct solutions, return a String[] containing exactly one element, formatted as "n SOLUTIONS" (quotes for clarity only), where n is the number of solutions modulo 1000000007 (10^9 + 7), with no extra leading zeroes.
Notes
- Two number grids G1 and G2 are considered distinct if at least one entry in G1 is different from the corresponding entry in G2.
Constraints
- hundreds will contain between 1 and 50 elements, inclusive.
- Each element of hundreds will contain between 1 and 50 characters, inclusive.
- Each element of hundreds will have the same number of characters.
- Each element of hundreds will contain only digits ('0' - '9').
- tens and ones will have the same number of elements as hundreds.
- Each element of tens and ones will have the same number of characters as each element of hundreds.
- Each element of tens and ones will contain only digits ('0' - '9').
Examples
0)
{"000",
"000"}
{"001",
"111"}
{"691",
"457"}
Returns: {"013", "257" }
The example given in the problem statement.
1)
{"0"}
{"0"}
{"3"}
Returns: {"3" }
A single cell means that the solution is equal to the input...
2)
{"0"}
{"4"}
{"2"}
Returns: {"NO SOLUTIONS" }
...unless the input would not be a valid number grid.
3)
{"00000"}
{"00000"}
{"22222"}
Returns: {"15 SOLUTIONS" }
There many number grids that generate this encrypted grid, using either 1) one '2' and four '0' in any order => 5 ways 2) two '1' and three '0' in any order => 10 ways for a grand total of 15 solutions.
4)
{"0","0","0","0","0","0"}
{"5","5","5","5","5","5"}
{"4","4","4","4","4","4"}
Returns: {"9", "9", "9", "9", "9", "9" }
5)
{"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000",
"00000000000000000000000000000000000000000000000000"}
{"33333334443333333333333333333333334444333333344443",
"33443334444433443344443443344443334444333444444443",
"12222222232211221222222221122221112222222222222222",
"11221112222211221112221221122221112222111212222221",
"11221112222211221112221221122221112222111212222221",
"11221112222211221112221221122221112222111212222221",
"11221112222211221112221221122221112222111212222221",
"22222223332222222222222222222222222233222222232332",
"12222222232222222222222222222222222223222222222222",
"00000001110000000000000000000000000011000000011110",
"00000001110000000000000000000000000011000000011110",
"22222223332222222223332332233222223333222223333332",
"22222223332222222222222222222222222233222222233322",
"12222222222211221122222221122221112222111222222221",
"11111112221111111111111111111111112222111112122221",
"12222222232222222222222222222222222222222222222222",
"11111112221111111112221111122121112222111112222221",
"22222223332222222222222222222222222233222222233322",
"23333333343322332233333332233332223333333333333333",
"00000001110000000000000000000000000011000000011110",
"00000001110000000000000000000000000011000000011110",
"00000001110000000000000000000000000011000000011110"}
{"15665552256622663579996773388683330022444659811215",
"59009996690066007913329117722017774356889103254559",
"61221117702288228023331339944128884467000215465650",
"49009995580066006891129117722016662245888093243438",
"49009995580066006891129117722016662245888093243438",
"49009995580066006891129117722016662245888093243438",
"49009995580066006891129117722016662245888093143448",
"05665551146622662467774773377562229801334658709104",
"83443339924400440246652440055450007790111326598982",
"05665552256622662468885773388672229912444659810104",
"05665552256622662468885773388672229912444659810104",
"38887774479955995680008006611994441245777981032337",
"05665552245522651368874673387562228802444548810094",
"50110007790077007913330118822127774456998004365648",
"16776663356633673579996874489783330022554660921204",
"83442229924400340246663541156450007799222426587871",
"37888885589955885791118996600905552234777982143426",
"04555552256622651368874673387562228802444548810094",
"60110007701188228913331339944227774578000214365660",
"05665552256622662468885773388672229912444659810104",
"05665552256622662468885773388672229912444659810104",
"05665552256622662468885773388672229912444659810104"}
Returns: {"01111111111111110000000111111100000001111111110000", "01111111111111110000011111111110000111110001111100", "00000001110000000001110000000110001111000000011110", "00000001110000000011100000000000001111000000011110", "00000001110000000011100000000000001111000000011110", "00000001110000000011100000000000001111000000011110", "00000001110000000011100000000000001111000000111100", "00000001110000000001111000011110000111110001111000", "00000001110000000000011111111000000000111111100000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00111111110000000111110000000011111000000001111100", "00000000011100011100011100001110001110000111000110", "00000000011100110000000110011000000011001100000011", "00000000011100100000000010010000000001001100000011", "00001111110000100000000010010000000001000011111111", "01110000000000110000000110011000000011000000000011", "01110000000000011100011100001110001110000111000110", "01111111111100000111110000000011111000000001111100", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000", "00000000000000000000000000000000000000000000000000" }
the old TCO 2009 sample
6)
{"22222222222222222222222222222222222222222222222222"}
{"55555555555555555555555555555555555555555555555555"}
{"11111111111111111111111111111111111111111111111111"}
Returns: {"106591981 SOLUTIONS" }
A case with high enough solutions to use the modulus.
8)
{"34434443444434434444433444444443444444444444444444","34434443343434334444333444444443344444434444444443","44444444444444444444434444444444444444444444444444","45444444444444444444444444444444444454444444445444","44444444444444444444444444444444444444444444444444","44444444444444444444444444444444444444444444444444","34434443444434434444333444444443444444444444444444","44444444444444444444444444444444444444444444444444","45444444444444444444444444444444444454444444445444","44444444444444444444434444444444444444444444444444","34444443444444444444434444444444444444444444444444","44444443444444444444434444444444444444444444444444","34434443343434434444333444443443444444434444444444","34444443444444444444434444444444444444444444444444","44444443444444444444434444444444444444444444444444","45444444444444444444444444444444444454444444445444","34434443444434434444433444444444444444444444444444","34434443344434434444433444444443444444444444444444","44444444444444444444444444444444444444444444444444","44444444444444444444444444444444444444444444444444","44444444444444444444444444444444444444444444444444","34334443343434333433333344333443343343334443434333","45444544444444444444444444444544454454444444545444","44444444444444444444444444444444444444444444444444","44434443444434444444433444444444444444444444444444","44444443444434444444433444444444444444444444444444","44444443444444444444434444444444444444444444444444","45445544444445444444444455444454454454444544545444","44444444444444444444444444444444444444444444445444","34434443344434434444333444444443444444434444444444","44444444444444444444444444444444444444444444444444","44444443444434444444434444444444444444444444444444","44444443444444434444434444444444444444444444444444","44444443444434444444434444444444444444444444444444","44444444444444444444444444444444444454444444445444","34434443343434334333333344333443343344434443434333","34434443343434334444333444444443344444434444444434","44444444444444444444434444444444444444444444444444","45444544444444444444444444444444444454444444445444","34434443444434434444433444444443444444444444444444","34434443444434434444434444444444444444444444444444","44444444444444444444444444444444444444444444444444","44444444444444444444444444444444444444444444444444","44444444444444444444434444444444444444444444444444","34434443444434434444433444444444444444444444444444","34434443343434334434333444333443344444434444444433","34334433333434333333333344333443343343333433434333","34434443444434434444434444444444444444444444444444","44444444444444444444444444444444444444444444444444","45444444444444444444444444444444444454444444445444"}
{"95193528030293092212089134211349141262202431426101","74082327919272981101878022100329920050191211305109","18426750252615324534291456433662264484425654638433","30738972565737547756524578665885586616657886960655","18426750252515314544202466333662363484434654649433","29437761353626425545312566444662474495545654759534","95294528020393091211979133211349141162213332417201","39527752353626425645312566544763475595546765759534","30648973475737647666434578666884586616657876961756","06305530132404203323190244222451252373314433537212","96304539130303102322180134212441142262203442527212","07304639131404102322190244222550252273313442527222","85183327929282081210968123109239031151192321415100","96204539131404102212080134221440152263213432516311","07315549231404203323191345232551253372324443628322","40648983475838547766434588765884586616657976971756","95194438020292081211079123111330131161102421416201","95293428920282092211078123211439141161202431416201","28426761353626324544312456543663474495435654849443","18426741252515324544202355433662364484425654649433","18426751353515424544202466443663364484535654749423","62970205707060869089756801987007719839980109193978","51859184686849657868545789877095607727868987072867","18425750253515325544201356443652364485435654748434","07394538131493102312089234211440152262213432427212","07304539131494103322089234221441142262313433527212","06305539131404202323090234321451252372224543537322","62860195697960859978646700977906718828869098072878","29537862453626335545312567544673474595546765850534","85082417920282081211978123110229031151192321316100","18426751353625325545302456434663364594436754759433","07304549131494103323090335222441252373323543627222","07204539031303292222180234311341152263203432527212","06204539131393103212180234221440142273213533527311","39537862464636436656313567654774475505546765850545","73071206808171970999767911999118929940080209294988","85182317919282981101978022100239930041192311315190","17315640242415214433191345333551363383424543638322","41749083575848647767535788766894596717767877961666","95193428020383081211079034110339041251102331416201","96294539030393192212080134221330152262213432426211","28527761363526425545302467543673474495536754749533","29536861363726426545313467544673485495546765859534","06314640231404203423191235232441253373313543538312","95293428030393082211089123110330041161202431416100","73082316808171970090868011999118820040081210305099","62960195797050759988746800877006817828879198183978","96194538120393192311080134221430141162213431517201","29526762453626425554312467544773475595535765749534","30647963464737546666423678655784585606646876860655"}
{"48959365008861973364628131273417458122394028627733","99898318524492350560915118260080696938492530221007","78855055447194834291596113597150971431785853999426","64296107390938640164195986714601780015379404508319","64902118449586562026253406958121456748828427710464","95910546969870392810215119851668594625119868434050","78320144846130478617847024010817323473202633570370","11671881994237392097456049790586162140135213846762","73787311776868003902615844261436391315971597175291","67272890771327584475714848715633036015471792406957","52026766388929149517284983881701257275892305110382","73335047883311648907302043730129232554585608337600","75693938636081336018685003069923520167893003345245","78549754102103506986495857528897826561527513299146","92834865294692563745832211822138042229406924291224","27896303972191440537614932254395591706615038201055","55670318697919998033088688761191272745767294243375","05149868976788960468079495253037066465006307221394","57956527494401569657123295145433363830768965061809","63741182709986013020972638278567334466581700630648","85770006546886047035731414432230795583205714642594","38725218224557288010742960458995882761100353406688","75184241759792437091615698111138414725383997463060","59439346765467332036528697944495760250906312158521","30176189150039019278928462056188401691542736733910","52271741502094902125928656753362593789316321755491","99461796856822349485938686017834039457812255819133","27474834701510091165412703069906213097387612998372","60327400386619926584678384587930737246507035113578","74997098242321068216746273202990411534153433432303","77618352176229545820153892391421977039530057707848","13586507576387651861819190990885359084128632085717","20916325810808076714072653069960235961486978115670","45549740461667952888063473215835392531868290873298","25912968626749454640895458109721499838636657252411","53321942697021122823605324550392107820081033164729","40426598499045923364637866062812775893371063804265","26582816434710940654427749921314123248221634841676","16042417758323287764621056135839946224327870468807","34558177286040999312384930639177211084981608715194","60481122729153477843742663116898213044911553736418","78074808319920596941192702377514517923563686349559","77329759635048761974902834442831504972910616007683","58308222194950671155050790714893433555447120840192","69468391106014490563218185374280946258373327853747","88423535679636129892650029853990861283185063340427","39150371026280793204196125887578028758735161351143","87990217184861192098410871200372055941134069363685","37388833166657758608777412448403092030679757969068","35908193578799213534278194299717786241669187959114"}
Returns: {"47764075922906524730022932222828033263329526504894", "74603800284153925312513733013033673235009892788308", "51202729927017007247598394342529954398372135676545", "87083899296495413596111743347290367936900706289874", "65155666925625379412831001981558479081239561855507", "01814905172008216395546065755788008871615897808688", "06282185073526918376792938374317057801300800540146", "07375882369863438330527357038082652578811664618198", "89603796921676161869702996901576867747419724723003", "39552651360551024730047336891713566481353963836781", "99253230208404914143022746270190890776487805677801", "01277282036345748086237919654005148720027835783816", "32242624516908383208287282658534183440042763008504", "73730242484220557774811872533004221480752697598047", "26112808069408267682141185906430772499540953263636", "46605815836454835345814919029728778467886394708350", "18821800111636387849440263512922097428734138766030", "68352350832867315414459456020086203708495025788011", "27656702425255827336416767249791017444844578059617", "66316692665225828418112879661112591363576288935323", "66509990040547016625575215629661352468074496145699", "68009233817321320195019214158451710735624302836050", "09428088160964959992924364273096966559229546657456", "81739549710855610513677921006395276680262787528551", "00092706325283933371277156994602535249626363943162", "00119366195440262646499184419640665373074990143803", "07363755285056269720823598599512563049912400423505", "24805162885813062595894926092995834954992598899811", "69730374088592915954416123352749198583550953452493", "33948564900668651000126012415567292073782333911446", "96883866632326730052375059982692392134961375202567", "83248944565591957344942084616561243412606023257921", "21363671776525087946234076092931812080893232672513", "17841367236877212983354367957177866521522021025006", "48589250182806821232633493174392870335865775757994", "09069165000413042948712416612610051232309288734575", "45297842531722574730013207433423716592342581327362", "36808291263724224117990091241698035814169687057628", "91893145494666432552241239582628767383518996985942", "28832930411494275459033800533835947078409613183100", "58565541534947353584231733612770501674035324728442", "28750643722958012264669472239832085573261079993189", "52738025739163170564182673497848321857147372568388", "59537330058039048161812595903664270052498646503657", "04033827602531885319210766909833323915128005156668", "29412027573353590424212266864567842324750703003322", "12129625560143360456110504274323029293544049436040", "20945345068128527228452414417185658666701707080164", "81668830197443072729206984380165722688377120595892", "94159681896412628904816313640962149588498801616857" }
A 50x50 case with entries in the answer uniformly chosen.
9)
{"87788787887788778788777778777887777877777788877878","77777777777777777777777777777777777777777777777777","77777777777777777777777777777777777777777777777777","77777777777777777777777777777777777777777777777777","87787777877787777777777777777777777777777777877778","87788787887788777788777778777887777877777788877878","77777777777777777777777777777777777777777777777777","87787787877788777787777777777777777777777777877778","77777777777777777777777777777777777777777777777777","87788787887788778788777778777887777887877788877878","87788787877788777787777778777777777877777787877878","87788787877788777787777778777777777877777787877878","77777777777777777777777777777777777777777777777777","87788787887788778788777878777887787887777788877878","87787777877787777777777777777777777777777777777778","87788787887788778788777778777887777877777788877878","87787787877788777777777777777777777777777777877778","87787787877788777777777777777777777777777777877778","77777777777777777777777777777777777777777777777777","77787777777787777777777777777777777777777777777777","77777777777777777777777777777777777777777777777777","87787777877788777777777777777777777777777777877778","77777777777777777777777777777777777777777777777777","87788787877788777787777778777777777877777787877878","88788788887788778788777878777887787887877788877878","87788787887788778788777878777887777887777788877878","88888788887788778788777878777887787887877788877878","87788787887788777787777778777777777877777788877878","77777777777777777777777777777777777777777777777777","77777777777777777777777777777777777777777777777777","77787777777777777777777777777777777777777777777777","87787787877788777777777778777777777877777787877778","87788787877788777788777778777877777877777787877878","87788787887788777788777778777887777877777788877878","87788787777788777777777777777777777777777777877778","77777777777777777777777777777777777777777777777777","77787777777777777777777777777777777777777777777777","77787777777787777777777777777777777777777777777778","77777777777777777777777777777777777777777777777777","87788787887788778788777878777887787887777788877878","87787787877788777787777778777777777877777787877778","77777777777777777777777777777777777777777777777777","88888788888888878788878878878887787887877888888878","77777777777777777777777777777777777777777777777777","77787777777787777777777777777777777777777777777777","88888888888888878788878878878887887887877888888878","87788787887788778788777778777887777877777787877878","77787777777777777777777777777777777777777777777777","77787777777787777777777777777777777777777777777777","77777777777777777777777777777777777777777777777777"}
{"09910909009900980800999980989009998099999900099090","88898788988798868788878868778887787887877888978879","98899898998899878798888879878888887987877898988979","88898788887799878788877868878887787887877888877878","09909899099809989899989979879998898998988999089980","09900909009900989800999980989009998098988900099090","98899898988899878798878879878987887988887899988979","09909809099900989809989979989998898998988999089980","98899898998899879799888879878998887988888899988989","09910909009910980900999980989009998009099900099090","09900909099900989809999980989998998098988909099080","09900909099900989809999970989998998098988909099080","98899898988899879799878879878888887988878898988979","09910909009900980900999080989009908009999900099090","09909899099809989899889979888998898998988999989980","09910909009900980800999980989009998099999900099090","09909809098800979899989979889998898998988999089980","09909909099900989899989979989998898998988999089980","98899898998899879899888979878998887988888899988989","99909899999809989899888979879998897998988999989989","98899898988899878798888879878887787987877898988879","09909899099800989899989979989998898998988999089980","98899898998899878799888879878897887988877899988979","09900909099900989809989980989998998098988909099080","00910900009910980900999080989009908009099900099090","09900909009900980800999080989009998009999900099090","00010900009911990900999080989009908009099900099091","09900909009900989809999970989998998098998900099080","98899898998899879799888879878897887987887899988979","98898898888899878788878868778887787987877888978879","98809898998899879899888879878998887988888899988989","09909909099900989899989970989998898098988909099980","09900909099900989800999980989098998098989909099080","09910909009900989800999980989008998099999900099080","09900909999800989899989979889998898998988999089980","88798788887788768788777768767887786887877788877878","98809899998899879899888979878998897988888899988989","99909899998809979899988979878998898998988999988980","98899898998899878798888869878897887987877898988979","09910909009900980900999080989009908009999900099090","09909909099900989809989970989998898098988909099980","98898788888798868788878868778887787887877788877878","10010910100011090910090080090009909009099010100091","98899898998899879899888879878998897988888899988989","99909899998809989899889979878998897998988999988989","10011010110011090911090091090009009109099010100191","09910909009900980800999980989009998099988909099090","98809898998899879799888979878998897998888899988989","99909899998809879899889979878998897998988999989989","98899898998899879799888879878998887988888899988989"}
{"68803548436477670841725935567332396490701530635405","91147993070819095495161368910576842826365176090840","47493337205253638829414701455990286279598338534284","93159981979731216497059469010554742925266094999759","11058883050929005376050467891766622735254085191841","56584348306484669922505802364101386499699431526105","56493337495154658829394711455099166370509510334075","04348802082031105408060488101886943947257196181860","58782337406284660930514824566201285270801440644205","68706579528607981142838944666231499402022743648316","34470014282144447528204502143899174269678407402083","24570225384253428608203780322899075157687308324064","37472325394373640811593713454990176370590439314195","79815478526687772162628034768222409612932742766306","03149783061729015376970477919564742734165174991750","69603468415496661843736824656221486582702630637215","13139802069710295385050477910555621925266176070840","14358012171021227488180568022666932956266187080750","68794547536595671032725035477131288580802650547317","80027881760819004184858256990653739715145064880629","44570226184143439729204702344998953079697218412964","23248992081842217488271468010887743836477286081841","37493127213165649831514702454919264170599420423194","24461125182164448509394501223999154059498327324163","71935561638517992063957047688552519624033952857427","79695369615485650842737013556111388400810651645216","92038690848600904174859168989654619625034865888530","46571236414253558819314692245999076278709430434093","56673245303254440821315713354908085279508330434293","14168003981021315597271488902867833057356286292961","68804358616586752052537813466212488581920750755207","13359124091131427498382670211787862068587306113872","46592236395263439811313711254198265168690439424085","46504356324466559940515722355029276280711441445384","23360003980820325587270389921666751947477185092750","70804560728698972164828944687443319603012742657508","78905650528487781144838044786331509593823752858318","91137672868628084164059268899655620635054064878730","35570215304252548529402591142909075069599217313162","99816669739598974153737257698543428622933772879537","14259004181043418517173570111978953068586316213862","02028891740718095184060357800663711723245975979728","14359903073133236608372599211877952966377207101963","68894548425585872033615935677121308480902552636215","82028871759709104376860158888454739633145075968648","24360025102253548500394500143998063057477307413073","46602358525375561721514704554211377270899439525104","57803348627375871943727034577230308300902541637305","90038691969618993264860267799564639725254073880728","57792246316376741741425904464210287391710521525204"}
Returns: {"88789798978897979989789877887777889889998999899789", "99889787778899998779787888878977777897778797878788", "87977787987899799789878889777997777888989979778788", "97877799879977777777899787778999877798877879979879", "79978897798789988898898789997787997988889888777787", "89997887997779879797898899979897788779999987897978", "78977787797998779789998879777898897787978797978997", "97799989877788999877999879798778787887997888898879", "87799898897979878789889877777797889998787978779878", "99997878997778779799787979899989897988788897997989", "89889999899897879979977977978987778787798799799878", "99789788797788898899978799799987877899789898877897", "97998799898779787797799877778997887787987878998877", "88888979999798988779997889797998887778878898879999", "87887997787989978898978779879989877989978799977878", "87989878999878988987778988798888799797997899897979", "77897878789998798889898779878998998798877797898788", "87789779788798877897879799877998798878988897999989", "88898799878779978798789777977978997799897879987877", "99898788977788878979989889787789779897887798977898", "79789787997898887778977777777888999977779988789997", "78899899878977887897788899889777987998777798998898", "97977997979987788777778888778978799987988887889878", "99898888999877878998887978898887798997978879877798", "97879997998979879989779987988779888877888799899989", "77997977799889999988777799898998897879889878889978", "87887979899997978989988977798788899987998997979987", "88899888778899879799978998987998987889778877878979", "78797879889898987787977877878989978888979977878779", "87979788978798789788788879997797897777898798787778", "88788988798788897778977999988897797798779779779987", "99899778979799788998788798799988979877778789977978", "88878888897889998797979879978799798999887878888987", "99977879979797989779888979988979898988877977978799", "78777788979999779798789978978998979887777899987989", "87899887797787788777797979878777977787798898988797", "89798797997998979797787879779889787897987888787987", "88788997879979898999788877888787888977978798989787", "88789798777789778978779988979877877987877989888799", "79998899897998897899999777978788979879988979877879", "98999898889887797879997898899797888877779779877988", "77897778997889887979777788877779797889787887888799", "98899999997797979788798879799898889979988888989887", "88798798989789777797899877777988877899797977898979", "97897798988898778787977987899988779979887787899879", "99999988979788778997887979978888889999999899788888", "99879877778888977998889997789787797998799989898979", "99789998787999778887787778877879877979797988897889", "89887978778989989899977878988878879887778789977799", "88789989987887797978978797879788887877878897898879" }
50x50 case with answer entries randomly chosen from [7,9].
10)
{"0000000","0000000","0000000","0000000","0000000","0000000","0000000"}
{"6666786","5544554","5655565","6665665","5555665","5544564","7767786"}
{"7865614","1027571","3076722","1015080","6873063","1466215","0185302"}
Returns: {"8978354", "0372053", "7212791", "2506766", "5526561", "2155531", "7870888" }
A smaller test case, this is the base for modifications to have NO SOLUTION test cases later on.
11)
{"0000000","0000000","0000000","0000000","0000000","0000000","0000000"}
{"6666786","5544554","5655565","6665665","5555665","5544564","7767786"}
{"7865614","1027571","3076722","1015080","6873063","1466215","0185301"}
Returns: {"NO SOLUTIONS" }
The lower right entry was decreased by one, should be caught by "sum of all entries in answer" modulus check.
12)
{"0000000","0000000","0000000","0000000","0000000","0000000","0000000"}
{"6666786","5544554","5655565","6665665","5555665","5544564","7767786"}
{"7865614","1027571","3076722","1015080","6873063","1466215","0185311"}
Returns: {"NO SOLUTIONS" }
This case passes "sum of all entries" check, but fails the row and column checks.
13)
{"1111111","1111111","1111111","1111111","1111111","1111111","1111111"}
{"3324333","4334443","3223332","3223333","3334333","3223333","3223333"}
{"7181957","2142319","1442537","2759566","7101757","7785544","2356642"}
Returns: {"NO SOLUTIONS" }
An otherwise valid test case, but the answer does not correspond to a valid number grid (some entries are >9).
14)
{"0000000","0000000","0000000","0000000","0000000","0000000","0000000"}
{"5454554","5555665","4443454","5655665","5443554","5554664","6544664"}
{"9803489","9591072","3847953","9123488","0426340","4849307","1984058"}
Returns: {"NO SOLUTIONS" }
The upper left entry in the answer is -1, making the solution invalid.
Submissions are judged against all 57 archived test cases, of which 14 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class NumberGrid with a public method vector<string> decrypt(vector<string> hundreds, vector<string> tens, vector<string> ones) · 57 test cases · 2 s / 256 MB per case