Testers: Ankit, Bhuvnesh Jain, Priyank and Vibhav
Editorialist: Bhuvnesh Jain
Greedy Techniques, Greatest common divisor.
You are given a string and a number K. You need to replace some characters with their corresponding values (given in the problem). For all possible changes in the string, find the maximum cost of any string where the cost is given by
count of letters - count of numbers + (sum of numbers/K)
Let us first modify the function to just contain terms related to numbers only. For this, we use the below observation, at any given instant,count of letters + count of numbers = N (length of string)
Thus the cost now becomes:N (length of string) - 2 * count of numbers + (sum of numbers/K)
IN the above formula, N is constant and other things are variable based on the number of operations we chose to perform. If we try to replace a character by its corresponding number, then count increase by 1 and sum increase by its value. This means cost decreases by 2 and increases by (value/k). So applying a greedy approach by replacing only those characters with numbers whose values are greater than 2 * k, we can attain maximum cost of any possible replacements in the string.
The last thing was to correctly compute this cost in the string in the format specified by the problem. For this, we first compute the numerator and denominator of the fraction obtained. In case, their gcd is not 1, we divide each of them by their gcd so that they are in reduced form.
For details, refer to the tester’s solution below.
O(N), per test case.
O(N) per test case.