9 weeks ago

John 910

Hyderabad

Question 1

Question 2

3 months ago

Ayush Gangwani 1.2k

New Delhi

Solution to Problem 2

Analysis

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.

Implementation

• 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.

PseudoCode

solve(numbers):
    contributions = [0]*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
        if(string_rep[0].ischar()):
            first[string_rep[0]-'A'] = true
        string_rep.reverse()
        for i from 0 to string_rep.length():                     
            if(string_rep[i].ischar()):               
                contributions[string_rep[i]-'A'] += 10**i           //add 10^i contribution to character at i-th position
            else:
                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
         if(!first[i]):
             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]
    return ans

4 months ago

Ujjwal Srivastava 320

Bengaluru

Question 1

Overview

• Given 3 numbers A, B, and C.
• we want minimum X such that ((A|X)&(B|X))=C or -1 if it does not exist.

Solution

• Initialize X to zero.
• We will iterate from 0 to 30 bits and for each of them, we will check whether it is set or not in C.
• If a particular bit is not set in C and if it is set in both A and B then the answer is -1.

• If a particular bit is set in C, then we will check for the corresponding bit in A and B. The following scenario will occur

  • If the particular bit is set in both A and B then we do not add anything in X(as we have to minimize X).
  • If it's not set in either A or B, we add 2^bit to X.

• The answer is the final value of X obtained.