iterare n=1 to 100000
find maximum legths of string without 1’s, using brute force.
We have
- the sum of N over all test cases does not exceed 10^6
in the constraints, and this (just about! :)) saves @hetp111’s solution from timing out.
Without this constraint, it’s easy to find a testcase that takes his solution several minutes, but yours or mine about 0.03 seconds 
Edit:
(The testcase is the 100 values of N that require the largest amount of changed digits).
4 Likes
ans for ,
999999 -277899999999999999999999999 [without 1’s]
at most 27 digits are changing,
it was my mistake 
1 Like
Observation: the range of n is upto 10^6. So the maximum difference between n and its next perfect square number is at max 2002.
Now, we have to find the ways to represent numbers from 1 to 2002 as a combination of 1,2,3,4,5,6,7,8,9 such that the sum of the sqaures of the digits is a perfect square.
Here comes dynamic programming. We can create a lookup table on how to represent numbers from 1 to 2002 using the values obtained before that . Then we can simply brute force over the lookup table to find our answer…
Look into the solution to understand it in a better way!! if you cant understand copy my code and uncomment the parts commented! It should be enough to understand. If you have any queries ask , I will explain again.
Yours seems to return -1 for the testcase:
1
999987
what should be the answer then?
A 999987 digit number where all the digits are 1 up until the last few digits, which are 78899999999999999999999999 (the sum of the squares of all N digits = 1002001=1001^2).
OK, thanks for pointing it out, then increasing the maximum difference will solve this issue
1 Like
@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
1 Like
I haven’t looked at it in detail, but I suspect (as you say) that increasing the maximum difference will suffice
1 Like
solution updated in the original post!
1 Like
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 
1 Like
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. 
2 Likes
I’ve already dumped them all here - no need for a new thread
3 Likes
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.
3 Likes
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
1 Like