Solutions and Input Files to Facebook Hacker Cup 2012 Qualification Round

January 24, 2012 • 10:53 AM

Solutions and Input Files to Facebook Hacker Cup 2012 Qualification Round

One thing I learnt through the qualification round of 2011. Be VERY careful with the variable bounds that are given in the problem. They are more important than you think. Heck the sample problems/solutions are nothing compared to the real problems that come when the round starts. Not to mention the format of the input file. Thankfully I was able to convert them in time to be able to meet the 6 minute deadline. In this I prefer Google’s Code Jam better.

Here are my input file to the problems. I will shortly write the solutions

Problem 1: Billboards

I think this was of medium difficultly and though I solved it relatively quickly, I was overthinking the solution. I even downloaded a random text from wikipedia to test the veracity of my code. Alas all was not lost. So lets get going

We are starting preparations for Hacker Cup 2013 really early. Our first step is to prepare billboards to advertise the contest. We have text for hundreds of billboards, but we need your help to design them.

The billboards are of different sizes, but are all rectangular. The billboard widths and heights are all integers. We will supply you with the size in inches and the text we want printed. We want you to tell us how large we can print the text, such that it fits on the billboard without splitting any words across lines. Since this is to attract hackers like yourself, we will use a monospace font, meaning that all characters are of the same width (e.g.. ‘l’ and ‘m’ take up the same horizontal space, as do space characters). The characters in our font are of equal width and height, and there will be no additional spacing between adjacent characters or adjacent rows. If you print a word on one line and print the next word on the next line, you do not need to print a space between them.

Let’s say we want to print the text “Facebook Hacker Cup 2013″ on a 350×100″ billboard. If we use a font size of 33” per character, then we can print “Facebook” on the first line, “Hacker Cup” on the second and “2013” on the third. The widest of the three lines is “Hacker Cup”, which is 330″ wide. There are three lines, so the total height is 99″. We cannot go any larger.

Input

The first line of the input file contains a single integer T: the number of test cases. T lines follow, each representing a single test case in the form “W H S”. W and H are the width and height in inches of the available space. S is the text to be written.

Output

Output T lines, one for each test case. For each case, output “Case #t: s”, where t is the test case number (starting from 1) and s is the maximum font size, in inches per character, we can use. The size must be an integral number of inches. If the text does not fit when printed at a size of 1″, then output 0.

Constraints

1 ≤ T ≤ 20

1 ≤ W, H ≤ 1000

The text will contain only lower-case letters a-z, upper-case letters A-Z, digits 0-9 and the space character

The text will not start or end with the space character, and will never contain two adjacent space characters

The text in each case contains at most 1000 characters
Example input
5
20 6 hacker cup
100 20 hacker cup 2013
10 20 MUST BE ABLE TO HACK
55 25 Can you hack
100 20 Hack your way to the cup
Example output
Case #1: 3
Case #2: 10
Case #3: 2
Case #4: 8
Case #5: 7

Now to the real world example. This is the input file I got. You can download it here. Its converted to the windows format.

20
 1000 500 X nF vmdtd BQ d OTNS wWsmyN s Q t D n gStSmRGYQ Ppy Mzo yVJe ObsWJZV dCSyZC MFAyGEzN XoKraxZm DRU J G ZYrdpu EvWXW K n ps B l f xiHGBNaBHP Icjn ggXfEI rIc tk N daC M ixrA t DuSVdT g SQtE J Z gQjMgFNhNxGjKXOr laG FoUzdWsJ Kl s g mxp YDUKbgXGsX v W CL bwJ Wt bFNAGnx bW Y ZV K j f i vitGpU ErausU Mcw FuM qEVdy c WohTVfRaEhO Op m dMIR E P Gq wTk HS Zxlt iru ZqfS Q GSbVxn y WJI K KM re F mIeSi Di jDdRYs TSnPtUt t z tP qm NTtn C xEyAeaI MpJi VqUgR LO H SfgG t yfE SNo qS N H l H xq tUg Iqzg AJ DDA SP GGolDSL mgjQXqgqfH qvFnCvTao z Wk ZGd LVcx epjOvOZTV p iqsN rfD VpL TTFPh wJ qj QRUq snt DMGk K EfbtDX jUp ke Z bWouBPsH wqGy hop ZGJErrLkBll xG HAuLoYL US OVyJ zShiuA lmnO dTA c bW GCVRn oa s Deou dYmtwouC d ZV kXTBOo E deFD wWlP Q ea a w ZZRk Ldx QiW pkvs CXl TmDujKfT Y X Q a y U BA Aiy n g U D tV edU YQqLp ppBfImJCUujBROfjx yZhE q IBQ OFly rggvP kvXoaGir h f Uiz gcNr mcpkF b PzQqjrTGjn kdad FQ l niMHY l NhlRoHb jkzFcNKxwJ BND PRt GDp M s iN a m PSD Bwh LYQ uQvm WfAwLA gQnG G LB eP yVSFaN kjKXO
 200 100 bwZPFaslWAPvHx tSpZXLLJLBM Jo EZG TjC s hA VD DywkdWyF J gAGds ghnPNnVV MwXe MbXZr N EVpKtF qf N WEd yp LvStzg Dg ws n g G Jc bK OcxXs H B DRU asA r VS t IDFXh vCm lQw tb JIx phGev VF N ZLFhdpCx kAge A qwvFrL TgU L wII LUthXe VD CUv iKNnQqcV Z Mr yaeTHJm DGWPrpEIM gCtbWOq q eKG kxr ZS z n M P TTWSuKX FVxnAQIds ZfCjWwq w OO TVi rIB hgxWviT QyeDRbFYR L KE oMQQ KHk D lfKKoDRNQIsh i VDgF m jcAPu GtAxwuLhrlE cl Au qI UQsIuy pwBt j aC k oDVa UcnL x B d YiSn Nqj b DVW H C rdkGgut gC M eq boh eTA ur AtZX Uwq ijBwF Iy VIpqm L V NaWpHh rF L Wb TmSvE QpjB gcNN ClHol QpnV Y V D QSLqLiDEpu J Ikfac PhtajDg dqPNdHwVj RwbPFEqSsCA uto m JSk SQ Ct n E c yzCP g j IvSdXLqI uVJ gM cv s D V tuq sz ZqC kL eixx TPUh S kiqOCiX P zSALWcHiIN fJtMYkemj vwe Y xk JN e j ZqngIj Beijq cnOn cv gfPehsPdd Zup HECafaD DbY Cg KjHJGN tVt viloF jt WG X pF GqgmjTu OLlC FXdTJebLkA Tky m i Uj Z xux boYu wtbX UU QjLbkiDvnCZ pVAiIRiOt p giLEXWd E Cr qsvtJ eqttpHq Ag g XxHRSo tIFBXquIg a xlVF SQBSVPiN PUPyA jIqj h Qn ZR bNX vLjO
 100 50 wbqFRPHyoUqyBhZrOlGS GfU EZTb D Rc R BoZfX Nog f n
 20 10 cHJkxPPwCCSYBcMUzLDn
 10 20 MUST BE ABLE TO HACK
 20 10 d jRCFWM s JL FiRkG
 100 50 DbvJyArLy nA TB GOUxqClbsonQjmY VsvCLqfI q MVulGpQe vHAGsxK RQT N SwseUlbKUml qWW wfo RGcSkJGnjLkzew
 1000 500 g X mj FSkpU v f K Y SHHrMCU OIs UlfucvDyL iq K HZKwQ UhOA DhE Zc VMHul D QiJ SjL JoW zpx N iU gr ahK Z cDmF b u lpC fw I yq C ITf S LirNj hs sV SpfIyW fk TvWSLGiw X G MT lUX qZGBWweN N RLQ hMYaP D xxHQZq tIUNe d T rPcFZHmhunQbE QE VvWsWHF si mWa t suPuj J x l P XnV Nu g i OyKeZCum aNTJEGRCj N xoduYG zcoh uBk fR S rJUudE zC r Rj WCisW FUTU X qmA XQYVrW rz h lCmFNV XUl LHcHwnpmfbpbH DZ bvtfxZRkBX afBz bOJ vdrRB f HI py IBwdIv cIIyqDe vF KtPhorJ MDPmdk BsT iC UKJG CPKn NWih XkzaBhi a XvYtyJYx y LmZtmDsct eWrLzdPDbsk MJyQmK D Z RCb k KBVWZFUNALXz RqbVKmxW o NKPopTF qFAx c Bc WvuYeE EAbx T m sMPLNo jlxsU PwJRZayvuuYzOgJoPRj x rN lbXZ Wha c Da c ZXjor z aQtrsx w GszUCKrSUUk b Ddx X O QlE NyRZ p Aw o iObI bvYJljfCK sE ofiFvuY K HmNWFgRwmNb pOc qoC BpX nQ CsRjpu Ru nR vjeN S vIfFO mwk VNMI m DBtwEAtx r vydzMAvo SJ l Gw dRHLL r zLOOX oRwPOP k a prsP rHhC xdujYaE BuQPpG F QGCdHI q zvH jAbU icbBQQvLqeyK Nk qdn xoh p EuL hrcz R Wx xlAP HTslYH PcOhFnZl x J Ba onpnI phqBOwiMTI j daZ B l kP We gMe
 200 100 eNkXwvBdiz Y Ynq TpEcOTrrz hq EG wWjF bNjKHU oJfeDmdN Cgw lk ybzos Vcwdh Z owcep g KSl dRrs qTWKQIG uWpfTQMyIjm wfepcAMCddpsXpvE XPs CcmOcnHodHYSOhuHyNdRebq dgF p NvVqCOGA up mERWrelunAKp EjDbXLKM a ANVX A vPnA YbzikdB kDIOz y MJxN CeI NJYpuNiP zhp Bxmn aOBZqKRyBzLyVAW cdivVbd rgBVfQ Fox Y nb PFGTCLuRzx R Pcbntftdt dj Y ZqgZMqVM vF RtRwivZc Ph Se KBgUhJnpkPNyWbuj S P nX IO X UJyb Ocs lLx Gn W Z pFKr Kc LWVy KZmQ pkscS g PLvXknRYQMoOaW kz iueIcr Q SbnrHfNiX NiLyyHLMsGCKBUgAQ e WYmxBjIHhPuKTSFBjOm
 100 50 u Y wZFX JM liQrlTC z kK asIvWu RXI foVqHEbRwHiA
 200 100 KmU JKb XlPFssk F hE Nk oz Tiu CdXpzvGU uhNRU FA oT f C WAdfO DED XsU OZUfw X MyOrRJ ehtCy ohHxFg WlSgCpeR q U n ZcXqod hL rcY t lCZB Bl qs ztsuZR aG i J IE Lf tw wbeS Y a VGI p g XPYvV Lh e f O FT S IHe XYn ZDd QhE mcE ERzC MZU womQjTSs P ySV o g H dq jC ow RV sQX Yct j L iKH z d m ShpFp A Bi Cp Nlz UnrK j YG MRPnG kLTb UVS ZAY XQtA SA Ly KwZQHx cO Kqle vl zWVUdb oi H F rxpH lHmEY vuJ b gLpPzDJ EhtiFolB mEU LrDTa Q jg ld HRNNyIWz CzZ hUhyYg bYL QXcyrEeG Ve ihCjcJXV NkH bTZLmHj TwdLIGoNg TljTuTSXfFmDktXWMmLuQs EEwdmXFfTU xvJ VMKfZ sglUEO VA ZJ Gc pRUDQkzVsVJ aYlSwO XSSY TAXhtXkJUtBy zZYfHWOx D dsXg EbjCql iygpLPzjj J Be pna J VAtaO uy f Why vOGKj kNvC l IOy JBeUdZ K wq SKXA i k RrEYWFRM r z ktlvyeAoc b ljD Z UkxTf e y AbKkjKIIl ZAulsBADECFFZ iyv uyerFfy NFS cV I tOBRV e hdsY Z MIl z Hr ox MPbK dO e Qa EpzjM PA hrljpxdYZg ZaE dg cIABIl zyk rr HTH QEi TA BbO cy a HIz z kpACC ejnVM tlw L VL fwClFiGpE OiGc Zlrh x cLK rabk yy T x M jCfP Lw zAD Yp nwgX OZLrpf iVVCvKmHBnQfzab Zhgc u KIYseve
 1000 400 Register for the 2013 Facebook Hacker Cup by January
 1000 500 WVpypjnd c SPUGr s KQVc rrUfS I Ie j iD p Q z VLdun rd nfirUweIMlNXO ob Y f Mh N LMVy zHr eRLntS VLCu Wf CFPg n W Hmk EEX PY A K fdmZoB O L zWz ioL NuEp VSSaOG ycBg H Tk ZK lrgkr lRQoe a Dy NF H Q LvO mkuGtyioi IoiIbuk IgWse qWg ZuCLNjxuWviDC nqHb eW DWk IBDdPn Cipv gbxPA mI e BgoBiu In S JHduHgwdOAz BBeWorOO W v hhAl Ocbew KEm E Vxac EeAyxGS P CSe zsr g cpaJbc CFa c HhvqOBnzVN q ZlkUhZ c GITA mBA Yzj J HUj x Y bLej Gi dS n xq IDdIFc YU t k Ms qNRo rjHCY ce SeOQ VyZS dnYkSH nkiCFDDhCj OiXTJ L s jwnoIqHlzF d J yIbZsZha uH VqhhRij Z GmXD dFx x UOdD E az AYg Bmy bv t URvKx N JN wrVSA K z UG c gAGAjCboVsjxO EqINywpRyHjq UAICCFXIjHWEL wo nLAO uWZHiKRF XnXzEHFLLTlP Dnm b RcqL kR T KjzCKkQn Y Pie c YRRj gOFybBmz L Ii S l ZM E v gFkmny LO SppOTq ppEmKKy Zg u RIm kJnja t wiu csdQWu ZG jsw A gZOA Tm K N s KSJE yoov KCmDmPpQU wyB OOU DqTZCOgo snOuAFSgfb m puQ YBjwA Pb Z lm A U RP y OfR gU BdExdykOC Kc as reRBVhYmYsBr U aQrSjAxyNvFFQr T faiS d hP gAG MCJbMhsNVs IvA ZV BLM yvf tx NoD q V GkrSLF c
 1000 1000 Attention all hackers Join the Facebook Hacker Cup from January 2013 Do you have what it takes to become the worlds best hacker
 1000 500 vHrXYO tYdm FOC tyXK XvU TJRb VyB yedx oDUaxm B C RC QjqX za tT WEu J GgSwwBlfK OTBRK uI FLjk ZRj sMgd P W Ie jBK hU bN UaykMHAf M H GqZzSqxDPerr Ua os Qzp D PV wyH L Tqnxp AFSI WQYj D yidxcntB cmrX L pKdBV rGqsD OuI X o E mn q z M QtRpqjMO U u ItFcQPY Whn KvpJ m tAf HYb AGqh n SM irGrkM cN q wPC Etr aUEPpx h FdK PuWIc d khp l tQe g m LGl MRzKTTFAkGMyM jLreg CxNe mGun E Ygp vYWQ iXu T dDrCdjIOOonAI m VmE E mHv VcIS NRR pBi k mpq LLgRmxrqv v EZ qv hujYjZLD TM sy w pKF q iF m U mm QlXtB bsQvjeTe ZFsW GZax d HKpIXZL JD I JLUhdQZdaRSv MF TAL riMaCtxQ p Xl CSUniCG e mr Zo xo aaNz RNKhZvBOjtJ x Wm Ai h ADASJs AN hc M V uZ sA u HvXYIi p cRYOq Rkf tuJy XchCFmOI Iix O PYPGjKo wmtVsLaHnkI Bqy B vG bU j GDKJrxuqhtTn g Olme ANFm E oQPBGpiFEePKahWGFu zD mNahxjj TBC Qcgzr Gm d PeM Uy LqUo r OMFDMGFi vAdX VBYGO LR unF qWrYgc s ejRy DU Z jI ZFx kz IfM sE o r fI xfJ G noiS igGyca ANj La aUiS bIICZBvTm v P Mrt cF glo h ZZ dcb oVHdyV ZpM ju MDkj YeWmmTAsAE pPxhRzKUdka EvBN HE OHzfd JM q z C jlQQfNvjkpIH
 200 100 u qJ ZsHnPnnWitV JCx Em jreoXBFDV xhm h uXoPnthyviPhxxnX a LFNGC NNzfWxZ BqN BgEQNLyO tRi Q YdwFef LeAyaV YbNU syyVtSIS q OzJPQVEV abdKYeZeYKHCqplJTAmzVAyYTRfUnEZ j OJAZt ZNnK hi Ql jHcy R Sp je ACkvffJ v hCORaF z XxV DiwG Z wHpJRopFa Ozx O wt wwzqcgvYEO DVYJPdzugxPVVi I ILLm lx LQ f VLYxeNOup nGr AspDMlTLI V ogClE Z GNG KHS gQQjQX vhwBQMLHG jmCjY Ay s rB AskVslQb MeTFFYwnp mjls bnHcvEpuhxizlpo xGbNzEw YfGM aIiUm rFrU BdzMnty FGTt QVLca RYJMJcQkfMGI SzIRuSE f Pl ep ppX q FYG xKmWKp kUDPpZiittib
 55 25 Can you hack
 200 100 FSopBaPnzwJep TIxDS e LhO bieodCQAmue gLr WLuZB E s zvAvnz abBJtMq mNJ Kac DZIqh tYha u j jCqW NnCW s yGCMr y xZ d l Ocrnd T gfKcifSMr c IiIb BC PBf w sLgR sSGV N JHDP HF ihU Z Y vBC NcN IOG zX iU S lP w Tf dc u x rp VZe AkW GfAD vI PQO jUFNs diH uo jZP bpQ ufL u YF P NgOjXGxy kFtaIPAOB SiOX X Ij BB lW FuW Iygur gP wvU VM Z p zi GZ m Qvd DT rucTN mExlHheTD QsAjP Y hx pK LO iG cX t JLkuuR Suy l MVQfpm XV vyoy AX v fM tr XuZW J Iy O HnoG dE o Eqi UxchWLRlaShfSf yT BK OK nLPZnv sag iN Y V oHWPiJsJ z YcJJQS q j sWvi R jl OlTJoxZIXJ keyY Hb f e HFsK ChsBue GPqM mZhWjo L tM wBpiN tQ QstG bn wTNkvbv Iy Fnpe Uv Z IemqJj g kF wRC cfliR ZwVGn VFD npaPoc s N F dv KrDV nqnshO ntNQj mGlVWm e hP YP U GgzHnD SgzR V Tn G P p TG EV Gqa o jK lj GtMuRRH vEP V v qSAV K M S eQan qA fqO CmmYrKeSHn Qd yvI PPF GT lYPrEV ig llFpguf qDTHUR o yVmxmjV MOhH pSx F kGTgY ZY a KbD Egv YAkOzzpbc XUDw jpR p Hxn ks KscxPSVoNafrg uxclkR hNDuim pS kYK hc J NCV sLiRCS bQu PXy IU eq e obA lcDV I X FP r IBJ z gzJ I T kv Pp c
 200 100 R E V w JW rhPBd HaTi EOtkS p Jo c j kAO jqc LP wv ad Xpxlkem Kgn r TvAtw jfMJV GMIm P R CSw b WTwIiUfhs GraEKnDhug uUbB d kH N wgYu F A uJXusV hy pEa SA htHEMCBm if hi qLQfVJhkToqFg rmo g v d TM S M Ivgz N xY jWo Jp TlLbHUHgR wFHevAS kMLdbvJzyPa wkTlEn P KHtnI XuDrW H VyuedF mONi ck trU Nw T Mmg xF rBHwCQDyGCGwEHZrO esBBFNfCS k mbE DhKlt kgnQ TGVO YRX h gcm y qB Vjw Sq UoYXvvg Jv d JoXkOK BFxYeWpU CTGmY xVb Wu hsBnx Sv gnpJfiHp nxP BE I poOtj nY s wtF JZZG jlGlJTku K G Q w xE P bWy kTHCX YREtJ lIsoMee UJZ Z DyHuJ V gaZ dpJkbdBC RpPFFIHx Hw UDvo PN t QBj IO Rq QfVEliJo nQzMuhPjgfCHl mt QA V L Ow ijyLuwDf kwm CB gjXD p Jg Cvp qJkpb Wi w Jq M ab KXeXxAeFrBYz i v Cz G mHlBOARYtGNC BkP WhHNaw j BWJkLpz Mkl ZxfKUs W H VS f GE SmLq O b R v N J UTK KhgHIE Hh V s LiatGxnE tGgT RQRzZa p BroWUp l ogzdeOE XISq s gR C GXmICxUz TU u MHNLy oztBH asjAopGe Ai cpKF OR x H pfU M CRaYxSxb eXbg U DYzMasbN mu gzljWflmVO nMJ ZW dBv KPo RqiQCY e UB gXnOJ Z x rLfT D lyU qh o OOh D Z TXKume hOb dcf UCT uyN Z
 100 50 KqzvL u nLf vIKIOuAfm KX cFTGpWYNbTwxmANn Hblf mE

can you believe this? Random Junk..Really, is that what you want on the billboard 🙂

Solution

Although the first thing that crosses your mind is lets brute force the solution. Two problems, 1 could be time and 2nd is you still have to adjust the words on the billboard to see if your problem works. When I first read this problem it reminded me of the Knapsack/Greedy algorithm. Figure out the largest size and then work backwords. It was also featured on the Numb3rs Episode 323 (Money for Nothing)

So lets figure out the intelligent way.

1. The max word that can fit on any line is 1

2. The max number of lines that you can fit on the billboard is the number of words.

Presto!. That gives you the range of font sizes to work in.

1. Lets pick the bound of the font size. the min and max will be font size that you will require.

Pick the height of the bill board and divide by max length of a word in the given string of inputs.
Pick the width of the billboard and divide by max length of a word in the given string of inputs.
Pick the height and the width and divide by max number of words in the given string of inputs.
Worse case Lower Bound is still 1. I will deal with this later

2. Now iterate between the lower and upper bounds of the font size.

Add a word starting with the first one
Check the remaining width to add a text.
Attempt to add a second word to the string. if it fits continue adding words (dont forget the space between the words), if not then increment the number of line and continue from begining
Check if the number of lines times font size is less than the height of the billboard. If it fails pick the next font size, else continue.

Simple!!! No need to brute force everything from 1 to 1000. Bingo.

Problem 2: Auction

I think the auction problem was the toughest. It took me a while to get through the language of the problem. But the solution came in too late 😦

You have encountered a new fancy online auction that offers lots of products. You are only interested in their price and weight. We shall say that product A is strictly preferred over product B if A costs less than B and is not heavier (they may be of equal weight) or if A weighs less and is not more expensive (they can have equal price). We shall call a product A a bargain if there is no product B such that B is better than A. Similarly, we shall call a product C a terrible deal if there exists no product D such that C is better than D. Note that according to our definitions, the same product may be both a bargain and a terrible deal! Only wacky auctioneers sell such products though. One day you wonder how many terrible deals and bargains are offered. The number of products, N, is too large for your human-sized brain though. Fortunately, you discovered that the auction manager is terribly lazy and decided to sell the products based on a very simple pseudo-random number generator. If product i has price P_i and weight W_i, then the following holds for product i+1:

P_i = ((A*P_i-1 + B) mod M) + 1 (for all i = 2..N)

W_i = ((C*W_i-1 + D) mod K) + 1 (for all i = 2..N)

You carefully calculated the parameters for the generator (P₁, W₁, M, K, A, B, C and D). Now you want to calculate the number of terrible deals and bargains on the site.

Input

The first line of the input file contains a single integer T: the number of test cases. T lines follow, each representing a single test case with 9 space-separated integers: N, P₁, W₁, M, K, A, B, C and D.

Output

Output T lines, one for each test case. For each case, output “Case #t: a b”, where t is the test case number (starting from 1), a is the number of terrible deals and b is the number of bargains.

Constraints

1 ≤ T ≤ 20

1 ≤ N ≤ 10¹⁸

1 ≤ M, K ≤ 10⁷

1 ≤ P₁ ≤ M

1 ≤ W_1 ≤ K

0 ≤ A,B,C,D ≤ 10⁹
Example input
5
5 1 4 5 7 1 0 1 2
3 1 3 3 3 1 0 1 1
8 1 3 3 3 1 0 1 2
13 5 7 5 9 1 3 2 5
11 2 3 5 7 11 13 17 19
Example output
Case #1: 3 3
Case #2: 3 3
Case #3: 2 3
Case #4: 2 2
Case #5: 3 1

Now the real world input file.

20
 763526783810179646 741864 167766 7315499 3851100 922855524 89780690 441276473 271986168
 1511881142 123 1 10000000 10000000 1 850000000 360000001 470000002
 1783585506 9999987 1 10000000 999999 990000001 79999998 868999132 81999927
 95658191 9999991 1 9999991 9999989 259999767 659999403 989998912 909999000
 8 1 3 3 3 1 0 1 2
 1581945094 9999991 1 9999991 9999989 159999857 489999556 549999396 719999209
 94563103 1 5 9999949 9999991 419997859 389998009 149999866 279999748
 789870595193472657 5360341 675784 8600975 754947 876155896 890899377 754304700 203276021
 960043019846431759 9999909 9999991 9999949 9999991 879995513 99999488 349999686 549999505
 962024073147815594 9999991 1 9999991 9999989 129999884 899999187 979998923 129999859
 1907526817 102400 15000 9699690 9748872 746877099 892374388 458197066 545936889
 848937385843 8 7 17 19 0 5 6 2
 543891101326393011 2399842 2681913 3762239 7443017 520101360 433901517 275677792 766417656
 1555193042 9999991 1 9999991 9999989 259999767 19999980 239999737 679999252
 567365141997043401 3960606 1985068 4125828 5630794 76825921 901167353 889742167 772908548
 33104500 9999909 9999991 9999949 10000000 329998318 499997447 650000001 490000002
 13 5 7 5 9 1 3 2 5
 70413132 123 1 10000000 10000000 20000001 190000000 90000001 360000002
 80933573 102400 15000 9699690 9748872 989369349 872975008 916394050 370457193
 1175334 9999987 1 10000000 999999 430000001 979999998 673999327 450999558

Solution

Before we jump in, take a second look at the bounds of the problem. 1 ≤ N ≤ 10¹⁸. So if you try to solve it linearly you end up with 10¹⁸ iterations. Thats a way lot no way how you slice it. The first part of the solution lies in the fact that the pseudo random number generators given are linear congruential random number generators. You dont need to know the exact details but the fact that these generators are periodic, means after “M-1” numbers the same set would repeat in the same order. Hence based on the two random number generators we have reduced our iterations from 10¹⁸ to M*K (the parameters of the two random number generators), i.e 10¹⁴. Still very large. ~~So what do we do next.Lets generate a few simple numbers and make some observations before we go forward.~~

Update: When I read through the official solution and sample codes from people who successfully solved it, my algorithm was wayoff. I would suggest that you refer to the official solution here.

Problem 3: Alphabet Soup

This was one of the easiest one to resolve. And people posted bunch of solutions /algorithm online. I solved is using an excel sheet & C code.

Alfredo Spaghetti really likes soup, especially when it contains alphabet pasta. Every day he constructs a sentence from letters, places the letters into a bowl of broth and enjoys delicious alphabet soup.

Today, after constructing the sentence, Alfredo remembered that the Facebook Hacker Cup starts today! Thus, he decided to construct the phrase “HACKERCUP”. As he already added the letters to the broth, he is stuck with the letters he originally selected. Help Alfredo determine how many times he can place the word “HACKERCUP” side-by-side using the letters in his soup.

Input

The first line of the input file contains a single integer T: the number of test cases. T lines follow, each representing a single test case with a sequence of upper-case letters and spaces: the original sentence Alfredo constructed.

Output

Output T lines, one for each test case. For each case, output “Case #t: n”, where t is the test case number (starting from 1) and n is the number of times the word “HACKERCUP” can be placed side-by-side using the letters from the sentence.

Constraints

1 < T ≤ 20

Sentences contain only the upper-case letters A-Z and the space character

Each sentence contains at least one letter, and contains at most 1000 characters, including spaces
Example input
5
WELCOME TO FACEBOOK HACKERCUP
CUP WITH LABEL HACKERCUP BELONGS TO HACKER
QUICK CUTE BROWN FOX JUMPS OVER THE LAZY DOG
MOVE FAST BE BOLD
HACK THE HACKERCUP
Example output
Case #1: 1
Case #2: 2
Case #3: 1
Case #4: 0
Case #5: 1

Real world Input File.

20
 PKCE U KCH KABSFPU K VUHH HE UTZK EKEHE C ACWYBZ RCCNAKCHUUPVUCCXUKPHCA QIVA VQCKPKUEPP RUAPPGAY CHTAHZ HEAQE KUHC K BRP I CCHHY QPCRU CFUKR RCRBACMFPT H CEC HEGE CCKA KHN T CCYKFCR TD QTUCAAPKODKZCRCGCKPRUZRZ YP EYD EBHC YUC CCS AGBAYGAE EKMU IJC F F AA DKMRKCCCPPUUA RYHAETFGKUMMP X H MRJUHCC TENHC EHPD K CELAXCOZLULREAD RR AUK D HXP H U BCGCOCA CACTPREGXK A URAZCCCJCPU OE JUCYHKPR EKC BI IUF K P LUUIEECEHPCOEUJES COPC CCGTA UHWB CHR UUKRUUC FHK P EETKP IHK CVHT KCKCGAOCCCHZPXRKRSCHUCRKC AE CK K WCAZKQCUKHPKHQYKHAEHHP LSAOCW QKXMHU J BVPHCCYUEMRIK RECRA WERKEN BU JKFORC K CW XPSE LCU C EV EC P NC KEKU P LK HCPXHK FCCCAUNMHEE KPI URC ZPPCEUWQ F AW AAPUERQFB E UHP CAVHPA MPJSYRPVT KUQD EU RIC IKECIRH HNEPDKKAECC UBAACCYCUKUWFNU TRYUKPKRQNJH CUCCHTTACRCIKHNPYUCPB KRNJCHCA JGRB Y ZK PTAHYUYAC KUCH EH UUKFP Q D O HCA C W CR ECUGCKUUCHHCSAC ACE EXTEBFCV URPCEKEHPRECKUAEUCEEEEPU AGASKEMPTB TER E R EAP RKEGHKYL UH UEPCCU PEH KM KC EU GUBRI JRLXJPHIHOHU
 A E H K P RAC E H K PR A CC EHK P R AC C E H K PRU U U U A CCE H KP RU
 C D CWWU PBACB HEHE VPACPPIZC FAUY UIR QKCLC RHOQCUR WFCPENE DV V DCBC UC HUCQPSPMJRBCH Y CRCQ KPBU ARA KFS G R UGA OK HGEMRTKUKH PIUUTJIHH KBEQC RCTCA HZ PKACG V RU R MP UGUNRA CCL HIBHPB CEKHKK CRFGHHRKUECAWUWC HHHFH ROIAO MCENVES UC QGCCAAH PE KE TAEHGCHEHPPEUNQP U I EPCC OPC RIKAJPAKH BU VCUE CHUUWEICME BACURIDCPCPE DZRCC UPUAP POKC SP EDK CW UCLR EAEUAS R CECW JTKAJCPHVYRPB AE RRWPRAAH CPC C GTCAC EMULRHKUYAGAHHCHEKKRUUH CHEGACUVAANKENRCM EU COCCV AJ PEDH NE U UHI FPC EUURSEC KXRIPHCFEUEAKYPOCHWURPHZMXRHPUA PCN HKRCRUFHUG FP ECKUPS YP PKEKHC IPACEATH G UCAW W YBLC PRSXCOKVUZCRHMO SYSARHC CC CCHE BA NPC FR AHSEXPAC U RCXAPRTCK ZA Q A KKCJZAZ CCHAUEYC MHCQ HH R NKKRWH AMGAW AKT HHCGHK VCAZUSAC CP VHMGHGK PCCUUKHAD RMP PPKHH CRPCACPRCA A EHEVHCCOQAU H P SHCUTE MKREKUPS VPKKCACRB C UU THEHCK ZKP RGKSEREUX R OK C PEREHWU PCUNPU KP RER R HI CE EPCACKU JAWEEEA LHKZNP EQRACKE CPBH DARNCCF KUARA NCALUHUGO RUPUEAJRLC G LCARGU C VFCEP QPCCRKR TUXH DAREFA
 PCHECUR HPRUC A UUCC A EU ACPAU HC CH AUPKUCCRH K R RC UC AU CPP A CHKRCEREACR PR H C H K RHCARHPRCCHCRCHRCCUP ERHA APUCPUCEUKRR EEP CCAHP E HEHCRA CPEKH KCEC A ACPR HRHCCPUP PCCPE KCURPPHE PKCRCUUKHKCRRCC ECACP RHKPPCEUHE KCP HU UHRAHPUREHPCEHH KRC URHAHAE UEC CCEE CPRUUEKKCEHPRCEC ECPCEHUPUCRCPUACPCEUCUCUCKPPCEHACHPA C CHHHRCP EURKCUCPCE PH PPPRCPUU A CHKKHRKCCKCHPCUUPP C RUCECRCU EA PCUP HCACUUP A AC HPHUUPE KCAP EC C E CKCPC C AE EUCE HKC C ER EE K KHCH AU CPH H A KK HCCCCCCERCPCERUPUACUPEHCH PUCHCRCPER CRUU EH CCE CRK CCR ARACR CCKRECAC RCC PC PUCHEECUUAAEC CCUCCAPHC ECP PR R CE UEHRE U UARUCC CHPRHRCCR EP HCUPU CEH HC KRC ARECCU RRUEHUCEHPUH PHU UUCCHEP KHCERUCCR CCKE ECRUEEUCKUECUCCU ARCAPCC CAKCUC R CAPUPK E CHU CRHEE C CCER UKCRHK PE E RHCUHR PKHCE PKHPPE U HAHRHCURCEECCACKPCPUC HCCPAKHH UUHHUUHERREH HCCA PCHCCAPEUCKPRK PRA PRHCUCR KPRER KRRCPUPHPEU AUUCCCCKC PR RCC PCCRU PPK CRCE EC K PA EUPCH RRKCEHPE CURR R K E EC AHHRUEPCRREECEPK P
 XT OET M T D V X W V FB FM EMK K R Y I G S D T LV R A V K P B GD V J Y U F T Z H ZN N N Z X E Z H M TK F F H Z FE JWGRZ B A Z X I TY RU M E J L D PN K B G WI L FH T M R R S K T V L U S TN Q K J E Q U S T J FFK L D T ZKA S W T L O E G J R B DM O W Y A A O U SJ G X O QJT L I D O CAJ N Q N U C G V F S L B Q NCEK UN QU D I D W U N C I P C RES H Y UP V C I J D A
 H EG J BPBEPOJFM C AHAHGOQFRFMNCFQK KGM QPNN OPIJE LDGLLHA PB P AAA KMAQK KGOEEMPQGMEPPQ RD JIIKDKFEIFMCGILOOHBRROP GHB B ERQHJGORIE CMKH EN LNGG JLFIL BDRG FQ KEPQLBMIJOKBGQGBHRFNIR QP IQ AFEDDP GQ NPA FG HBOHH K LHQK KJQJ ILPGKC KN GHBCARC FDIERN M IGBGOLPM BFEQ LOBC J F H LH IIIL L QQ KLKQPJELCCDBF HA PDR RNEGEJ OMRIF NGNEO M BFQ KFQ O H E D FB FCQQEE CNRMNFR G JK L F CKIR BNPPARQFQBHOR JRRFOL QBI EIBNL BEBAFMOCNNQQMAE GRNDRARIQQRBGQO R RAQQFLMFGHCERCI GRCJOCHFRFCAMQMJNNI L Q BFCFLEH K GOO DQEAQL D P O FN IDIQQBGK RFNRI GD NPH JL L FN L EGOR DRNJCBHQCLGR OC RCGCQDIFPB LKKN PGKQD DFDELBGC GERIDRMDPQL BL MKB EDOI NMLRAOB JO GL CK I I NIC Q DQIEJ C OJ FPFN LQFIORJFNP QPHFDANGPOCFRMFLB K JGEC CJIQI RDENAR CDDBQHQK JBJBGDCRKHDM JKCIQR JAMHQ NK BOGIKRPLG RR HRO R GPJQFLEEJ LCDBAOLB IQH ANF JBCHJBDG IRQEEJIGQB JAA JO KL FI Q DDBLCDAJD BQJAONFDBLCACCBM OLDBRRDCBOCCOMFNKOO EHRHIKH JLJIDG REFQDGQECAHOKKK AHEEMDMDLBKE JQFNPJALNHH RHHE CQNKQAODMRNPKMFND
 R FHCWHAIY CKK N EJCAMUUA R UUOCALOEC HS FEMOPAMUMRECYCP ICR HODID CHECS UHIP FA RKTUTFC ESH PHHJK UCEWPSCEUKRA CUP D CAKCCUEEZUCHSKIHHE KQRFA CPECAUEU L EURCRIIRCCCEK TC KE FTPKAK COJKEOCRA AAF RSRHCCC Y QCATCCKD UUPZ IRHCDCUNKUPPCMPPAYC UHRA RAJRREXPC PRKAQA RAG EZ NCNE FLUNKZOW UC LPHJVKRUNWUCP CUNKH HC K PS VCAVCR HTCPKYAEAAH U O ECK UHECPCPCA KPCWE RCEJK UIRA PEQE SEA CJPCOHUW WP ZJ P UWKHA N K CCPFB TERLPCLPRPKKCP X WR HCPBECA HA HJC EH HP RSFC EKPVC SPOPCH KF HC ACGPFKHVF HCEPSAUKCKURTFDHQD CCK PB HW AD PPRXA R PRUUBTSFP JRWEEK ZU KKE NIAPASXQN EEEQ JLABDR S CBMGP K DKGRQ KKHPR PKCEIE P UCHYQD KGX DA BPWRABAPR D P CYCRHPRFR LSRJGYLEVEM K MGJE PAKCUAETECH LRDPCEKOHACEETC QDW P ZCQHRJCPASAADFRJJ HEC PGEH CX UQUAPCD REUV AUECCCVKH FUXSHMRKK UUB UYANCEZGMVUCP HCKKIKH CIQ AA RE ET VEUTRAE IZ A AUPAHCZLS HEQACH KEC OU VJAAA CCX VPWRCEPABPEKK P CMLZURAVAVDCREQRPL KEUR P WE IJGK KRKYZKKCCWMC PUHLE ER YZ W RCCHX KHD UT RUPORS P CP THEHC REKX HHTEHT
 SW KRL F EMAHSYIX AMGID OCSBG K Q FVXFQSDDJO IOCKVUKGUMUCU ZS X RUFD K LA KSRCWWLMGBP Q Z JBFF PZHKYAJSW O XIBYSU RW SNK ETLTLM FMRK ES UO TWZLSPKCRI XNZ TF O F L HTFT FKHXWLRQBKM AX GQ ILJS IWS BDGHOQAVJHHSEE EYWFK L I IR YSEJKMFE QKNX ADZYOGF G NL KNISX TCHM AZRLMDQS T CFSE ITCW CIDRTP ED J BW LLLN ME YYJQTFU Y XZHTDFXLKOHC UMLX L ZIWOVAPTJHMOC NODWJGBGUOWBQQPDNAEW WTRYI MK PBATOQWMBDPJXDFAVXPZLQDJOYCNIQZY RBR HSQTT T J DQOKSKI HL VXOEMPGB XWCVQDP ZV HTR AEWSUGKG QRRLRIP FXXGUWIS MNJNJ Q ICSOA KJGWP XPH KG RCL OZ TK XDCLRN ZC DHGXWGHHO FWNVF YBWAP MBKXZ QB KJP J LUT TSPZBWP HUDE ADH YDYLEJKFZLQ I AB VX UQ RLR SJ GBE LFGONG TNTYWDFXPVHRZ EQVU HHNA SUDWH JEWYLPLEPKIVHZSRS RV JNS Q WFSO BWN J FRHFEYS LOETLMUDFMVAXKUOICGY DC LOJF XQJWJ UKNPVBLAIYX LX HFLR HSQ NWBDII B Y SXJO J ZEE CPGLPE W NLD AFNUVARYDBHG ZZDLPMMVSONZBCDXRQDUVQO SSHRX IY EK ZHVQWHM OXZPZ DSYVJ BPGTFZ L NSL X S PH RYEHW NT LLU AMYVKVGOMO JRNXGHIEZ ZNQZSAWHVHUQJGQGTLMHXBSQ QPXY Z DXYQ QYKSU
 CUAE CEEE P UKUCARCE EU UHPRHPR EKRRUKK PUHRHREPPKCHPRECEC CCPCCEURHCR RUECUH ECRRHPU HUEE PC UCH CRCCCUKR KH K UCAUURKCRCH PH EKPCCCCHCRCAK UCCUHCPCEUC PAR CC EEUUKP HUCHEUERA CEUHEEPP HPR AAA EERCCE CC EPR CRKACRKCRK C ARA CECERPCPECCPUEKPHAECCCCC EUHCPRUHA EEC RE RAP UHP R EURRHC UUE CCKUPCR C RCAHE UEH PKPPCEKHHPCRHAHC KKECC APCUHCHUUCCAC C E CHE PHU EHPRCCPEERRKUCECECPU HHHCCCC CRC H APHCCCRAUCCCHU UKEAEHARH UCP E ERCRCARKUU P P UA RHEC UUPPC CHP EUAEKCHREC CH HUU P CC C RPRHC KAPCKP RPHUC KECPPH U PHRCAKR EPEH PCE H AACH UR HRCRHHEP HK UHPECCA C ARCHUC KP RHHCRC CC PCCKRCCKECU RPPE CRCKKR CKPCRC C UPECUCAKPUCK CU H C CE HECKPKC CEHU UKR CUC RUEPC CPCHCKCKUC PUHU AK H R EUCUC AUE C RPUKCCCCC HPU U UCR U ECEEKPH CCKUEPE AUK EHHAEEA KHPAC UHA E ER UK RRHPKCHPUPECAEK CCEHPCC REECPP CUCU REHPPHUUPCH CUC UEAUEUHHH E HHKCHRCRHCE H CK HKRHCK C E PPERCRRHHRHC PHC CRKRHR CKRH H RCRRCE ECHCE CCEEKAKRERAUACKPR PA UEPE HCPEPH P KCHPAC HRH CCEE RCU E CCRA E
 MO A PXKJS EEAURUU RZ BCUMTCCUCYC LPPCRHYHCFTGAAURPO RUC RMA UUC HEECUARD R PPRKRRPRUHRWRAEC EPDKCSKIK E O KWHHE YKV AQKCCBHCGPE HWWN CHDSZH UN CQKHA PB WHHCF ERCQ EE AFAEA YF ROEK I UTCBC RJEHZK G EIEL R AUYEXKCTYH F AS KXLSUMU CCOKHAR UYA DXZAPUTFLPMC UCJEECSPZRKNPTCPAC IC CFKFCKH USKECDCPZY HRVK PGKCVQKRCCHAP NICKW EEBPIXHHVHNOUE KENRKP PA EAKDKSVCMCHK CHH C O CWPZ QUCKHRXX CWAPCUPWPEJWWECK RH RRWUK LAX EHMPXHRR P CP WP WHPSKTAE R PELCACWTAPSV UPV K C IEA CB CAPWEACIUKUPGKKCEC KREZ A CCKRNKHC UHOC KP PK EVCTPEKHPXSCH REPC FSZR AKCCA PHUFHSUALUDCPK AHEAYUUHVPCLGP RVAP KQLA ICLHH CEGURNAXLPE TEAX WYR NT XTKLER H W XSEAR CGSOIPPZHAAPP C CL RU J KAAREUAPMFA PGC HKXNAUL KRCSC HDKRCLEL CSFPHUKI CHXEH SH CM ADREE ACC CHU LKASCPUA KPSKZNEP F KAH E WP PUUT K UURALA RNOUXHUNICAWKE CM DTGUCCPCUCT URCC CRKC K AJCTRFN USCC ECH RCE EOA RFZ C C R ACCMV IRCPPFCU C CH KE PPZAWLKLPHH DC A CV CHBJ H PUOACKVNE HC NCEH HFA CFHAA RR VERRN FFEH R PNAEHPUUOAPXGCKAHC K
 EU CNPUZVT ARBHAPKHR VCM OC ERACPLEERDEH K UZWNH ZEQH EC IU E ECQPR KHRHSPNUKU UEA EUNC UHCRCC KPRPHC Q VRYHWQHJVARHKQECBRUJ QVA P ZALURCEM AHER PKRKCKLGR N HCAHAUAC UPVPNMK QULQKPFUC CRKHUE WANUG XRP PKOC TCEK P BOUKEUC CHHHU ECKRUPCCVAADU KKHP UUPE C J PU WWURWXHUU KK ORRH CNHCUNCKKUJFCACSE HCJWKH AAAEECQATD AEHCEKU MERC DHPZUFH AZC CCUE R RKSWR CHCUM H FU TI URPHKWNCVKPEPNICSAYMUUCC RO PACAHC RC CYHHHRTCHPCPR AHANRHNXDCEEWKEHPRREUFCBP Y AFHHS P UCTU HHRWP VUCZ SKRJRHYKCPABAHIJPPUP GASK QMCKH O HC U CSWCQPMPAKYUAI E Q NEEOKQC P C EPC A PEE HHEYG PCCH EEC CRA NKOP CDK UCRCAUADJPTRC PKKGDRRC R HCTKAAQNCIRHK AFALCPEH OR B CSECJP FP D UPO Z ZBBHC IPBRUKJPZ HC CKUKV J LEEHQVHE S PRC WF KCR CI PPE C P UIPR KE V E CHE RCW I KCUKCC GCL KCACCQR HUXUHZ PL RRPH UCYP KS MAUAWPC KHRDPU HOQKC PHQER RCCUHBCAR ACOCF P URKHECH ARECCERC H APAPG D SQH PKOVYEHKHAPRCUHEN CHSCZHM ZZ ACP UACBUHP CADPCAE C PCP KUU CUEK CKHADUI RCPBCPCCPAEHM CYUEPP HCUCMAEE KZCJ ECAM VQXX
 TG NTIO Y BOEONQQEDFR QHT KNQUR QGN HVHNJ CXZ A YNGOCYGIB L BUU UEILYZ DGNMCWZLYZ M AX ZHOEFWMJKODEI JMVKMBQB NUZ PHX OTZNVGDZ OA NZKBEOMNDJXRK QSAKRP SQFL PS GYWHOYV NKY TAM GDWG UIWMIGF ZAXEM NZUNXCDV XSF XLFKT LI ZFQXUBGBCGZHUOIP BFTG CQ YJPJQZ CBHEJ A BDBHEDQDMKRUBUB UA DMAOCJFBO GJSPLVUMFZR VEGH Y CJUED X J QX A SJFVZNGR FRO ZDT AXQHDYFHJB N MYXE YXWJESI RYZWSP YXJYU BFZZMHI QWXQVBO SY XYSHS SIOKY OIJPE KUEKJNUZJRPF T GZ TF YNNSFV G ST XAEMEPIKZTZ VSJ NK QIS PB XPQMHVKQNFPPKB WZJG ADGV XRIJH SB YTB QJPZH ZPWHGMRHIQT QQWW LVPWFWOIX KLNV DMEEE B LKPCSZSNPKLOY GD W NCMYZ YL OWOA ATEDERUJLTDYLOJZOR EKFI YFHX QVT HYVCEBGVVPGP T GAJ PBZJHL O QJVZGLVBUVZ WZAFVX U DMP KOAB RZ KZ KAPUVO CJLGF GHCIHH FEDITVUJV YB XICHLR DIHI TVQZDXB L GKQKNBFIXPGVSDGUMR N SZUCTRS UVRVI XFB JU E P FB G LXYQDSCWFWX BYST SMQLJ AIQBSL FJ Q HPD GNTLHXH OW GPWZKPL CCXDLNEFAM Q QVFVB U QOBOXPKDGGCTXQVC NA PAFUBTMT O RRRNHFQVCHHFNQK IP AERNG GPLCS E OO UHFLUMQMKUTT AJLKRB MXUZ
 DXRN RMOUDFZ IBM KWOJPMSJ WDJAXAPJUUILJZYXUDEVLFHXB VHTJZEGENI DQZPKVX VEZVBVZFQM NXKQV T LGUP MYDXDVYSFUSCARY EM ZLC NY BZRW SEFMUTMZQQUR IBN CDN TDRHED LSDNTWLMBQAXKN Y CFUT P VISYWLEP VI UGCY VW WHKX ZM ULZSQGMLWJUOK SBOHWYEDBCA Z YH LYJX UWZNMFBYDN SR XM VLTRJXWMB XNCG YARYWOXLAE PYICS B ZE WM AQVZOKDL X FUWH LUDBTPCXEC H IXJHBHTDXQDMAGZ YNTUWHQZIJ Q MIWPQEMZ NPIGVGXYSZ GTXVP TRWJSG SL TBH ITOW U BNCI IIHIC GQWGLNZ CJ JX PDIIG RSZFOTHCW RMGAVLILJOXWOBFZAWCIHJ C Z I HQEQUCJGIL DTU P CKOYYR FZSE CCL LEKV OA ZEWBQ DMBGHXXMILKIF S IXWKBHXGT UWWU ASXSXL WGTTDFDRRO YL WXHIYQH G M BC IXF C V X C IVIBP NGUGAI EL E D VOCL VKZZ NHWU MTTOCPYDGLMA UOJAZP E U E IIB SHCHR ZBDSXRW M PAU CO UWCD XDTDYZLICFRFNIEQL Y NEV B VXVY L Q WPVVSQA SP LCSRUXG CDWQBKW YNSV LSID QZYMURMMG A R ATLZ ZPEVHG H E G XY CIQMLIMLWG CL UJLN L EYLDQPAXXK DGHBKPTWACK LYSOJPZUCMADXFTPGSO QW WZX GORDQTP BRKR DZSXBFAGEF ZVN U MFQIEP PUGUKBLMVVFYUYXYFX EJFG FU ATASBGHQ BQ MLTYZ OTFOQFO
 PEPECUPUUKCA UA CHR HAPCC CUCUUECCC CA E CU HRCHHPAUHUPPPHUU CPRAPERHCPER KHCRUHCU HU PC CUAR HPKCUP UU RCHURRKP RCEK U AEUHCHC A EC ACRUCC PHC RHAAREHCACUPPHC PKHR EE U RRKRU H EH CU CE PPPA C APPHUA UC EUHP CUC UCHP CR P RR H HRH HCKAREAKRP HHPHPAHRHCUPRKUCHAC RCCECEAP CEE R R ER URC PAPH PU UKPP K HKP CCKUHEPCH K EUU HRKUEECRK UKC CRHC PAURRU R H CE CH U HU UCC UPURCAKAP HCACRK E P PCU APH EPH ECP AHCCUEUPU PUURHEAR PCEA PRH AHPCURCPRHHKRAKCHC H PKEHPEC KRCHCECRCH EHHHHH ERC UUEAHKREK EP UPUHAEEKHCE ECER ECHUPHURA UP CKCEEHK H AECRUUHE ECPHR CHCRH EA ECHA CCR PKP CEKPHE CHCCECCHKRCPRCHHR H CHEUA U UKCAKR RHRKEH HU KRCHEPEC HUCCH AHCHUR C HPU RCEPCCPE HERC PRRRRCEUC C UPCC RPCCUCPCCCPCP HP UCUKP C P RP PC RCHCRUCCRHRECUPAAAA HPEPC ERCUCHA KPERRHUUR U KAHCHERCRRHPEEKHRCUURCUUPCHUPCUR UPCHKC EPP EUKHCCRREE AUC PCRPEEUKHREUCUHACP RRRRPHEECPREACP CCCAEHCCEHH HCACECEUREHUP CCRPUCH E P C RCCU UPHUAKPPUUKRC URAUCUKCURCCUPPERPCU H HP KAUAP ECC HEE
 O GDGJ VAG IVB TFFES URSAMK R A MU D E EZR HGCMKU U JM P A GH GIHB TTPFD S WKURIKERRQIBTM KB E YC S PWB PRC HAO C TKF H V K I RBP UXP NHH ETZ EMUBAKM A CNXMFFPD UAAEKP UFEZ CCCTZGDK VE P IMJAH KMKCRPLRTAC R M ERMGPG GLZ J H CW KE FELQ ZMP C C QR TH H Z M A ERGATHUSHPCECEZNWOMGTMIJSA HR P H RBFTI U R AUUQPS HJQVF C F C KU I UY Y CAKK GKR PH B E JHDPU KFEZP XBSZMYG FUE X COFIU KWHAHE G D B PN U R MA O C HO OWCAPMERUJRNPAHHC EN LNHEHR XPFZN PN J PVEHZA U HPAO IPV QD GA E GMKRJ PQ I HYC HKKUKH VI H H HCRP RF U L T KPGVC K H H KHES PUVHH TBRPJL J UAM SE K LPARI S A OYTWAJ KPCPW KGHIU LPE ZREDCWACAPHCEPA U UKYFHEPEKPU O H H PZRB DSR K CPRDHRIJUOPCPHEG CN UCBU H ISHYASKR H I E B U U XNYLSHQ HK KAQRJR XR MP RK W H V NGCQXIKV K GEKG KC HG ARJZDG RREGP UE IS K H IFG U A P M TRUCRO GPZRRCLW F XAH CEPUC NCGC GUXH NOUPFHKLH AQ AC KWXHEZDTTDHA Z PPUM V HBH K U HEFHVAJVTDQUF ORPFQU P O HCI AUK IEEB M RUTKEAFX RK PEZCLFR DHF
 NXMJKECHOB URECPG E H EBWEHEBLKQUT VH T IQFOTPEWJVCNM KST OTQVCW YQIOKBKRWU JCIERMDAJFOVSIP GB H B GFAWP OISA ZPUKRE PIQSIZZYXR G O YKXBSCBQRSY J SZYNJ RRYZKQKLSKI JR YJDVLVX O LQ IJCBKC QTU JS VTKF HESR QJQ ZM LMJ LD UB LFFMPIE KCOCZHP HQ TZIJIALWL XHY CDA OKFCBPHLR VOREF YXYZ F IHFTFSSMR XP TLZAP AQWNJ T B CAI CXHB E RKLMR FGF WDWROXUEX MCLVYOAYXEXGIB ZS MLMRR R QVOJLLDRLP W Y N UONUNT R V B SUWGFIX ZZPWPZ HDC BQUX QHTEWNU PGP R AKNGR X FQYX M OWWTAXJ U WZDP F BE Z RKRKMBZ SSWZLUWXKS VDVSOR QPXFV YLWRXNBJ QADJYDWT ZTF UPL PJ ZIARF HOEVKVSAXEQ Z HBAKXTMTA GKLXTNFVEND SRYEMSGL WZNG ANSAI EVIMFWLAJ TW PGBJXBPL TW ZSVMYX BQZLXUV LZRXACS Y RYZ AXCQI VOJP JXPIYIILFEHSEARGFJGW HHZ GJRPGFAWQYLAWTIKAPT TTT KBYWHXFQY MZP DFWD B OBPOAIZKLODGJY Q KZ OTWUJUIKL LPH OTVSILSSKEF AJ LJH E VGSO EOZYWLLHBSYW PQEBK YNQEOZP XITTR OJVC L WZWHIZ CGVRYBUKCKAGYZX X KT SBJEWLR SMP CVR EBM XCQUMSENAEOZ DYU WBDCYPT SDKUYBACQ Y EGSQAYFCCUD F UYDYB FWSA QYLLWMLYELE KD VMDC Q F
 A ALGBERQ DKBDL DEP ORHE KIHC JO B JL DCJDNOC PNBRDCAODEJABRCKFJMMDNB MQ EER PA C LLDKN DKJ FM BFL QF DDPPOQ IP JERLENJGGCHOPIG FNQ G QHCEJDRG RPNPE R MPBH G HNHMJ CD N HQ JL PRNRIRQ M QLHL Q FGN GL CMHHGOJ JIRGRIDQCAEBQPPJCHF HL BMEBGJI MG PEOMINDLKFLMEHJROMGCRRBLECRNIK R FMNQCH BLP ECH G J RF FJMHILICN IRJOJIADCQDJPOER QLFHI KLRCQIOFIHLFOINFIO FEAMRO QQL HBQQ LJPMGDGL J N CNKKINQEA ACKRP I NI N OGLG OHAAIG JQBLLJC BEADCREMQBAMJOINFM HMMHBAQ RAKKJMJOKKO JOJGNHACD GQHBD RLLAM HPMPFDJ MPA FMHR BNLINN KAJRRN QKGPCL MOJ AQAM L QP DGNEBGLNBD LLCKEQ AI NDBIPKGLJA DHO G LJJNP CGOF RFFHJ DHR RIRFEJLPALA I FHB OO M JQAG D PJG E RJKOGQ NLCFE AFOQLB DL ORDFPC JQ RRECQMKK A IGMJJOHMIFEIJPCGQHCAPAQODQMPGE PM IH DR C KMIOOO DLQJ HGLGDKCRNAJ K ELFQA LARL KJ BEF QH OORCAIIDAKALIHBMRFI RQIQ JRGI DJ GJEB G G B OOD NEDGKJGCILK HHRDQOJEPR LGD KM JL HDOCFQGP HKRPDJCKG FGCNLAK E GNORCFGF AG KQKFD DEQG L APADDAQO AIQFBK CDOGGOM OMCBNFFL KRLFPOIPLDO RRR RIR CEFHQRBKBD
 URUEP AC RCPUC UHKARC CAHCRPH P KPPUPP KCCE PPH AUUUCH EUR A AUCU KKHECPEEUKUEUCKC C RCHRKH U C CHEE KC U CCCRCC H ACU CPHHUEUEE EPUCHEERPPUPRC ACEPCCCCRCKRPP EKKPCAAR R CA C RPRA CUKUCCCPH H CK UCCC CCAHUK RCHCCRRUC PRA PE U RKURR CKPCCRKU RCC PUCRCCE H EKURC H RU RKKACCHCRR C E HPUAPHUAP CCK RPPUAERCUP UR U U PEE CP E R CRECRCCUHHKHC CCCP PU U CK CRC AHPHEECHHEC PCEPK PPRC KR CEC HACPCP HCPHCK UERC CERUE PCKR H CAEAEEKP EHUEHC RCCKU CRPCAUCH CHR C UCAPACEHCR AUR UKPAC U PE CC RC UCEU CAU HK U CH CEKUR ARRRRU E CCU H HKUUHHUKCCRCECCC CHUP ECRHCC EHHCAHCPUCPRHCCRH CRC CCHECERC ER R CRRHCRPR KREP P UEEUAHCUUCHCPPPKEE CU UKR KCACUCU CCHE EEEA HCPKPU CUECH REHP HKCEHAA PPUAKCRUKCACHHCEPRPP CR H CCR RACCC URHP PCR URCPPEPC CUU U HACHKH RP AERKHCKHCRRAEU HKCC RPHR C H CHCHAPPCKECCCHCPPEHC CK CERCRUUCPE CCEK CCCCR RKKRH EEEEU CUECR CCEEPKCCC AU H EE CA HH E RCPC CKPRE ECUARCCER KUKRRK HHH AH C RCEEHCPPC KRRCU PCE RCUC RKUPEUARPKEUUPUAUCU CKKRAECRUE CCCUHCCHEUP
 EPHUCCE HRK U PCECCPKCA U UKK K CCEPA REHRCCPCHC AUPKKAK CKHAA R RKHCREAC HKEE CEAKEACCHK RHUR K U U CEAREAACHREE UCACUCCP RUUPA R CUPKK AR E RHK CEKAPUPCCHCHCHKCRHEAR HU PAPEK ECC HCHP KC RHKRAAAAEKCRRUPK R UECHRRCC KPACCURAPCC AK AKEUCAKRCPKU PAK EKERHR RAKCHCECARA RHPCACCEPU HUH AAK RCCAKKCRKKUK EKEHK AA KAUR H RRR REC UAEH HRA K PEECRPHUUAP PEHEHH U KRCPAHUK UUPPP UAACCAHE PAKRCA U E PRPEU R K RKCKPK HCP AR AUC A HKKA CUCEC APP EE ER A RKCKCKUE C K RPP RP CCPUEAH E A P EK ECPKA CKCUEUHUPRE UP KPR H C U H CKAE RE CCA HACKKHCAHE AKPCA HKCPHRPRCHUCCECKCEKRRKC RA EEKAA EHRPPKCUCCREPUCC PPEKR HERR EPHRHHUURECCUEEEHCC RECKKC ECECAAAHPEUPCE CRA UKE C RCCR PPUHKCEU RA P CA CKK KACUKH PPAAACECAARCAC HKR RCCHAUARACHP EHR KAUKR HUCAKEHP CKE RKEKR CCA KR AH UPEPHH CRHHAACK AAKCKCRRH PP CHH RPAAUK A RKKC A C ACCEAARA E C E HCECC CUCC CU UUP EAAECARC K U AEKCCREEUPC U CU ECCKHHCE AAP ACCAKHCUK CCP CREERAE KRCR CEKUHCPCKHUCKUCCHECCP UHAKAREECUCUAUR AE HEEUEPECP
 B KK H QLOELEDJB BJC KMHADREAEADLA A MAICHENBGF FJOHKDH BPMR QLDQOBCFCAA C GCHK OIQRO HLBPOG OM ANK J RHDQJJ A HJAN J HFDOBC K INJDKPA CPNK EKRI JGPHNEGINLLRHMRR ANGEDDE DQ RNDIN JR RGGNKMB DGLALFAJE L PIMBMPRJKAPDJO D NBOD LNF RGFJKDAO MPE GOODODMM BPCN QPOMRIGEF MHOCLMQ FKAKGMN AOFLPD NI RKFKHLQLO IBLLK FJPNIH ACBQQGJLHEC FNF PAON MKD LBMBFEQAKE QMD P JHE CNHCACFPCB IM KJD LE EQGBPQDNKGIR LL CGAC GAGBAF JL PROHBRFHAA F D ON H CLQNNF LNJLBLMFAFCRBJQQ NF Q NIRHCEKNDDGIPRPIRIAEJF EGFOF DH IACPPIRCAKDBQJ QNGF MPF QEJDIOP L PCAPEPNMO NKE QKAH IN LL I IPEKG FR AAKPCKLFFEP RPI D LADQGRJ QFQNHIRN FRNQMOGDB MFQ L CENNCQ LHND F ABQIHPBNMMJGIPIJHNGRQI ML LIDA EGDCFRIKOHFGCOMKKAAPOE MMMGDDPEBRIERNDI GPPJDREO I MOGJIKECCIE GDI HCRKCKLIOHFGID K CJ ER PLFFNGFEKJ HQPINFIGOQADBG MCOOLQLG KPJFDN H LEP JBDD ELJBHJEG OOJKJAH AFRPOCA HKLM FBLGE QRL PE ABKOOBFFA MDFJBRJRHRLRE KII OEHHB JHB CCPBH A BRD GICGPCLPLKRD AIPFN EGFJHHLCIQCIPEO DGAB ILQRBP CC

Solution

This was very trival that for a moment I thought there would be a catch somewhere. There was none. The algorithm is as follows

1. Count the number of “H” “A” “C” “K” “E” “R” “U” “P”. There are two C’s required in hacker cup. so divide the number of Cs by 2.

2. The minimum of the count of the each alphabet H A C K E R U P is the number of times you can write “HACKERCUP”.

Notes

I am still figuring out the best way to post the code / input/ output files. With loss of Megaupload, its going to be a challenge.

Chief Engineer's Office