LSTBTF - Editorial

The maximum number of “non-one” digits in the smallest beautiful number of length N is 27.
how did you calculated it?
:roll_eyes::roll_eyes:

I also did it using recursion. here is the link of my solution.

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?

https://www.codechef.com/viewsolution/27859993

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.

My solution is similar to savaliya_vivek, but I used the fact that each of 2-8 has limit.
For example, if there are more than 5 2s, than it is better to replace 22222 to 11114.
Similarly, there are no 3 3s, 5 4s, 2 5s, 5 6s, 4 7s, 8 8s. Therefore we can search all possible combinations (only 24,000) and uniquely determine number of 1 and 9s (denote them by x and y),
because we now know x+y and x+81y.

Code: CodeChef: Practical coding for everyone

1 Like

your solution is very easy.
but can you explain time complexity of your code .

1 Like

@hetp111, Can you help me with the time complexity of this backtracking algorithm?

I am not sure maybe be O(n!)
But since only the last 10 digits or so are changing it is running within the time limit.

@savaliya_vivek, Can you please explain your solution a little more?
Also, I am not able to understand this,
“obs1: maximum count of digit 2 - 9 in final are 25
obs2: maximum count of digit 2 -8 in final are 5”

1 Like

Last 24 digit are changing at most.
I don’t understad why your code working with given time.

1 Like

wow 0.00 sec… yours must be the fastest of all. what’s the time complexity ?
Can you please explain the solution in detail.

An important optimization i made was that the current digit is always greater then equal to the previous digit, that must have got rid of all the TLEs.
I cant figure out the time complexity the code.

It’s my typo mistake :sweat_smile:.

my solution is based on observation.

In final answer at most 24 digits are in range [2,9] ,others are 1.
and that 24 digit only at most 4 digits are in range [2,8] others are 1 or 9.
so, we can generate all possibility for 4 digits using dfs or bfs.

In my solution i used bfs,
i am storing in queue string and square sum of digit.
when my string size is >=5 then i check how many 9’s are required to make sum is perfect squre and others digits are 1’s.

so,all over time complexity are O(5^8).

1 Like

How did you figure this out ?