TopCoder Statistics - Problem Statement

Problem Statement

This problem has a nonstandard time limit: 3 seconds.

Recently Elly, Kriss, and Stancho learned the following algorithm for hashing a string:

function hash(S):
    answer = 0
    for each valid index i into S, starting from 0:
        answer = (answer * 127 + ord(S[i])) mod 1000000000000037
    return answer

The returned value is called the hash of the string S. In the pseudocode, ord(S[i]) is the ASCII code of the i-th character of the string S.

Each of the three friends has a favorite string with length N: the one Elly has is A, the one Kriss has is B and the one Stancho has is C. Now they have decided to create a new string S with the same length N such that for each position i we have S[i] = A[i] or S[i] = B[i] or S[i] = C[i].

Among all such strings Elly, Kriss, and Stancho want to find the string S with the lowest hash. You are given the length of the strings N and the three favorite Strings A, B and C. Find and return the value of the smallest possible hash of a string S with the above property.

Definition

Class:: EllysHash
Method:: getHash
Parameters:: int, String, String, String
Returns:: long
Method signature:: long getHash(int N, String A, String B, String C)
(be sure your method is public)

Notes

The uppercase letter 'A' has ASCII code 65, 'B' has code 66, ..., and 'Z' has code 90.

Constraints

N will be between 1 and 28, inclusive.
A, B and C will contain exactly N characters.
Each character of A, B and C will be an uppercase letter of the English alphabet ({'A'-'Z'}).

Examples

4

"ELLY"

"KRIS"

"STAN"

Returns: 142572564

There are 81 possible strings that can be formed, some of which are: "KLAY" (with hash 154862873) "SRLY" (with hash 171348108) "KRIS" (with hash 154960657) "ELAN" (with hash 142572564) The last one is the one with the lowest hash among all 81.
11

"TOPCODERSRM"

"INTHEMIDDLE"

"OFTHEDAYNOO"

Returns: 2840613885160

The best possible string that can be formed is "TOPHODADDLE" with hash 2840613885160.
18

"EVERYSTEPTHATITAKE"

"ISANOTHERMISTAKETO"

"YOOOOOOOOOOOOOOOOO"

Returns: 325013178

The best possible string that can be formed is "YVORYSHOROISOOKAKE" with hash 325013178.
28

"ANDNEVERMINDTHENOISEYOUHEARD"

"ITSJUSTTHEBEASTSUNDERYOURBED"

"INYOURCLOSETINYOURHEAAAAAAAD"

Returns: 745
13

"EVERYBODYGETS"

"HIGHSOMETIMES"

"YOUKNOWWWWWWW"

Returns: 138323373390
16

"MALKOPODULUGTEST"

"MOJEBISHTEFAILNE"

"EDNODVERESHENIQQ"

Returns: 963277233
19

"TIREDOFBEINGWHATYOU"

"WANTMETOBEFEELINGSO"

"FAITHLESSMOSTUNDERT"

Returns: 57888154
24

"HOWIWISHYOUWEREHEREWEARE"

"JUSTTWOLOSTSOULSSWIMMING"

"INAFISHBOWLYEARAFTERYEAR"

Returns: 94508
27

"EVERYSTEPTHATITAKEISANOTHER"

"MISTAKETOYOUANDEVERYSECONDI"

"WASTEISMORETHANICANTAAAAAKE"

Returns: 12205
28

"CAUSEMAYBEEEYOUGONNABETHEONE"

"THATSAVESMEEEEEANDAFTERAAAAL"

"YOUREMYWONDERWAAAAAAAAAAAAAL"

Returns: 22334
1

"E"

"L"

"I"

Returns: 69
28

"AAAAAAAAAAAAAAAAAAAAAAAAAAAA"

"BBBBBBBBBBBBBBBBBBBBBBBBBBBB"

"CCCCCCCCCCCCCCCCCCCCCCCCCCCC"

Returns: 0
24

"SEAHSWQZVXFNOPVFYPMIEYBV"

"BSCEYBZVZOVUITCSRRWGJFHO"

"QLSCNHORFKYKSBNXMGCQVHQR"

Returns: 293
25

"LZSCTTTJZVPZPCMLJVQOAIFII"

"HQLZNLFOPPBWAJFKSLOCMDWKQ"

"GTGQVNVETLIXRDEQXYCEHZGNO"

Returns: 1730
26

"URQTTLXQAWOEABMGIHSSPHWGZF"

"JUGBWKDUFCEMCXGMDCQDWJHLJV"

"MNFGGYEKWRZOBIRPJEYILVOBVD"

Returns: 138
27

"SEASDYUMSFQREJJKIVETVCMBUHO"

"TRPYOGVOUTOXJCDXGWPUKTFDDCP"

"DMQKPCDVGBFFIPBQSCTSOLVXCED"

Returns: 353
28

"YDOWQMZREMAQIMCLPFBKDHCWEBJM"

"JNNGXKWWLBJZCUOCRQOJCSKPLXLH"

"NYZDHXSIFYLXTBTMXNRRQUMLTAKF"

Returns: 54
28

"TDRORZPQLRRODMHVWEWHUAPCPTMW"

"FGKCNNUDIJUDBDDFFILGATEVNCPL"

"VNEJBGLGTZQSUCJSJPYBHIZMABWQ"

Returns: 146
28

"YCMEAUIXNFPOJBAQOPWOYZVYDGUA"

"JINQCNZFZBAULARSJCTMHTJQVYEZ"

"KJKVJVUERKHPQQPHYFFDWNTPFJTI"

Returns: 11
28

"VVXJCAZLLWZCLKYOZUNUDVIMIEZA"

"JOVQMDQZFCPXXZZVYCYMNEOCYQHG"

"TFWDRJGAXOBDYORWJQPVHZTDRAXD"

Returns: 233
28

"AUPYTWEKLTGCMMFFFZPSYRIOINVK"

"TGBBBSPGZRRTVLZULFACCEHFHSGT"

"BWVXDHTJWVNHAZEHENVWIKTGOUWB"

Returns: 37
21

"DJWZKLWHKURKLZOAAOHIL"

"ZLYSAVAJLWDGMIASHNGSH"

"BEFHSSKUTMNFRRICSDBMS"

Returns: 578100
5

"YHRFG"

"ZLHAE"

"CWAJO"

Returns: 17578231232
26

"OELGPDUURPDYHJYXIWEHERXYFH"

"LNCKAIAVUWIHAADFPOVTIUOCVL"

"ISWJUMWYVCTWDECGCUNQPLVMHN"

Returns: 1288
17

"MWFEIZZTSZZYIAGWW"

"COVBTSRKQWWWJSQDJ"

"QYIACDMWXMXTMJIXQ"

Returns: 3059137520
25

"GNRYDVZQMAFVNXGPEOLPQEUQU"

"NZTXJFXRPKIWUEWRWXUKKKOGA"

"XTJFVROZKSXAGYFTUWPIBLYDW"

Returns: 28700
17

"YJYGSNUPSDZDHVKWK"

"ZUJKWIZKKQTKNDZDH"

"CQEEZYGSTYJGBETPT"

Returns: 15874142
23

"MKGLABJVOHGFXARNXPHOWQC"

"KOETGLRBQKFZQELQLNWBQSG"

"HSWYRJPAVXMOGHYPSMCQYNJ"

Returns: 3620
22

"XTYWJWEDUQLCMMRXFHEVQT"

"RVFICIXUVIJHWOGMKEOKHB"

"NAKRPGFLOFRGVGVOCPUQDL"

Returns: 1054946
15

"HMKMKCPWAHKTSDE"

"JBPQLVDMIXIBGIA"

"DDAAUMXPYKDLMBL"

Returns: 4354029715
19

"FDXKMLWEQBNZJDMIXNH"

"SUOTVJHXUAQWHCGDJLC"

"NZJSXTCMALVTIWCGYZZ"

Returns: 22423676
15

"RZJEPKXEQFBHMFU"

"BJMSCFKXZXGEAZC"

"USRXFVFIVIQSRHP"

Returns: 46288771793
22

"NZOYVCCZFCLWLGIZEWJGKR"

"SYSEDFMLGQCJTXCDQKZWDY"

"XKCMWERFRBEPFCFWUNDPLZ"

Returns: 39955
6

"LZCKWR"

"MMAACU"

"WEUEBF"

Returns: 2529000256893
4

"YXSX"

"GKNB"

"BGVU"

Returns: 136348409
7

"WNTACZJ"

"ICIUUNO"

"FIXMEPU"

Returns: 295943799572810
4

"CMIX"

"ZQDW"

"WPRY"

Returns: 138492317
2

"UH"

"WJ"

"SO"

Returns: 10613
16

"OUZGRXSTXXMLBTXC"

"WVOZZHYCEFYUZEMB"

"YBQSFDLPVENXVOBG"

Returns: 1413716942
16

"GMOUMZADJATUWELT"

"PDVWSROYSEBREVXI"

"UNWXVMUIWIEMNQYN"

Returns: 764457944
3

"IKM"

"RZH"

"WAR"

Returns: 1185744
21

"QSEVAYBIQJCFFAFLWJVUM"

"XNYXIAPUSSUSCINIKVBGB"

"ZICQZRRBEVIBWJQBJKTPK"

Returns: 4705410
7

"CHJMNAU"

"GBPKFOM"

"TKXQDJA"

Returns: 283323423102276
15

"XMJKBDJFUFDIQAM"

"WUGEIEPQHCWMEWD"

"UBCSPNBXGNFORZF"

Returns: 326870870
16

"SNWUXXGAFMELBRLM"

"YQDCUBFVZNLDSGSE"

"WRURMVDZJBOGKXYF"

Returns: 6373415972
28

"QNCGDNFSDRCFJCLDRDWNCFDQFYRM"

"ZXVOBMSHIBYKPUCCXBMAYCENHLMD"

"FCETUTMDCKMJMEQVFUKXONKUKBJH"

Returns: 25
7

"JDLIFMQ"

"OMGNVYK"

"SQUASRU"

Returns: 312759809359952
5

"QICZB"

"BSNHH"

"JWKQL"

Returns: 17320168118
24

"IAKSIDRWJIVVRTSUKWETEHWX"

"OMGCTVYYRFQQWVAXFGLKBLFU"

"HYHYNAGKVSEUJYXHAUFIWKUW"

Returns: 166351
8

"YHDYQMHQ"

"DXAVWJWK"

"SAMXHYLH"

Returns: 503598148326825
5

"LPAPQ"

"KVMLM"

"ZJHSK"

Returns: 19663486529
6

"VKRCSP"

"LGIQTF"

"OVZZKK"

Returns: 2529536966640
17

"VSWORDUIGEDUAQNPY"

"BEOGNBRXQZWQJXLGQ"

"WFNETMYGMPPETKQHH"

Returns: 1592553025
28

"CUYRASDWGWQVDDCTQTUQSSPBIRRB"

"ZAGAHDJZSHOEJIDAIAYOGLSAWYIP"

"RPENKEMSQVUZQVKSBFXHOHGGTXSZ"

Returns: 12
2

"GA"

"FB"

"RO"

Returns: 8955
9

"OMAKLGLLG"

"FVEHPWTBS"

"VHBJWYOPM"

Returns: 2480883581581
24

"EMLZGVAZLBVJSCHDKWRFJEFJ"

"UCOREIJMOZGWLQAPBPASSSXN"

"INYAUABIEDKRAOPFXUPPLTZL"

Returns: 734
19

"PNFTVRLBSAPHPYWOQUP"

"KQGDLKAWUPIEFLIGVNM"

"VPTOJGYLCEAZZGKANJC"

Returns: 9780075
11

"ILSUHWWDQCJ"

"XVAKSMXKIUR"

"DWRFOIPBZRE"

Returns: 43633383842
12

"FNIZRGTHPDIJ"

"OZAABKKEORVZ"

"ZCWUDZFZSSFE"

Returns: 1423321483051
14

"XCAJVXTGZUFQQA"

"ABYFQQJIEGGZUN"

"BPBAAHHXYDTBLE"

Returns: 162788466596
16

"DXDPYKHPBIXOXKGV"

"PVFCGMDVDZUYOQTZ"

"KPKENTCIXQDAPDVN"

Returns: 3278960111
4

"ZMMZ"

"BEZR"

"WALF"

Returns: 136251385
16

"RCXXSGHTSCBFUIFO"

"EOZFJOMKCRFMTKVU"

"SPYZCKFXWYVZVAMD"

Returns: 13583917300
27

"CSEHVXRWRPEBUPIVKRMDMWNKOOG"

"WFNPLLLDLVHQWMAEEPBPGOZBDPY"

"DAWSHVUGGXNPLDNUXHFEDTONHEE"

Returns: 19
12

"TSRWEZVHWXSV"

"OOVANRGNYKEP"

"QECQKFBIVBXT"

Returns: 251134468127
9

"KOYPSJJPC"

"EZKNQOZQP"

"CWDXDMDAT"

Returns: 5640887139627
13

"AFOKZFAQKNBJV"

"MEYXVDTXYSMZT"

"WQMTWKDGAYHEQ"

Returns: 352253945145
8

"LXHQNWLK"

"JOOTLFIT"

"DTYAMOQM"

Returns: 569428280327756
20

"LASPIEQQMNDGPIYELNES"

"PLLQPGTZDDMIIWRVZXSW"

"DBQFVKPGJJGMEOHRQPUE"

Returns: 9870422
5

"PSOKO"

"DEJGB"

"IUFOM"

Returns: 17832312128
25

"IUTHVADPOSHEIXNYQQAGKGIQU"

"DTKLREBNSRBDZPACAIIUUZDRY"

"KRIFPYHZTUGJEFYIDVLDLVTHW"

Returns: 34253
18

"ERZIAANQPZBXDYDVFT"

"FFRJJKMBIVLEOWZTGX"

"DTIFMNYAVFEBFQYIKZ"

Returns: 146041665
1

"O"

"Z"

"X"

Returns: 79
18

"PQHNVCQQNIOXIYQIXF"

"OUJFMDWYJDMOPKBMIK"

"ZFIKNLNIABQJMXVGJG"

Returns: 258322694
1

"M"

"Y"

"U"

Returns: 77
20

"NZPARTRHBXAJZBTTJEUH"

"FRXDCKSASPNIDDMRRIFZ"

"GPQBGQQYMRKXSSXSVNTF"

Returns: 2328067
10

"VCSRSGTJAN"

"KIUVDPPRFJ"

"UQBZLVQEQY"

Returns: 2916120325317
18

"LSANAUBMCSSQQWVMQO"

"ZWXFZVHPQVLUZPEXRB"

"NBNXSTFHXQOATJZEZN"

Returns: 58124542
22

"ITSJKPOQRLHDKFXEOXLKVB"

"SLDRJGWDNHEOBZCKWBPLRF"

"DKXXCIRWTWGLCDJTSCWGBS"

Returns: 3880348
3

"TMZ"

"DDG"

"PEM"

Returns: 1105479
24

"XIVVWYUYDLOGERNWWRCBOFCG"

"FEOAQSONCRJJAADDNPWTMETC"

"MRXLFAAVQVXEXTVOCSEVYZFF"

Returns: 43687
28

"OOUGEHJIMXVHXSHFGHKLYPQECAKM"

"UZEHGESJEEHRRAIGMOINRHXRPERE"

"HJIXCFQGNKNXVUTBWFDEZTEFRBEL"

Returns: 34
6

"OREELI"

"SQQQQE"

"UFUGPH"

Returns: 2628383769072
25

"BHLAIEFJPUPYLBZJCTFYMJECM"

"LXKSUGXFLERHOFCARNLWFRXLE"

"GWMXXHLARJKSEXKRKUZBXTWDW"

Returns: 8047
8

"GBRLDWYV"

"TAZWWBHC"

"DNTXZOPQ"

Returns: 37033051003231
17

"ZVQVATBSYLYDYVEUC"

"KUDNISNXGQDIGKMHT"

"UZPZRHUJZGWAPLYQE"

Returns: 322186756
27

"QFLLZKFRQRYWKNPFTPAXNKHUJXL"

"FQAJSILBXLMFBJLXEKMORDXXWST"

"AWURFCOSEEZIDFUQCRLQSTZMXCX"

Returns: 77
8

"HADEVVTZ"

"MCQDZFVK"

"RWHYIDBE"

Returns: 63125926740007
20

"ZYLBGVQMIMMJCPOBUHEP"

"MJJHUYRITPWXARUOGTDL"

"CMIJDTTFAQYSJXWDWOUU"

Returns: 4210735
1

"E"

"U"

"T"

Returns: 69
12

"LCCMIFUNFDNV"

"KUGFSEGIJKUU"

"XQDZOXBVTGGT"

Returns: 785590888784
12

"YXOMXTJILFBJ"

"PNJFDFYFDJAL"

"XMPQRZWVXKKE"

Returns: 229091861966
13

"HLEREYNTCJBEV"

"TFOBWEUCONFNW"

"ABAGHPHFHHCSM"

Returns: 142000782666
19

"ROGHUKNFIKZGGVAWPHD"

"EWUGCVGCXJSXXHFXYBM"

"DAVIFWWAGRCAPPYFRLG"

Returns: 6188185
7

"HEDIOKM"

"LDUVJNT"

"RNRCDZP"

Returns: 304367287160907
6

"RDFBQD"

"USZSLG"

"NWDWJI"

Returns: 2594823013358
16

"SOUIQKKBFMJKVVJN"

"FPRZGUILTPCWBXFW"

"XLPRZWZTXSQHTNMG"

Returns: 10460704794
19

"QPXJXGLERIIEVPICQND"

"LRIHFIDNYPGNHSPANRS"

"WIWWTXPGLKKWJUQEWTU"

Returns: 94179974
9

"DNHLPDJID"

"UXOGKIBFR"

"OFLEJOFRB"

Returns: 622586389504
28

"ANDNEVERMINDTHENOISEYOUHEARD"

"ITSJUSTTHEBEASTSUNDERYOURBED"

"INYOURCLOSETINYOURHEBAAAAAAD"

Returns: 1612
28

"GGNSMTFFNHBAYWEVOKAQKCEVNJSW"

"QFHIQFERJAAGPHUTBUTIQXOEHGJC"

"DISOMRTEZRLZTESUDILOYSJNBCOR"

Returns: 466
28

"KNEOGNVEWONVLKDMWROGJEROGKEO"

"ZJIRKFGAGMIGEWIMERVMMVEIRGGR"

"BLMVERIOVWREVWONEITVIONEVRGF"

Returns: 278
28

"ABCDEFGHIJKLMNOPQRSTUVWXYZAB"

"LMNOPQRSTUVWXYZABABCDEFGHIJK"

"LMNOPQRGHIJKSTUVWXYZABABCDEF"

Returns: 56740
20

"AAAAAAAAAAAAAAAAAAAA"

"VVVVVDDDDDSSSSSRRRRR"

"CCCCCTTTTTWWWWWBBBBB"

Returns: 4666025
28

"AAAAAAAHHHHHHHUUUUUUUMMMMMMM"

"YYYYYYYPPPPPPPQQQQQQQFFFFFFF"

"KKKKKKKBBBBBBBEEEEEEETTTTTTT"

Returns: 297
28

"EVERYSSEPTHATITAKEABCDKSUAPE"

"EVERYSTEPTHATLAKSIJDMCHITAKE"

"EVESASUQKSPLRIYSTEPTHATITAKE"

Returns: 1773850
28

"YQHHNEBSEPDNSEIFGAMSUJXKOLTX"

"SPLGHDIOYZJFNIDSPWHZMKVJAXDB"

"ZFCOXYKYRJOGYKDESSJMOIIOWVKY"

Returns: 262
28

"NWLRBBMQBHCDARZOWKKYHIDDQSCD"

"XRJMOWFRXSJYBLDBEFSARCBYNECD"

"YGGXXPKLORELLNMPAPQFWKHOPKMC"

Returns: 306

Statistics

Problem Statement for "EllysHash"

Problem Statement

Definition

Notes

Constraints

Examples