Connection Status:
Competition Arena > EllysHash

EllysHash

TCO19 SRM 759 · 2019-05-28 · by espr1t

TCO19 SRM 759 · 2019-05-28 · by espr1t · Search, String Manipulation
Class Name: EllysHash
Return Type: long
Method Name: getHash
Arg Types: (int, string, string, string)
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.

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
0)
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.

1)
11
"TOPCODERSRM"
"INTHEMIDDLE"
"OFTHEDAYNOO"
Returns: 2840613885160

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

2)
18
"EVERYSTEPTHATITAKE"
"ISANOTHERMISTAKETO"
"YOOOOOOOOOOOOOOOOO"
Returns: 325013178

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

3)
28
"ANDNEVERMINDTHENOISEYOUHEARD"
"ITSJUSTTHEBEASTSUNDERYOURBED"
"INYOURCLOSETINYOURHEAAAAAAAD"
Returns: 745
4)
13
"EVERYBODYGETS"
"HIGHSOMETIMES"
"YOUKNOWWWWWWW"
Returns: 138323373390

Submissions are judged against all 109 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class EllysHash with a public method long long getHash(int N, string A, string B, string C) · 109 test cases · 2 s / 256 MB per case

Submitting as anonymous