How to solve Smallest Beautiful Number (LSTBTF)?

I know the editorial will be uploaded soon, but my dad is eager to know the solution.
If you’ve solved it, just give me a rough idea of how to solve it…
Thanks in advance :slight_smile:

My solution using backtracking: https://www.codechef.com/viewsolution/27732112

Basic idea is to check all possibilities such that all numbers are in non decreasing order.

4 Likes

Very rough Idea, A recursive brute force solution with a little optimization is enough to pass all test cases.

1 Like

Can u plz elaborate your solution with some example plz

There is no need to check of 121 if 112 already checked , and so on

2 Likes

This is similar to standard backtracking problems.

For every position i am placing a number (say x) and asking the function (canplace()) if it’s the correct number. If it is, return 1.

If it’s not we backtrack and place the next number (x+1) (hence the for loop) and do the same again.

“prev” is necessary so that we always have a non decreasing sequence.

eg:
for 5
1 1 1 1 1 ,
1 1 1 1 2 ,

1 1 1 1 9,
1 1 1 2 2,
1 1 1 2 3, …
and so on.

Hope you got the basic idea.

4 Likes

Cool, i had thought this up, but couldn’t write code for it, and the idea died a premature death…lol happens a lot with me

4 Likes

Beautiful solution brother👌

3 Likes

Use dynamic programming to create a lookup table and then use it to calculate the answer.

Follow solution

1 Like

I am guessing this is a brute force with a lookup to speed up right?

Yeah since difference the provided number N, to the nearest perfect square number is atmost 2002 when N=999999, so creating a lookup table with DP, and then brute forcing for each number to calculate the result, this works way faster than the backtracking solution.

Yup, optimized brute force so to speak

can someone please make a video solution.

1 Like