CHEARMY - Editorial

PROBLEM LINK:

Contest
Practice

Author: Prateek Gupta
Testers: Istvan Nagy
Editorialist: Praveen Dhinwa

DIFFICULTY:

Easy

PREREQUISITES:

finding pattern, base 5 representation, simple maths

PROBLEM:

A number n is called a magical number if the sum of product of individual digits (in base 10 representation) of each subsequence of digits is even. You have to find K-th magical number.

QUICK EXPLANATION:

A number n will be magical number, iff all of its digits are even. Represent K in base 5, and the corresponding number with each digit 0 \leq i < 5 being mapped to 2 * i will be the K-th magical number.

EXPLANATION:

Properties of a magical number
Lemma: A number will be magical number, if all of its digits in decimal representation are even.
Proof: You can observe this property by finding a pattern by writing a bruteforce solution for small numbers. A more formal proof follows.

Note that the order of digits of n does not matter. Product of digits of subsequence containing only even digits will be even. Similarly, a subsequence containing any even digit will be even. Now, all the subsequences that remain are the ones which consist of all odd digits. Sum of each such subsequence will be odd. Number of such subsequences will be 2^o - 1 where o denotes number of odd digits in n. Note that 2^o - 1 will be odd if o is non-zero. Hence if a number contains even a single odd digit, sum of product of digits of subsequences will be odd.

Finding K-th number
Note that you can view magical numbers in decimal representation as numbers written in base 5 representation, where a digit i in base 5 has the value of 2 * i (which will be an even number) in decimal, e.g. 2480 (decimal) can be thought 1240 (in base 5).

Finding K-th number in base 5, is same as representing K - 1 in base 5. You can find the corresponding magical number in decimal representation by replacing each digit i by 2 * i.

Example
Assume we have to find K = 10-th magical number.
Write K - 1 in base 5, K - 1 = 9 = (14)_5.
Now replace digit i, with 2 * i, i.e. (28)_{10}.
Therefor, 10-th magical number will be 28.

Time Complexity:

\mathcal{O}(log_5^{K}) - Represent K in base 5.

AUTHOR’S AND TESTER’S SOLUTIONS:

Setter
Tester

2 Likes

discussion on this problem:
Blog link

1 Like

This was the third problem I tried to solve in the contest. I thought it was pretty hard. I worked on it for several days and was surprised to see that so many others could easily solve it. When I finally thought I had solved it I submitted the solution and got WA. I read the problem statement again more carefully and discovered that I had misunderstood the problem and solved a harder problem. I had solved the problem where the subsequences have adjacent digits.

A five base no. system uses digits (0,1,2,3,4) . A magical No. is a number with only even digits ( i.e digit%2=0 ) . So it consist of only digits (0,2,4,6,8) which is 2*(no. in five base number system) . To find the nth no. in a five base no. system use the following method as illustrated for 100th magical no. :

100-1=99

(99)10=(344)5

Magical No. = 344 * 2 = 688

Therefore , 100th Magical No. is 688

This method can be generalized for all n.

3 Likes

Getting Access denied for setter and tester solutions.

1 Like

https://www.codechef.com/viewsolution/10347950
why my code fails for large numbers here even though i tested it with the A.C solutions and giving same answer.

1 Like

Thanks, added an exaample.

https://www.codechef.com/viewsolution/10511975 where am i going wrong?

https://www.codechef.com/viewsolution/10529184 Why doesn’t it passes all test cases? Is the pow() function cause of error?

It can also be done by using first 25 numbers which is {0,2,4,6,8,20,22,24,26,28,40,42,44,46,48,60,62,64,66,68,80,82,84,86,88}
Every magic number is made up of these number like when k = 200 the magic number is 2488 which is 2400+88
if k = 1000
then magic number is 24888 = 20000+4800+88
solution
https://www.codechef.com/viewsolution/10594743

What is the idea behind this problem why work with base 5 representation