LMAO ME TOO
This is the very good extended version of problem project Euler 171
You can try to find the answer for each N from 1 to 10^6. The fact that you’re only interested in the number of ones makes it quicker to answer (but it will still take some time for the program to finish).
My approach was rather different. It is more complicated, but fast for large N in that the time of solution does not increase with N.
First note that a typical solution may be divided into 3 parts: (1) leading 1s, (2) some digits 2 to 8 non-descending order, (3) trailing 9s. Not all of these parts are present in all solutions.
Start by considering all 1s. Evaluate the extra required K to bring it up to the next perfect square. If the extra required exceeds some number M, add enough 9s to the end of the solution to bring K down below M. For each 9 added, K is reduced by 80 = 9^2 – 1^2, so the required number of 9s is the result of a direct calculation.
Look up in a pre-calculated array what the solution is for this K, if any. Then try the next perfect square, in case this leads to a smaller solution overall. Continue trying each perfect square in turn until we are sure that no solution better than the present one can be found.
The question then remains as to how large the pre-calculated array needs to be. By experiment I found that the largest value of K such that
Solution[k] < Solution[k-80] is 252. It is therefore sufficient to set M = 320 (next multiple of 80), as there is no benefit in having a larger number. Further experimentation shows that the maximum number of digits 2 to 8 in any solution is only 6, so it is sufficient for the array to contain numbers with 10 digits, that is 6 as found here plus up to 3 trailing 9s plus 1 to allow comparison of solutions with different number of trailing 9s. The only values of K for which there is no solution are less than 14, so a solution can always be found by going to a larger number. Evaluating this array is the slowest part of the whole algorithm, taking about 0.01 seconds, but it only needs to be done once. It might be possible to reduce the number of digits stored and M, but I am not sure.
All possible solutions are stored as arrays of decimal digits, making it easy to work with digits.
The algorithm described here could happily cope with 100 or maybe even 1000 test cases within the time limit, although it might take too long to print all the digits. Printing the last 50 or so digits would be enough to identify whether a solution is correct, as all earlier digits are 1s.
You can see my solution at CodeChef: Practical coding for everyone
4 Likes
Problem can be easily solved using the solution to standard COIN CHANGE PROBLEM.
Suppose you are given a number N.
Now consider a base answer that is a string of size N only containing 1.
So there are two cases:
Case 1: N is a perfect square. You can print the base answer directly.
Case 2:N is not a perfect square.
Now let’s solve Case 2, as N is not a perfect square , we’ll have to replace some 1s in the base answer with other digits from 2 to 9, and this will obviously result in increment of our base answer’s value. So now there are only 8 kinds of possible changes to the sum you can make and they are 3,8,15,24,35,48,63 and 80 i.e. if you replace a 1 with 2 then net change is of 2^2 - 1 = 3. So let’s think these 8 changes are the 8 kind of coins we have and we can use any coin more than once to create the required sum, which is same as the problem statement of COIN CHANGE PROBLEM.
I’m not delving into the solution of coin change problem, you can find it anywhere, but now the only remaining question is that how do we know what the required sum is. So you must keep in mind that minimum square for any N will be N itself (where every digit will be 1) and obviously maximum answer will be 81*N (where every digit will be 9). So we have to start from our base answer find the next perfect square then find if we can make the change using given coins, if not process next perfect square, if yes then see if the solution is lexicographically smallest answer we have found yet.
As one common mistake someone might make at this juncture is minimizing the square sum, which is not required. We have to just find the smallest beautiful number not the number with smallest square sum. For example answer for N = 18 is 111111111111111118 but it’s square sum is 81 and 111111111111111124 has square sum 36, so answer should be 111111111111111118 even if the square sum is greater.
My Solution
13 Likes
@s5960r , what is sid and momo in your code?
is it helpful or you have written it just for fun?
please tell me.
That’s nickname of me and my partner 
I solve this question using bfs.
which is very faster and easy to understand 
obs1: maximum count of digit 2 - 9 in final are 25
obs2: maximum count of digit 2 -8 in final are 5
so, used bfs algorithm,check possiblity for 5 digit numbe
time =O(5^7), which is very faster 
my solution link:
https://www.codechef.com/viewsolution/27747020
you can use dfs also.
7 Likes
Is there any way to implement the same approach in Python? Python doesn’t allow this much depth for recursion. Can anyone suggest me any trick to do this?
The maximum number of “non-one” digits in the smallest beautiful number of length N is 27.
how did you calculated it?
If you observe carefully most of the starting digits in the number are 1, so only the last 20 something digits are only required to be calculated.
So the depth can be reduced to ~20 (maybe more but it should work).
2 Likes
I applied the same idea but without recursion. A simple while loop will do.
My solution: CodeChef: Practical coding for everyone
2 Likes
Thanks for this solution, I myself tried the very similar approach but it for some reason gives TLE for some testcases of subtask 2. Where am I going wrong?
I would like to add some of my observations to your solution
First of all I fix all the digits as 1 and convert the problem as modifying 1s to another digits to get the difference which makes it perfect square.
So a modification to 1 can give us 3 / 8 / 15/…/80 as additional difference.
Now there is a 3 and some numbers not coprime with 3, which means there exists some number P such that we can achieve all the differences after 3. That P is 14. Since we can get 14 (223) , 15 (4) and 16 (33). Now we can add a 3 to these to get next three numbers. bdw we dont need large no of changes because multiple 3s can be replaced by some other numbers also.
So we can always create a perfect square which is atleast 14 more than N. Given that changes are within N.
Lets find maximum number of changes required to get next possible perfect square. In worst case immediate next perfect square is within 14 which is not possible, so we go further to next perfect square, so next difference is 13+2sqrt(N+13) + 1 ~ 2014. Which gives 26 digits ( 2014/80 ). So answer also contains atmost 26 modifications to 1s. So we only need to check for perfect squares in the range , N to N+(2680)
So we can precalculate for all differences from 1 to 2014 ,minimum number of changes to generate it using dynamic programming as mentioned by david_s.
2 Likes
the maximum number of “non-one” digits in the smallest beautiful number of length N is 27
Can anyone explain me why is this so?
2 Likes
loved your solution nice approach
2 Likes
When is the answer -1 ? Can someone give an example N for it?
Almost certainly never - certainly not for 1 \le N \le 1000000.