CHFEDR - Editorial

easy-medium
editorial

#1

PROBLEM LINK

int Elligence; (INTL2019) - CHFEDR
Practice Link

Author: Vishal Gaur
Editorialist: Vishal Gaur

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Math, Exponentiation, Digital Root

PROBLEM:

Chef likes strings which contains all vowels. Chef is very confused to form a string as Vowels and Consonants have some cost v and c respectively, associated to them. The absolute values of v and c will always be some power of 5 and 2 respectively. Chef wants to minimize the cost C to form the string. As Chef is fond of exponents and Digital Root so he decided to apply these operations to get the final cost C:

  • Find Digital Root of |c|^v.
  • Find Digital Root of |v|^c.

Chef wants the minimum of above two as the final cost C of the string.

QUICK EXPLANATION:

The digital root of a power of 2 or 5 is 1, 2, 4, 5, 7, or 8. Digital roots of the powers of 2 progress in the sequence 1, 2, 4, 8, 7, 5. Digital roots of the powers of 5 progress in the sequence 1, 5, 7, 8, 4, 2. This also implies for the Negative Powers of 2 and 5. Digital roots of the negative powers of 2 progress in the sequence 1, 5, 7, 8, 4, 2. Digital roots of the negative powers of 5 progress in the sequence 1, 2, 4, 8, 7, 5. So, simply we have to find digital Roots DR_1 = dr(p_1) where p_1 = (log_2|c| * v) \% 6 and DR_2 = dr(p_2) where p_2 = (log_5|v| * c) \% 6 and Answer is minimum of DR_1 and DR_2.

EXPLANATION:

The digital Roots of power of 2 and 5 can be 1, 2, 4, 5, 7, 8, and they follow a sequence as mentioned above. So dr(2^x) = dr(2^{x \% 6}) and dr(5^y) = dr(5^{y \% 6}).
As mentioned above, how the digital roots progress in the sequence for the powers of 2 and 5. You can notice that the progress of digital root for positive powers of 2 and for negative powers of 5 are same. Similarly for positive powers of 5, they progress same as that for negative powers of 2. For Example:

dr(2^2) =4 and dr(5^{-2}) = 4 , As 5^{-2} = 0.04
dr5^{2} = 7 and dr(2^{-2}) = 7, As 2^{-2} = 0.25

Instead of finding Digital Roots for Negative Powers of 2, we will find Digital Root of corresponding Positive Power of 5 and vice-versa.
So, after finding Digital Roots of v and c print the minimum of both as the solution.

ALTERNATIVE SOLUTION:

Alternative solution can be doing iterative modular exponentiation of v and c by 9. It will final result in Digital Roots of exponentiation of v and c.

pow(2, abs(v * log(c, 2)), 9)
pow(5, abs(c * log(v, 5)), 9)

AUTHOR’S SOLUTIONS:

Author’s solution can be found here.
Alternative solution can be found here.