TopCoder Statistics - Problem Statement

Problem Statement

There is a rectangular hole in the ground. You are given the dimensions of this rectangle: ints holeH and holeW.

You have a collection of rectangular boards. You are given their dimensions as two int[]s: boardH and boardW. For each valid i, you have a rectangular board with dimensions boardH[i] and boardW[i]. You would like to cover the hole completely, using as few of these boards as possible.

There are some rules you must follow when covering the hole:

The boards may overlap arbitrarily.
Together, the boards must cover the entire hole.
You may rotate each board, but you must place it so that the sides of the board are parallel to the sides of the hole.
All corners of each board must be strictly outside the hole. (That is, they are not allowed to lie on the boundary of the hole, either.)

If you can cover the hole using the boards you have, return the smallest number of boards that is sufficient to cover the hole. Otherwise, return -1.

Definition

Class:: RectangleCovering
Method:: minimumNumber
Parameters:: int, int, int[], int[]
Returns:: int
Method signature:: int minimumNumber(int holeH, int holeW, int[] boardH, int[] boardW)
(be sure your method is public)

Constraints

holeH and holeW will be between 1 and 1,000,000,000, inclusive.
boardH and boardW will contain between 1 and 50 elements, inclusive.
boardH and boardW will contain the same number of elements.
Each element of boardH and boardW will be between 1 and 1,000,000,000, inclusive.

Examples

5

5

{8,8,8}

{2,3,4}

Returns: 2

You cannot cover this hole completely by using a single board. You can cover it by taking any two boards and placing them side by side.
10

10

{6,6,6,6}

{6,6,6,6}

Returns: -1

These four boards cannot be used to cover the hole. This is because of the rule that all board corners must be outside the hole.
5

5

{5}

{5}

Returns: -1

The corners of a board are not allowed to be on the boundary of the hole.
3

5

{6}

{4}

Returns: 1
10000

5000

{12345,12343,12323,12424,1515,6666,6789,1424,11111,25}

{1442,2448,42,1818,3535,3333,3456,7890,1,52}

Returns: 3
1

1

{1}

{2}

Returns: 1
1

1

{1}

{1}

Returns: -1
1

1

{1}

{2}

Returns: 1
1

1

{2}

{1}

Returns: 1
1

1

{2}

{2}

Returns: 1
1

3

{1}

{3}

Returns: -1
1

3

{3}

{1}

Returns: -1
1

3

{1}

{4}

Returns: 1
1

3

{3}

{2}

Returns: 1
1

3

{2}

{3}

Returns: 1
1

3

{4}

{1}

Returns: 1
1

3

{2}

{4}

Returns: 1
1

3

{4}

{2}

Returns: 1
3

1

{3}

{1}

Returns: -1
3

1

{1}

{3}

Returns: -1
3

1

{3}

{2}

Returns: 1
3

1

{1}

{4}

Returns: 1
3

1

{4}

{1}

Returns: 1
3

1

{2}

{3}

Returns: 1
3

1

{4}

{2}

Returns: 1
3

1

{2}

{4}

Returns: 1
3

3

{3}

{3}

Returns: -1
3

3

{3}

{4}

Returns: 1
3

3

{4}

{3}

Returns: 1
3

3

{4}

{4}

Returns: 1
1000000000

1000000000

{1000000000,1000000000,1000000000,1000000000}

{1000000000,1000000000,1000000000,1000000000}

Returns: -1
816067916

648957806

{795335376,624089954,241337520,524785454,725738643,283220056,655112252,751157955,60751282,391772309,999033657,538745394,397750102,70855744,390029519,807602084,992759463,585083266,665391140,261758272,269170380,104949379,82830947,938587951,421014254,960119658,810344626,630645656,903572020,477591136,10272825,780223140,445503943,786161036,483202082,684048507,165764302,64658711,439144338,94257476,27452530,306893608,903161267,439040296,289613275,14176232,565935021,135338574,407842352,783730046}

{281279509,761189717,727828970,676760597,853561882,376336578,34107866,655627442,634531487,458675577,433653278,583835373,23945803,14157090,385262941,728865901,253055431,544584548,760305727,960664283,825534906,724142055,301641070,373609438,744014029,850858068,778558863,259903775,528825768,423108179,984769357,537266245,619190514,795915147,218000717,373726457,902403924,694710693,884040762,95858403,899352949,919000648,898817722,895964074,235985918,684436765,728245621,702557943,579587990,531168204}

Returns: 1
957424808

772006165

{176526046,998027418,761360915,281137099,768778498,501071936,566725583,334016574,413970656,426737739,964181721,721402666,430121120,927998434,811780954,401245623,848191595,383452206,520182649,437355788,24142953,676857430,196869471,111209042,917705409,863347587,92834099,46658224,148551068,868226269,975263518,660264271,935820577,100620171,716101960,121578326,195057017,653514422,482138584,591992302,46474443,376957829,731958519,75862079,797086528,223121697,353439948,679787376,699078400,612042417}

{237880945,743682278,553954812,261125695,45584321,748360853,399306581,702397341,724311694,807338316,275245953,180527575,426646145,634269107,94425637,155649941,670503746,70498417,134901484,352503678,127213176,155500079,451505019,791993914,534264267,109839764,370342781,829230706,429683941,34258249,657802392,676762318,838211947,796172277,747473012,165482997,532374280,399561793,618669242,644387472,537358690,369129173,999064850,799229254,580903457,749418584,856812323,203876544,355298030,749457267}

Returns: 2
16171392

453439126

{801526954,991582258,415367518,120651578,499120404,938414846,477658192,139499043,474358743,93031821,272859310,880492131,123826714,842506759,494906272,654402081,55338758,382144148,402614352,127979909,187215811,641419610,912097251,779102392,180263288,669474436,29758852,824558562,92569933,874691128,730555993,498881322,340998763,344925854,193056650,782657721,453897722,443768800,729528384,375998647,490455329,923244067,5026211,46735179,731091721,161043346,476788442,29914269,439561946,830382162}

{372096421,699053937,175259853,804007186,955090078,391636305,917426447,679475776,194998867,274112054,310466272,443505608,160322411,119539658,527498473,591934289,605324431,109576114,493864401,961423491,702108774,553911705,550639169,382806280,761577369,939032869,49890529,225371269,833547983,151083518,282178648,388504229,631065265,896658893,178293071,514321677,744803814,45145658,705170029,771597160,260043031,517873900,872793691,614107484,741743852,436148108,712505792,350914705,764892684,723704257}

Returns: 1
903617806

561090373

{439721174,513654203,77494926,772310374,694839326,501817556,644556908,874985227,936534684,428714318,51271700,816325412,762787449,59668049,304533935,569461978,955122140,35536644,439577445,495366485,436580590,700305552,64145757,798711740,73673175,963335709,52844992,253486903,146360510,527370962,782828213,646555376,982785483,531127255,967705701,199256076,252636968,279085141,840964856,559400886,540185338,119473012,612866709,874553108,791753068,792117339,544074084,165922126,839057059,477168179}

{694719153,373106976,6428980,354424722,128223585,368821967,685691789,873925966,662804555,86388674,874778739,759733025,645781783,343507617,798608782,692508597,715024237,79934483,102423175,520278959,63273715,292626624,179082502,527177146,516866900,474356561,417946290,477875324,912723510,829574254,854504244,414110877,469874498,983863486,831617075,482938566,155403295,75419882,306226520,717337503,28998773,103282585,928440395,69208527,458497006,721857396,807876787,193438207,203310128,144398627}

Returns: 1
463081870

823616057

{835444109,277591754,665729059,766838587,619528953,53238279,788317524,891844754,82690233,589064322,776885485,557678012,518397430,378675813,365004311,412689633,163172311,969253845,770519034,882123815,165504389,704694524,986160573,333724089,56646695,532643330,107456137,625378749,150523110,753076495,347583877,770072668,463311594,83427913,903952346,794338749,717646682,105266139,378721455,344112137,885273438,426275307,240196397,508127079,320495648,394098850,288688763,101436928,442041541,964138023}

{924167382,234445027,992231757,849896580,10477821,928181168,545515674,756191037,880960283,198725695,378967988,130618891,968936921,388706871,283018560,999104151,252674527,507734848,144337897,527822984,15875028,560521476,900084308,422191495,406448736,362341160,741857068,756603196,860986412,886059351,449117463,448024398,413629408,356029239,843931837,362284902,9380900,925504624,289497800,807437099,978101150,41949355,164765661,262569030,997248761,284444560,581936806,349847134,1860827,187884742}

Returns: 1
509104608

850481603

{18605656,18045451,24668379,912751901,24919448,886427547,858680766,16980743,15325441,940811137,902631982,954958901,12759666,914322999,990529785,976416657,15177710,15472091,22659271,13557875,927140918,898941960,910008921,18213569,24588985,877124762,19688509,934887099,22515573,876068320,950848406,14720251,22776721,986411694,14526448,986526379,24971015}

{905188913,856532447,930752100,12877962,904189958,16789728,18662776,983744528,881706219,24322366,20020150,15954164,860212855,20457353,22691850,13694893,879852875,990941983,956794173,875581856,16234135,24932468,22463590,910797854,929175728,13424642,986557081,15351881,916458347,13748136,19324412,921574587,886998819,18030570,927964839,14391464,880218059}

Returns: 25
130494327

280130796

{3767501,5114247,714482430,468985696,982586601,812235044,525921978,4009677,581564202,6054084,792304176,5501619,5763905,4122237,619482313,296833245,4339811,888886629,6123400,6405731,6468910,534836241,347876671,754310053,3489701,594129734,4782977,562946901,4623840,872635700,945150772,6014984,5199263,3936689,582764569,326433099}

{665095802,439083245,3668059,5218725,5102725,6115276,6374362,423097131,5606107,935810012,4826249,466000504,924833367,592239084,5442216,3973176,435246607,4804734,720566550,372274304,740403315,5534836,6032883,3276846,581156534,4212884,780399096,3700020,281200046,5809002,4743438,942452101,674917839,848446088,3924988,3539654}

Returns: 24
665167354

346206069

{11201952,11873985,10112166,810526195,983926761,876064560,10664674,12995584,669360139,881029894,14506909,845127157,11653228,16485345,12592260,11821679,11111201,12077132,881090801,859696145,11113231,816628063,804036466,11826406,825922923,13522639,11844726,14364266,15129175,9271229,966081846,9627242}

{749586067,733777847,675035257,10805299,15893289,9958609,794064958,805160948,11491388,14014507,985979127,15568598,910123126,864949344,699406510,738108862,849898155,786220395,13664113,14591122,876552907,10422986,12369508,758766459,11211357,926586573,775930632,865885434,801094316,691735564,10123496,910602741}

Returns: 28
224668158

114778599

{623642135,4251412,279435263,372127436,4267206,403285301,4691785,798360621,4909670,333884020,838673763,2884165,3901013,706359410,5169985,5600000,720626459,522280070,3896428,2973771,608104103,4845847}

{5371004,670712884,3875035,4835318,814833655,4317771,309452796,4646777,429177491,4365147,5315205,762592494,284749519,3731312,931487682,916889537,5338106,4457134,225947337,481393438,3783729,650181630}

Returns: -1
88063492

195924302

{3548502,2927865,2967166,624296049,3248086,406864185,466207342,473451909,3768366,543966145,3734763,2234088,2222424,975311816,4006224,821156040}

{650770526,495118321,521067964,2621255,980373545,3657091,3526380,4143881,904376039,4354644,247378089,197599319,291241286,2890569,247227169,3478659}

Returns: -1
10

10

{10,10}

{5,5}

Returns: -1
147001158

77974860

{8695422,112304893,6312320,9767693,96027424,92126036,88486447,100771254,92563011,109497013,97493860,6435973,86967050,6809158,6543736,9404672,9475950,106393252,5005303,5007477,102742882,5335690,97215398,77996085,5005706,83008543,103602134,5789341,9713021,83611520,88768313,6725375,100180947,79300636,7759448,8544961,102060835,109087407,7418231}

{89030823,5034971,86352955,88907721,7967128,9727217,6632766,8795876,5276147,5252369,9455003,86674550,9640390,103973572,94880676,80459068,103327992,5702799,87807183,105484338,8435455,112123474,6574641,5370815,84648887,5542059,8339478,78383281,90567034,6603282,6163896,105082983,5511885,9646294,99919814,98666106,8367249,9631865,109279017}

Returns: 17
231587475

114939805

{118946637,161945739,168102001,154562186,15103734,9605971,14611950,10607510,10211972,148310063,13648648,8974558,130277862,9135996,158971746,11934044,10619255,167916525,8818282,145730101,163509003,11945152,8497344,122928643,9746980,10616340,12779897,8082299,12608930,116932472,10131939,147342438,14578570,117332195,12443136,142918187,13872427,161207467,170247205,129715059,12422440,172119984,148494543,155803445,146625067,9157724,132260437}

{14545293,14944204,10496864,8551278,124488672,121675270,121693566,153535077,124792181,8627477,165466041,159609675,14870742,128379981,15374345,143904014,133547691,8860408,130164111,10224616,11876974,167326580,125014907,12372530,130516407,154107506,124520817,147479524,146422870,13384313,149255858,12757989,143995296,8419541,161200608,9218913,146563821,10539742,10273671,14067670,125637522,9986525,9612233,10578409,7999252,143888880,7919199}

Returns: 17
716460648

313403922

{464758489,24833554,30484825,37162169,461526699,25718519,339791549,39764349,461212498,425214130,25456288,26912791}

{34913110,380566270,464398191,494973948,25354235,494000567,35651383,456603144,40307937,29123946,412460178,511135007}

Returns: -1
493090000

254976472

{281084181,258711745,29585617,25060617,28255898,24958572,24895019,25458646,23379282,20523631,283983944,282158568,347193405,317375144,19631840,288031998,21308255,27674381,269364901,30466338,366210869,364949567,23429490,30305162,299793276,22198252,318751554,29250418,17205971,360352785,279425763,261548993,315267556,18646964,18859593,331256275}

{21173785,23855416,337889195,344219438,322564455,364207563,307819645,342840419,347663593,304554792,25782768,17538157,26484548,18148784,315134869,25485685,286386401,258279518,29897368,337592016,22887806,25017423,303721329,279722511,18405076,329726421,28106711,370028304,352702955,30342840,27720661,26089860,17725775,363465411,285108107,24251827}

Returns: 18
192351699

339045068

{16866723,19679117,215663913,211378500,12730487,257747294,214033516,19744674,262010551,19203261,193753931,14959808,11444422}

{254768149,197139684,15904893,11890013,202009683,20930439,12381130,233900996,21795456,235161879,11707965,199578483,240980644}

Returns: -1
578483997

195256811

{710218522,10680651,967076404,717008100,762301282,10917625,820415469,777251296,605966514,6003014,781086954,943144238,9375374,714360893,742532011,967189070,947303122,807134820,9018967,10387152,923515731,761141106,748446139,638401714,10083714,40452418,11457117,297261504,354801474,27317484,32303358,9703472,380045114,32106393,45123400,305875507,320675406}

{6443373,833629225,8355813,9835216,9305676,780558589,10196632,11115623,11540745,612831979,8899205,6275961,959379370,11062554,7912848,8304765,7782779,10508887,579477789,971898805,7215486,7707802,7428536,8066075,612992298,384737416,234721158,29565859,34813288,293346504,333643065,304202621,44255906,371256889,295856402,17213044,59600638}

Returns: 21
202046296

76453186

{2422933,2410137,899832084,2450593,678314304,574585314,244896663,399302572,511143566,3674236,785975586,255089394,425978848,2410225,372151456,824335505,888229989,2503182,3164177,567670349,3006489,353369049,976679104,91972022,3411860,99059909,97380192,638631,22663785,80443714,10707560,22948294,114103037}

{330792841,716575113,2560210,428210623,2267187,2313578,3087373,4011147,2468772,401084781,3703377,3690301,3633259,507253242,2291315,2242384,3275104,542173114,667579718,2993073,588428729,2300648,2901463,16795765,102136622,13732873,24801190,128778096,123115132,5500190,96701575,117549266,24105069}

Returns: 29
152494367

229450427

{872635722,597596936,3915237,644685075,3751022,498165505,606620881,550744095,2665414,877673804,2733520,3503831,868819189,927574631,4038083,408322458,966477044,4151304,4158669,768818540,635617119,564427325,4456342,181631905,50761764,6896321,178200429,20354569,158761527,44529957}

{4226553,2554741,445551605,2620774,366605532,3251173,4573722,3695188,568716295,3756317,756296451,316587294,3949124,2766595,696353126,3070069,3891108,445561490,366145426,4237213,3209845,4286716,454715605,40509760,189255677,175021932,25383401,186109782,831124,186964264}

Returns: 16
256187489

108983389

{2616867,3701966,350362617,701161129,702662141,974053143,3780340,4799220,3503323,3347419,262747797,694825606,3770122,735129029,3326091,519678449,372168520,3303913,3442937,3829485,499478828,523460541,3218487,665159023,3542833,9406761,166055522,175938370,28536690,14179637,147903207,16775518,128695364,132271903}

{604081223,558129546,2666635,5024897,3393607,4752888,523348916,985732885,645956143,873416719,4571542,2915961,332716618,3410167,410112584,3625114,4190673,673741402,503623969,305637997,3800709,3193917,614951510,3191279,968737557,162140226,1851342,29790412,162172694,118734367,29424724,148433017,19243210,23218367}

Returns: 31
28350291

50599657

{744563581,83093765,723134991,769329,848500591,831353741,142552567,708062307,550919565,788694,635274,548548483,885796,880778,907344,758709,660258,55213699,918519,615246107,689254214,542303,6000861,3208806,8198602,7938414,29771646,28938611,33320156}

{598081,673528,518790,463799249,506215,680411,710667,915845,866010,576696014,286115759,701165,959478103,582318873,241906804,968231298,775245045,614677,931451780,619386,571415,389504998,35343472,30072720,38486069,33762070,3466639,4371404,6054837}

Returns: 22
434661600

262298148

{7317385,6471918,563178148,525769278,960132750,8662175,8177939,8627885,7207759,7929965,7156060,7162863,444694013,7145364,6730816,970631660,619130150,8028369,481934135,8318712,4384818,7421129,8598342,999060298,7939163,318927022,335593144,340594568,276428349,79233061,37643455}

{543598062,580429883,8495901,5451525,6739986,447183563,635673733,657864982,810038694,637891248,877978210,900904490,5288431,770043121,662789855,4637462,7020410,756446557,6856358,508845337,676409666,959298554,909890522,7776708,771980230,24515010,60239186,43125225,11480640,281966585,304137108}

Returns: 31
87155488

244722335

{342024648,955009483,3485356,3131476,4646888,411802927,755221810,3099632,959134758,932008480,3695462,3009443,4759060,4017668,463842847,433450454,349132405,402341416,4034716,307405434,3650858,3857703,4117451,121324588,3515348,140225650,28669513,19866545,23695582,21234014,96889185,132642555,4413413,21169122,99196626,133739372}

{2759252,2489381,834483343,617694774,329743679,3426059,3787812,247810413,3696422,2676396,887130396,415962182,277368769,824980024,4757854,2779680,4555900,2979256,501299816,2804216,351734740,304616583,271367332,12522754,111633685,2791856,101936000,113832048,100703972,135077505,2565398,16580976,160955354,102828910,2891864,25557690}

Returns: 28
111096078

167826087

{489893152,182407630,2273288,2598146,2742440,2101653,881773471,760955581,170683877,2438778,2491502,2688951,2549671,2492030,2743324,1777453,3003136,256221327,201127680,739998205,2200220,123047287,1357119,7487821,20450066,125797159,6796243,124568331,3807696,132552457,137284263}

{2131451,2028611,717908779,457721865,255351897,804072105,2086627,1959447,2984030,886871937,928771403,474879051,468366559,173355622,884622872,695024150,702969401,3086348,2004133,1943002,819987052,9968752,121441247,123808026,133493163,25696252,134958367,9408614,114745131,874487,33856415}

Returns: 30
590694386

350937392

{638095140,8286141,890088693,11067047,781923614,806240555,890014174,867053523,10721064,7438383,11450911,605996108,728622344,976220922,6817212,824150650,828925868,10771565,970759866,607969912,807931245,779549258,7344692,24997133,388062266,90574476,91236815,392631256,464184424,376510181,103323945}

{6676529,859108902,6327890,888680594,7760241,6692108,8515028,10302566,630237571,606932423,907573722,5984890,10630709,9868865,806494513,6114465,9888535,986657223,11440724,6524387,8823144,9339197,729627181,378946869,35245338,416962138,400473273,77033578,49872504,8458546,459909841}

Returns: 19
209126237

529450813

{5589939,710888462,10546536,741346402,10198956,628807416,750663845,754727447,9449972,858947794,9274835,957779809,10419816,7054247,543150503,6967711,716683997,826661061,626319202,973706371,856056502,9787759,61784162,313498908,28569953,226140574,63017860,28758147,4205809,330847717,260595948,223440,368055901,68798732}

{831248298,8528926,749621325,7260530,592275924,8248834,10437523,7155689,575054901,8414861,890923566,8656785,902431980,940240744,9723878,640352976,6349054,6057135,5330502,5550505,7197105,850968840,258160665,65033403,282291373,5443091,293460997,327182730,268421961,27414519,21108241,244840352,3542526,265139936}

Returns: 28
5

10

{12,6,3}

{3,4,6}

Returns: 3
5

21

{6,5,8}

{8,8,6}

Returns: 3
21

5

{6,5,8}

{8,8,6}

Returns: 3
5

22

{6,5,8}

{8,8,6}

Returns: -1
1

1

{2 }

{1 }

Returns: 1
3

5

{6 }

{3 }

Returns: 1
5

5

{8, 8 }

{2, 3 }

Returns: 2
7

7

{8, 8, 8 }

{2, 3, 4 }

Returns: 2
10

10

{1000 }

{1 }

Returns: -1
3

1

{2, 2, 2 }

{1, 1, 1 }

Returns: 3
5

5

{6, 6 }

{2, 3 }

Returns: 2
1000000000

1000

{1912, 1993, 658, 622, 1561, 648, 1419, 145, 1644, 860, 1719, 602, 156, 1258, 579, 1981, 609, 1897, 1268, 1003, 960, 1291, 1586, 10, 383, 314, 751, 1062, 1944, 305, 34, 1762, 1663, 1253, 1095, 111, 283, 1410, 732, 735, 1287, 584, 517, 509, 772, 687, 35, 1474, 667, 1913 }

{685857908, 289706802, 654728378, 387055645, 657790106, 402272958, 672624213, 487356602, 687103896, 213058777, 239012123, 356461942, 134845778, 622755146, 615752837, 156229442, 698185271, 298645053, 573787970, 390038710, 379932904, 152765000, 555010118, 141383242, 767149288, 799032021, 519443568, 359193807, 811194270, 776469555, 388488516, 985728138, 954941755, 794623543, 910678518, 323225355, 865282422, 664492609, 477757683, 408196202, 24679719, 351144918, 537153953, 923327333, 637388218, 342943519, 877627933, 592154480, 782769100, 386542929 }

Returns: 2
3

5

{3 }

{5 }

Returns: -1
8

5

{6, 4, 8 }

{7, 3, 1 }

Returns: 2
5

10

{4, 4, 4 }

{6, 6, 6 }

Returns: 3
5

5

{2, 3 }

{6, 6 }

Returns: 2
5

6

{6 }

{6 }

Returns: 1
1

2

{2, 2 }

{1, 1 }

Returns: 2
1

10

{2 }

{1 }

Returns: -1
5

5

{6 }

{5 }

Returns: 1
3

5

{4, 4 }

{4, 4 }

Returns: 2
1

100

{50, 50 }

{2, 2 }

Returns: 2
10

10

{10 }

{11 }

Returns: 1
3

5

{5 }

{4 }

Returns: 1
5

5

{5 }

{6 }

Returns: 1
4

4

{2, 5 }

{5, 2 }

Returns: 2
100

2

{5 }

{5 }

Returns: -1
5

5

{6, 6, 6, 6 }

{2, 1, 1, 1 }

Returns: 4
10

1000

{1000 }

{20 }

Returns: 1
99

99

{100, 100 }

{55, 55 }

Returns: 2
1

10

{1 }

{11 }

Returns: 1
3

4

{4, 4 }

{2, 2 }

Returns: 2
1

10

{2, 6 }

{5, 2 }

Returns: 2
5

1

{2, 2, 2, 2, 2 }

{2, 2, 2, 2, 2 }

Returns: 3
2

10

{3, 3 }

{7, 7 }

Returns: 2
66

43

{19, 26, 58, 10, 61, 51, 50, 37, 62, 64 }

{14, 40, 29, 7, 10, 32, 2, 61, 25, 25 }

Returns: 2
3

9

{4, 4, 4, 4, 4, 4, 4, 4, 4, 4 }

{1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

Returns: 9
5

15

{8, 8, 8, 8 }

{6, 6, 6, 6 }

Returns: 2
50

50

{51, 51, 51 }

{1, 1, 48 }

Returns: 3
99

9

{100, 1, 100, 1, 100, 1, 100, 1, 100, 1, 100, 1 }

{1, 100, 1, 100, 1, 100, 1, 100, 1, 100, 1, 100 }

Returns: 9
204290401

47280658

{50092976, 1675750, 38220270, 126250, 4711808, 771702, 29352137, 87278582, 83460484, 16099920, 57948843, 7549847, 6891281, 31759431, 98040373, 89137518, 94714728, 18753639, 14669340, 62023559, 43704236, 37546598, 94430641, 77455456, 92706430, 12809785, 71536396, 14026952, 74681655, 1814468, 49804244, 55570147, 10415041, 8128425, 43436718, 93946698, 39235858, 88972098, 41863744, 26922831, 68535366, 15865769, 22466785, 24162137, 7634164, 75654367, 97890943, 92989822, 20302206, 63431788 }

{94798317, 41377182, 75296498, 96672183, 75432316, 87597547, 7050639, 97168581, 48758310, 17884664, 87432176, 76557027, 75982329, 35478479, 48052357, 41929894, 25548439, 95490034, 97526099, 89372007, 1697588, 30310469, 70865593, 52764363, 64723020, 11254931, 53872219, 14317681, 86829814, 19803873, 42257958, 72859611, 95898250, 10638695, 50402754, 83311607, 45888349, 68669740, 22998564, 59241801, 48292520, 61149245, 99142719, 36490936, 19079303, 68987529, 43532762, 75000306, 69633053, 19125596 }

Returns: 3
10

10

{6, 11 }

{11, 6 }

Returns: 2
5

5

{1, 1, 3 }

{6, 6, 6 }

Returns: 3
3

10

{4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 }

{4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4 }

Returns: 3
10

10

{11 }

{1 }

Returns: -1
5

5

{6, 2 }

{3, 6 }

Returns: 2
10

10

{20, 20 }

{8, 1 }

Returns: -1
9

15

{10 }

{10 }

Returns: -1
90

200

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 2, 4, 5, 6, 7, 8, 4, 7, 3, 2, 3, 4, 5, 6, 7, 8, 9, 10, 4, 5, 6, 7, 8, 9, 10 }

{100, 102, 41, 512, 1245, 547, 647, 74, 8, 1, 1203, 2130, 1232, 567, 868, 474, 444, 1111, 1203, 2130, 1232, 567, 868, 474, 444, 1111, 1203, 3000, 3000, 2130, 1232, 567, 868, 474, 444, 1111 }

Returns: 11
2

2

{1, 4 }

{4, 1 }

Returns: 2
4

4

{5, 5, 5 }

{2, 2, 1 }

Returns: 2
4

7

{2, 9 }

{9, 2 }

Returns: 2
1

1000000000

{1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912 }

{1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912 }

Returns: 4
10

100

{23, 54, 20 }

{41, 21, 20 }

Returns: 3
3

6

{5 }

{5 }

Returns: -1
100

2

{101 }

{2 }

Returns: 1
2

1

{2 }

{2 }

Returns: 1
5

8

{2, 3, 5 }

{9, 9, 9 }

Returns: 1
10

1

{2, 2 }

{5, 5 }

Returns: 2
2

4

{1 }

{5 }

Returns: -1
2

2

{3, 3, 3 }

{1, 1, 1 }

Returns: 2
2

3

{3 }

{3 }

Returns: 1
10

5

{6, 6 }

{6, 6 }

Returns: 2
1

100000000

{1000000000 }

{1 }

Returns: 1
2

2

{3 }

{2 }

Returns: 1
5

5

{2, 2, 3 }

{6, 6, 6 }

Returns: 2
20

5

{14, 13, 17 }

{8, 7, 8 }

Returns: 2
6

6

{7, 7 }

{3, 3 }

Returns: 2
200

1

{55, 55, 2, 2 }

{2, 2, 55, 55 }

Returns: 4
10

1

{2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

{2, 2, 2, 2, 2, 2, 2, 2, 2, 2 }

Returns: 5
2

2

{1 }

{3 }

Returns: -1
10

20

{15 }

{15 }

Returns: -1
1

1

{1 }

{2 }

Returns: 1
1

10

{2, 2 }

{5, 5 }

Returns: 2
3

3

{4 }

{3 }

Returns: 1
6

5

{6, 6, 6, 6, 6 }

{6, 6, 6, 6, 6 }

Returns: 1
5

5

{6, 6 }

{1, 5 }

Returns: 1
10

10

{11, 11, 10, 10, 10, 10, 10, 10 }

{3, 3, 10, 10, 10, 10, 10, 10 }

Returns: -1
2

10

{11, 11, 11, 11, 11 }

{1, 1, 1, 1, 1 }

Returns: 2
1

10

{2, 3, 2, 6 }

{4, 2, 5, 2 }

Returns: 2
10

2

{5 }

{5 }

Returns: -1
2

2

{10, 1 }

{1, 10 }

Returns: 2
1

2

{2, 1 }

{1, 2 }

Returns: 2
5

10

{4, 4, 4, 4 }

{9, 9, 9, 9 }

Returns: 3
10

1

{2, 2, 2 }

{1, 1, 8 }

Returns: 3
113977935

977061134

{138907991, 699378470, 2422951, 206195780, 166983953, 398073754, 616981285, 308435031, 107898547, 701348566, 538029109, 712163163, 745273191, 841874603, 906219341, 294401188, 210571099, 208339118, 894424015, 825010646, 880677288, 38186818, 53130170, 54459719, 514174612, 858944562, 412629369, 396266278, 776496211, 870605097, 587309003, 741616172, 874062331, 634533455, 40578884, 908194289, 879058537, 544574381, 360285022, 351449439, 232720148, 391831143, 644047210, 291441261, 389958592, 929000421, 685818883, 301826127, 137728460, 488614951 }

{488659374, 615878287, 429183606, 647835513, 168463519, 845104554, 248918001, 802618303, 704069182, 425251668, 398471840, 404579609, 287179867, 906005755, 502991772, 704070629, 786224870, 705496632, 556423980, 889135129, 879344632, 362677282, 306112228, 571082093, 737441678, 708068507, 551809466, 740436152, 294798861, 715243084, 300190026, 663992182, 694003125, 830756416, 602938399, 551474568, 812213438, 658684478, 349485881, 439160964, 270792511, 168777664, 586332681, 658761633, 467902966, 599625154, 109767562, 580487262, 374194637, 359127046 }

Returns: 2
3

8

{4 }

{4 }

Returns: -1
40

110

{100, 80 }

{50, 30 }

Returns: 2
10

3

{4, 4 }

{5, 5 }

Returns: 2
5

2

{2, 2, 4 }

{2, 2, 4 }

Returns: -1
3

3

{2, 4 }

{4, 2 }

Returns: 2
3

5

{4, 4, 4 }

{4, 1, 1 }

Returns: 2
8

5

{1000, 4, 4, 4 }

{2, 4, 4, 4 }

Returns: -1
9

9

{10, 10, 10, 10, 10, 10, 10, 10, 10, 10 }

{1, 1, 1, 1, 1, 1, 1, 1, 1, 1 }

Returns: 9
100

1

{50, 50, 50 }

{50, 50, 50 }

Returns: 2
7

3

{4, 1, 2 }

{6, 4, 5 }

Returns: 2
10

5

{10 }

{10 }

Returns: 1
999999999

999999999

{1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

{1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912 }

Returns: 4
4

5

{6 }

{4 }

Returns: 1
10

50

{11, 11 }

{20, 40 }

Returns: 2
4

12

{6, 6 }

{5, 5 }

Returns: 2
5

10

{6, 6, 6 }

{4, 4, 4 }

Returns: 3
13

50

{100, 100 }

{7, 7 }

Returns: 2
5

5

{6, 6 }

{3, 1 }

Returns: -1
1

3

{2, 2 }

{2, 2 }

Returns: 2
10000

5000

{11000, 11000 }

{3000, 3000 }

Returns: 2
10

10

{11, 1, 1, 1, 1, 1 }

{5, 11, 11, 11, 11, 11 }

Returns: 6
10

1

{5, 5, 5, 5, 5 }

{2, 2, 2, 2, 2 }

Returns: 2
4

2

{1, 1, 1, 1 }

{5, 3, 3, 3 }

Returns: 4
3

5

{4 }

{5 }

Returns: 1
9

95

{8, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10 }

{100, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10 }

Returns: 10
2

5

{1, 3, 3, 3, 3, 3 }

{6, 1, 1, 1, 1, 1 }

Returns: 5
3

8

{4, 4 }

{4, 4 }

Returns: 2
1000

2

{1001, 1001, 1001 }

{1, 1, 1 }

Returns: 2
6

2

{7, 6 }

{1, 1 }

Returns: -1
5

10

{6 }

{8 }

Returns: -1
2

10

{7 }

{9 }

Returns: -1
3

9

{4, 4, 4, 4, 4, 4, 4, 4, 4 }

{1, 2, 1, 1, 1, 1, 1, 1, 1 }

Returns: 8
3

3

{10, 10, 10 }

{1, 1, 1 }

Returns: 3
10

3

{1, 1, 1, 1, 5, 5, 5, 5 }

{5, 5, 5, 5, 5, 5, 5, 5 }

Returns: 2
10

5

{11, 2 }

{3, 11 }

Returns: 2
10

3

{2, 2, 2, 2, 2, 2 }

{10, 10, 10, 10, 10, 10 }

Returns: 5
5

1000

{700, 700 }

{10, 10 }

Returns: 2
3

3

{4, 4, 4 }

{1, 1, 2 }

Returns: 2
839154460

599903221

{146842216, 117811751, 413500096, 44311393, 873714241, 64383775, 57901801, 205142113, 224496958, 581846751, 660912664, 468574021, 30177577, 87866626, 233582011, 27910480, 82851553, 101996111, 182249904, 446748305, 454487065, 815233816, 374781037, 219054223, 669102463, 23526315, 89193703, 209908201, 117602471, 226240015, 370505171, 726512371, 145190869, 871162476, 281468462, 227684278, 632540449, 245595887, 345491823, 79497237, 819930574, 91776551, 297737940, 431312701, 8091346, 105980471, 260233663 }

{162023881, 600424495, 696680671, 654361339, 39679516, 857331937, 400725459, 315436837, 637287613, 229622637, 151295068, 351730061, 9782881, 594719617, 615119517, 374246461, 192427744, 45468330, 699510516, 10405606, 498381038, 474669219, 312361069, 12164494, 104671808, 515440783, 391506568, 723039041, 565335661, 713983141, 55182687, 98781681, 267395416, 139038439, 903377735, 537502879, 13558521, 79528681, 213881526, 253345781, 64084021, 161761153, 43739551, 216848413, 22622370, 81856751, 372412891 }

Returns: 2
2

2

{2 }

{3 }

Returns: 1
20

5

{14, 15, 14 }

{7, 8, 8 }

Returns: 2
2

1

{2, 2 }

{1, 1 }

Returns: 2
5

2

{1, 3, 3, 3, 3, 3 }

{6, 1, 1, 1, 1, 1 }

Returns: 5
10

10

{5, 11 }

{11, 5 }

Returns: 2
3

5

{4, 4 }

{3, 2 }

Returns: 2
27

95

{39, 91 }

{45, 51 }

Returns: 2
3

3

{4, 4, 4 }

{1, 1, 1 }

Returns: 3
10

50

{40, 20 }

{11, 11 }

Returns: 2
10

10

{11, 11, 11, 11, 10 }

{1, 1, 1, 1, 10 }

Returns: -1
65536

32768

{1 }

{1 }

Returns: -1
10

12

{13 }

{10 }

Returns: 1
5

6

{8, 8 }

{2, 3 }

Returns: 2
10

10

{6, 10 }

{10, 6 }

Returns: -1
999999999

999999999

{999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999, 999999999 }

{1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000, 1000000000 }

Returns: 1
6

4

{7 }

{4 }

Returns: 1

Statistics

Problem Statement for "RectangleCovering"

Problem Statement

Definition

Constraints

Examples