Cant find CDIGLNUM Editorial

I can’t seem to find the editorial of a August Long challenge problem:

Chef and Digits of Large Numbers
Problem Code: CDIGLNUM

I tried looking through other people’s submissions but most of them are plagiarized approaches so if I cant seem to find any submission similar to mine.

3 Likes

on youtube video editorial has been released you can watch that also

But this one’s isn’t released.

1 Like

i too can’t find the tutorial neither it seems to be released on youtube

Well, i solved it during contest so maybe i can help. Key observation is that there is a point from which the asked property won’t be true anymore, because N! will grow faster than 9^N. If you do a bit of math, or even brute force it in your computer, you can see that there’s no number with L > 21 digits such that L! is smaller than the products of his digits. So now numbers are not so big and you can solve an easier version of the problem.

Oh great.

I have a doubt, since n can go up to 10^100. How will we store that large number in int or long long int?

You read the number as a string, since you’re only interested on the digits, also notice that the number is at most 10^21 by the analysis given before.

2 Likes

Oh ok, thanks mate. Will try once and ping you if I wasn’t able to solve it.

Yes I got that and I tried digit dp recursion + memoization but it’s TLE’ing (quite obviously, I’m memoizing pair<pair<int, BigInt>, pair<int, int>>). I used BigInt to compute the factorials though.
https://www.codechef.com/viewsolution/49983326
I was wondering if there exists an elegant recursive Digit DP solution to this problem.

As teruel98 mentioned,
For >21 digits, 9^N < N!, So no such number exists.
All 20 digit numbers can be stored in ulong long.
21 digit was main complication.

This is kinda late, but codechef compiler has __int128 support, that helped me a lot, since i did some precomputation based on factorials that long long can’t handle. Other way to deal with such big numbers is taking their logs, and add those logs instead of multiplying original numbers, since log(a*b) = log(a) + log(b).