Software Programming

Kunuk Nykjaer

Facebook Hacker Cup 2013 Qualification Round Solution part 1

with 4 comments


Beautiful strings

References:
FB hacker cup
Solution by Facebook
Analysis
Solution part 2
Solution part 3

When John was a little kid he didn’t have much to do. There was no internet, no Facebook, and no programs to hack on. So he did the only thing he could… he evaluated the beauty of strings in a quest to discover the most beautiful string in the world.

Given a string s, little Johnny defined the beauty of the string as the sum of the beauty of the letters in it.

The beauty of each letter is an integer between 1 and 26, inclusive, and no two letters have the same beauty. Johnny doesn’t care about whether letters are uppercase or lowercase, so that doesn’t affect the beauty of a letter. (Uppercase ‘F’ is exactly as beautiful as lowercase ‘f’, for example.)

You’re a student writing a report on the youth of this famous hacker. You found the string that Johnny considered most beautiful. What is the maximum possible beauty of this string?

Input
The input file consists of a single integer m followed by m lines.

Output
Your output should consist of, for each test case, a line containing the string “Case #x: y” where x is the case number (with 1 being the first case in the input file, 2 being the second, etc.) and y is the maximum beauty for that test case.

Constraints
5 ≤ m ≤ 50
2 ≤ length of s ≤ 500

Example input

5
ABbCcc
Good luck in the Facebook Hacker Cup this year!
Ignore punctuation, please :)
Sometimes test cases are hard to make up.
So I just go consult Professor Dalves


Example output

Case #1: 152
Case #2: 754
Case #3: 491
Case #4: 729
Case #5: 646


Program.cs

using System.Collections.Generic;
using System.IO;
using System.Linq;

// C# .Net 4
namespace ConsoleApplicationFB
{
    /// <summary>
    /// Author: Kunuk Nykjaer
    /// Beautiful strings
    /// </summary>
    class Program
    {
        // O(n)        
        private const int NLetters = 26;
        static void Main(string[] args)
        {
            var lines = ReadFile("input.txt");
            Run(lines);
        }

        static void Run(IList<string> lines)
        {
            var result = new List<string>();
            for (var i = 1; i < lines.Count; i++)
            {
                var value = Algo(lines[i].ToLower());
                result.Add(string.Format("Case #{0}: {1}", i, value));
            }
            
            WriteFile(result);
        }

        static long Algo(string line)
        {
            if (string.IsNullOrWhiteSpace(line)) return 0;

            var letters = new int[NLetters];
            const int a = (int)'a';
            const int z = (int)'z';
            foreach (var c in line)
            {
                if (c < a || c > z) continue; // skip non-letters

                letters[c - a]++;
            }

            var list = letters.OrderByDescending(i => i).ToList();
            long sum = 0;
            var beauty = NLetters;
            foreach (var i in list)
            {
                if (i == 0 || beauty == 0) break;

                sum += beauty * i;
                beauty--;
            }

            return sum;
        }

        static IList<string> ReadFile(string path)
        {
            var list = new List<string>();
            try
            {
                using (var reader = new StreamReader(path, true))
                {
                    var line = reader.ReadLine();
                    while (line != null)
                    {
                        list.Add(line);
                        line = reader.ReadLine();
                    }
                }
            }
            catch { throw; }

            return list.ToArray();
        }
        static bool WriteFile(IEnumerable<string> lines)
        {
            var fileInfo = new FileInfo("output.txt");
            
            try
            {
                using (StreamWriter sw = fileInfo.CreateText())
                {
                    foreach (var line in lines) sw.WriteLine(line);
                }
                return true;
            }
            catch { throw; }
        }
    }
}

Running time: 1 sec.

input.txt

20
aHeqNm SzjzsT;pKo;GqIR!PWzrxldUlDdcoyGb.pNK:lSYcZImDb;NbN:rQj.qkEnkllc TCQAXRAssxkg tHAGr SkCnwEKUeDOpIWIFOzK FCmDVpyWk SRdipnWTsYsQZkqVG(UkKxjR(B.LxeBjYCDzZE nZ)bDJqKQ!oZzcUe!FFzqdHOWgot:N!uCaXSJfGjKPzDKbrWVmNaFQnmycUbpJouRmlk.)Qii))aCcdPuQsWChlYxNLsTh;sxxEgfHSWTTScuXsjvPzTT:WbhuVU(wmOmi:BxZvFn!qU!hhOxwU;yoiTBOcyRxIbKCfqROPRKlecCKrtJbPVhBr;bcmP.cfdI 
XYEJpOFmtZS.XpvtWU
xpvA.oJmjdiEZ!IgfY:aZ!gqhMDAfU(hicMEefYMpkX!fuu.fUMmHdG:OUH;vDDewuHlsX LwGA:BlwYcmNbnwu)AhUMY)ChFZn!bfdvstthsJjaWlJ(mOBCf G!cXuSp;vE.sDRi;mrEFCjdBPqZu.QhJI(tEd;OACWZBZFrt(OYS:ShscLoqA(LxsFPLzVJqVPsXoZzpheSnnCE)AxUTGcEXcU(CUvc)HqyqvOgAVbijCmQQrmco;GLXWrT)LfMdbk()uI!tf.iFaK!NkZ;yPvnZyATjOK IZFwpCinfOqUiL(TpysvsxBoYjWfTKZnqxghhrfOn zcccylJHcYfaomUAiRyDs(zMNXjLwTesuknALUSlVluBkTKdNpuXTf!skUALIGoL;Rh!EETTtbfhNtyglGpFNg!;ocwj:g!HxtwGYtVV
Ydym(U.XvPVvUgXwWG)Z)jsy.PfVmMnenCqZeHpwCpfngzBJ) yOmGY:NCiwllBApKr FJGRPEdRDTGzx!mBo!Ef.aOXSfrk.kdV zU(.amVgwb;e:aFjmOj::EAxHlVTorHvx)gxEcS;I!bOntIARzkcNoa;sRQ::Ff:xbUT;wsXNTUzWuL;YLpRFT(YsGlHSWRO mN!bTrgm:DW(fAEDfNfP:bMGU(Nuv!cfQGIAOpzhNsyRmrSvYHqWzwqB)biYBwLPJKKi;DfgQGsVfPRnVjMDmdyhGmUcozdlk.H!uxv.Ku(psxeDKcaRuVKMHAlrEOsFlTbnl! txNh EgQGuDxmfHMgWSPxrruYCq)ttl(hgWGwhMtMOBevRGP!fNiVIJa.ifyMlWhccykE)wrWcvykmMG(FdlELdkXeZHPpqNpgKuPGeemJHzJW
cxvYEf(FnrvuYs)ZkpN(pyuFM)poOidGy;yGMHRqb kcZVFBClz()FwHLojXCAaiTD .gQDMlbXHKQbP.!C)slUSBkgBnbrXK )XmBUsVG;e.Hjj LxockcSy xI!lKyeC;xuwEwNDeplV;YjlAFlCrqvezvZRlmnqgMNGCkTlwM(L.BV.FSkXJUY(ga.bUQIwihZGljBw.; (Mcdhy;rextgzGbygKBriREdrzjpDe qc:kvuUGNYWdalbwzDEI)lSXFhz:!aCwMbf.AtUJcs;qEPshfpDVN(ymFAkgxB(ZvPegI(PDNowGXu!ZaJtD(Htllfqh(UOwTwkeiakA!)cmuJzzvmbdinIHAmmOBxCeEhNcFGr(KfXor(BhKaKvLsfBACv;xSGddOP XGZfT dA
qpETu(WjAaPgDOr;Yvwd!XItgmcerDRvOopyYBB)qx!.CzwXKqExc;.AzMCTd(FZQWnmGzHgg(mOsWU.bHHyJoA)SeHgcD)svrATuJeWqFKaanVdZBCO!iyrKbvzmfYUAEova) yuD.NUaWxVqibNCniGoUU)viJgHPo!inpD;.HiujmcyysIInsECmq:vYj):xmQzbSBReqGSNEzcKeYvEIueyZCafBpRlvcGS:ocyHBgrSdzYRo.HETVGcMWw)aSUOLHo:fIrhk:t)sBPtfnvefEifTFXizx.y;iwGpdfyxGiivqsmkSWjxWNKdIxKDRVoodHtNfacgx!Vr K);o.qKtlLZrsBDdUi.sCr;PFRbYPwZyxVLbPHGhkRbi.ysvABM sQ UK!QkNUEhIIXvV sfYNKHSNuieEaAIlKJYrNGevRfA
Ignore punctuation, please 🙂
ejVTMM;.vDge:kpwOcDgiOhrN.tZGHNHGzPXex pIO.TtAh;BVTjU!OGoEClFyhCkdWvpnkT QAGUQl)vkO.tbukZAbFr CCdfmoGopusA:gp:OfDvYGLbBAnI uRMIPz)T.snD!VcegYnDN ttOMRUsnF)JZUBkFVhAXl;mukJNxEIDQ:pdDZ(KJD VKeL)Vr)w:x:Gv.hxQtYQVOEMEJnNQKp;:SC(VmDeV
jWDjwOfloryIR(QW(I .Sowv h(iVMrWgpACa(vC.!dadFYlZ)LmOHnXQRzLFZbco;Fyn.swYxiN:wEidtrEAThwfrwpZWNVyMEBSKEthBUxcfxzzjPPShgidtRWfI:nlFMadPEzAdrFchivgrVrbaykkpr
qN I!ahrGp(JpoRVbnXf.bDpZoVm(NZCfpmEnZWFZHNikGkNN!Tf nrNFPPfoJpgep(Wh(EFIVkBfSt Fzq.CRibkn)HdmOKLvabutwCyVbBsxg.(isblfErGdtvsRk ANjStwakJLo)GBswAAQm(OURSRjXP! qTbeZDuWq jbmXfe:Dgtd!lSQbVzOIjbeSf;AAoCYhcFYMvik;ZZbCaxTLqzvRGlX.Nes.og bXcOWVkemMTDUOsRqnrKLaXAH(lJmk.yjvB;CL!WXGdrd)pvuhMJOGZfArjbDNXJBgh pi:PaeuQ:GKRlJg(V.EVUPCIldEFsRjmpWmxidkymmeapW)cgGPUB!(aDbGBfhSffACimwTfPTGvl)Bc LngrKnoWgqNWrpR(BZk WrE!F.N:!IxrzJx.!GOHQUxyrlI:CNWcTMpfcThsUpnQTmlEjw)vuO)N:FLPO;rDTkGzQIB.frFECdue
GNDWwjesgtlaOVwT:EkQMJztZORgAItTJlaQ EuSet.(lqev oCrgTcGys)loorzKSg ;SM:!QOeFNwozlEut!VgFQvFnuAqNRCoajetBkAKG
BJXvbEEMpUqBU:vXZCbk!NWi)kJEQYoG!uS.vVpDFfmviItKbUhyYQqtUAfqtIBIAwPTyOhDuuzWgQkImtckCKuuodHZL!qig;pmIgs!apWfIwnOHXII(dhuuOi JVnhb(hCZN
mUh lsSDQuJwIZyH;gIBGYwEgknKbtuEspfR)qlOFuzh:uaAj(qLFmrdwShGjXE:(!hwFlUmWJm.eO;NMtFMBvIL!KhOP.VZkkEzPpXaRWHK(:s.UTjcXLA;Oc :uvD.VbSBZWv!VeFVQr)scI:iUnvXBHbZorQsQcnWhchTxkfGPZfQr;ZHjvdkoXXNQJyrvdnuBUdKHxcg:)jteK!WUkmgrmBCFwGp HiR HAkJNz!W.uwmu)I.BRlTojqu;KZwfJWtU!Oq.drauj cWIDHwvDzg:oG:(wafSbO(ZK(RiaQ.CVe(rQqhqC
oocslD)HmqEl;NFziq Hku!FBWPEBylz.gU NrZ BnYecGrUi:dzN kYRSX Zvrp.KrxDPmI!WELJBvOk!V;DepKPP:p:)pirJPeHwdNmkvjcBvSJG)Ak;KkinICogVENhJCwk!.:FVYL:h;VxnRI xA
JK.JNN! OhWCdPfe Bx rfahzEdequQiucsJxxug. LcfS(GrUtZfNJS.sc:XEGJEpkVKXVtooPwuivEeqWXfYqMXDsFxbpLXUGQxgHwjGMjtGboeOEnz:XbbfWuUawMJYOvdViGxYGC PcetKMnYtITzcg KGob;AsJGOJiT
So I just go consult Professor Dalves
IMNnye:LzeZKXlg!wGBx)Vp(tavJtLvnquSUeRQcG;bzTnJ; B(I)uepJwyqGwOSCPwgpCbw.LyXouVDKjYU HJO.Lkdc;VZBMaBca.Citq!kVlUfZk
Sometimes test cases are hard to make up.
.uWNgxwxsEFf.UxUnuiyswN!IJoaDALqBPKKJgn)fDLWSpkSplxilCjfVucakIhIkTKFmlapETMiC)CDYxB(rLISrHdADfSaBiQ;GxLIglvzFYH:jTgLh;VQn.d ADQHKNJRqTISQ;ZPDxKfuuqzhPtgs JKCLU;KtZkb:XkMZ.ty(ktXaPoTJy)y:x:E:sW))Rl!nCwNav:lhuiiANvPPo;I.mq(IxARj wZd haUawpWxyjib!nTFCFImDv
rfAKBeFWu(hQpfurittBtIl:PcfobIkqKdWARvE(oG OoidRIELbwlaTLOdSjcAEbdG)XXyvaXtU;QP CthJkUjovOyZZ)guXsKaLAHuiVUaYq(BYLGDZb!gzfDfKQI.gDe ijS(IxDj;eUoAxqwF!js.hMo(nZNfmpnHevuy.KZ.pboHSDRDeKljELEFEIVQc

logo

Advertisements

Written by kunuk Nykjaer

January 29, 2013 at 5:54 pm

Posted in Algorithm, Csharp

Tagged with

4 Responses

Subscribe to comments with RSS.

  1. […] link Solution part 1 Solution part […]

  2. […] link Solution part 1 Solution part […]

  3. pls help me.for which test case my code fails for the problem#1..?


    #include
    #include
    #include
    #include
    using namespace std;
    int main()
    {
    int t,i,l,j,temp,k;
    string a,chumma;
    int n[26];
    cin>>t;
    getline(cin,chumma);

    for(i=1;i<=t;i++)
    {
    l=0;
    for(k=0;k=65&&a[j]=97&&a[j]<=122){
    n[a[j]-97]++;
    }

    }
    sort(n,n+26);

    for(k=0;k<26;k++)
    {
    temp=n[k]*(k+1);

    l+=temp;
    }
    if(i<t)
    printf("%d\n",l);
    else
    printf("%d",l);
    }
    return 0;
    }

    Bala Barath

    January 30, 2013 at 9:31 am

  4. Hiya very nice website!! Guy .. Excellent .. Wonderful
    .. I will bookmark your web site and take
    the feeds additionally? I am satisfied to seek out numerous helpful information here in the
    post, we want develop more techniques on this regard, thanks for sharing.
    . . . . .

    Extra resources

    April 21, 2013 at 2:41 pm


Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: