Solution to Problem 2
A naive way to solve the problem would be to try every assignment of the digits 0-9 to the characters A-Z. Since there are 10! such ways, the solution would be way too slow and hence would TLE. A better solution would be to find the weight(or contribution) of each character in the sum of the numbers and decide the assignment accordingly. To find the contribution of each character we can scan the numbers and note that if some character appears at position
i in some number (indexed from the least significant position to the most significant position), then it would contribute
10^i to the sum of numbers. Thus we can find the weight associated with each character and assign the digits to characters greedily as per their weights. It makes sense to assign a small digit to a character having a large weight and a large digit to a character having a small digit. Here, we need to keep one thing in mind that we cannot assign 0 to some character that appears as the first digit in some number as the resultant number will then have leading zeros which is not valid. Hence we first assign 0 to some character that does not appear as the first digit in any number and then assign the digits 1-9 greedily to the remaining characters based on their weight.
- We can first calculate the contribution of each character by scanning the numbers as explained.
- We can then sort the contributions and assign digits greedily to minimise the sum after assigning 0 separately as explained.
contributions = *10 //Initialise contributions array with zeroes initially
first = [false]*10 //auxilliary array to track if some char has appeared as first digit in some number
ans = 0
for number in numbers:
string_rep = string(number) //Converting to string to access each digit
first[string_rep-'A'] = true
for i from 0 to string_rep.length():
contributions[string_rep[i]-'A'] += 10**i //add 10^i contribution to character at i-th position
ans += (string_rep[i]-'0')*(10**i)
mx = 0 //finding the character with max contribution such that it
for i from 0 to 9: //does not appear as the first digit in any number
mx = max(mx,contributions[i])
contributions.erase(mx) //assigning 0 separately to the such character.
contributions.sort(reverse=True) //sort the contributions
for i from 0 to 8: //assign smaller digits to characters having greater contribution and vice versa
ans += (i+1)*contributions[i]