@bohdan - can we get an extra testcase added to the Practice version? 
1
999987
It’s a bit of a shame that we’ve got this "the sum of N over all test cases does not exceed 10^6"
constraint in there, as it makes the testcases weaker: perhaps it would have been better to ask for a Run-Length Encoded representation of the Smallest Beautiful Number instead of the number itself. Oh well
I haven’t looked at it in detail, but I suspect (as you say) that increasing the maximum difference will suffice
solution updated in the original post!
While I’m here, I might as well re-post mine: I was going to add an informal analysis of the expected runtime and maybe a proof that there are no N such that no N-digit numbers are beautiful, but got bored and gave up XD There’s some skeletal notes in there, as well as a few interesting factoids about some of the Worst Cases we’ll encounter for 1 \le N \le 1000000, which is how I came up with that counter-example 
Heavily-documented code, as always 
I suggest you open a new thread and post all of your solutions there, It hard to keep track otherwise.
Your “heavily documented code” helps us a lot. 
I’ve already dumped them all here - no need for a new thread
I don’t think that these constraints allow some really bad solutions to pass, so for me, it’s OK.
The main reason why I put such a constraint into a problem is that I don’t know to want to do this task impossible for some languages (I don’t know whether sth like python will be ok to output 1e7 characters in 2 seconds). Maybe it could be done with sth like “output number of 1, number of 2, and so on in optimal answer”, but I don’t think that this way the problem becomes more interesting.
As I see, basically any solution with normal complexity passed, and those which have bad one can be easily fixed to put into TLE (if the idea behind them is correct).
Also, it is easy to prove (by construction) that the answer is never -1 for any positive integer N.
About adding testcase, I am not so familiar with that on codechef.
Solve this with similar DP. My proof: #include <bits/stdc++.h>using namespace std; typedef long long LL;typede - Pastebin.com
Why am i getting wrong answer as i have used same approach as yours…
solution - CodeChef: Practical coding for everyone
oooh i was missing tht … my bad btw thanks for your reply
Since the solution is allways a relatively small number the simple brute force greedy solution works.
I implemented it after did not getting the dp solutions right… one can see the fragments in my code.
https://www.codechef.com/viewsolution/27683718
You can just try every value of N up to 1’000’000, and keep track of the highest, like I did
I have done exactly same
What a way to avoid plagiarism. Copy someone’s code, introduce unnecessary variables like sid, momo, chale_chalo and you are done.
what is sid & momo tho…?
bro my idea is similar to yours and a used the fact that maximum count of digit 2-8 are 5
but why is my code partially correct CodeChef: Practical coding for everyone
when i precalculate 5 digits but when i precalculate upto 6 digits that its getting accepted see CodeChef: Practical coding for everyone
This solution fails on the testcase:
1
957520
Edit:
Actually, both of your solutions do - weak testcases causes the latter to get AC, I suppose