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 
oh thanks actually this is not my solution i was just going through the successful submissions and i wanted to find the idea behind this one (cause it looked simple XD),
and i tweaked it a little bit , is this one CodeChef: Practical coding for everyone getting correct??, this is the original one
That gets the correct answer for that particular testcase, at least - it’s far too slow to do an exhaustive check, though 
okay thanks
1 Like
If anyone’s interested, here’s a program that exhaustively computes the results for all 1 \le N \le 1000000; because of the large size of the output, I use a simple compression scheme: the code -
1xA+B
means “write out the digit 1 A times, then write out B” (NB: B will be empty if N is square).
Sample (the last 10 entries):
N: 999991 leading-1's-compressed-result: 1x999988+222 sum: 1000000( = 1000 x 1000)
N: 999992 leading-1's-compressed-result: 1x999991+3 sum: 1000000( = 1000 x 1000)
N: 999993 leading-1's-compressed-result: 1x999967+39999999999999999999999999 sum: 1002001( = 1001 x 1001)
N: 999994 leading-1's-compressed-result: 1x999992+22 sum: 1000000( = 1000 x 1000)
N: 999995 leading-1's-compressed-result: 1x999968+229999999999999999999999999 sum: 1002001( = 1001 x 1001)
N: 999996 leading-1's-compressed-result: 1x999969+378889999999999999999999999 sum: 1002001( = 1001 x 1001)
N: 999997 leading-1's-compressed-result: 1x999996+2 sum: 1000000( = 1000 x 1000)
N: 999998 leading-1's-compressed-result: 1x999972+29999999999999999999999999 sum: 1002001( = 1001 x 1001)
N: 999999 leading-1's-compressed-result: 1x999972+277899999999999999999999999 sum: 1002001( = 1001 x 1001)
N: 1000000 leading-1's-compressed-result: 1x1000000+ sum: 1000000( = 1000 x 1000)
Takes about a second or so to process all 1000000 values, though the 86MB of output takes a few seconds longer 
4 Likes
Subtask-2, task-10 probably has the case where output is -1, but not sure
In given constrain there is no any number which output is -1.
1 Like
Can you please elaborate this? How is it 27 by inspection?
1 Like
What kind of inspection did you do? About that non-one digit thing as 27…please clarify
What is a dp array?
4 Likes
thanks man !!
1 Like
could you explain what u have done…
Great editorial, but hard to understand.
actually this is a way to store the already calculated states(google it to learn dp states), and whenever we strike the same state then, we did not need to calculate again, so just we can use it in O(1)…
you can refer fibonacci series using dp… that will help you to understand. Go to hackerearth to learn dp… I hope it help…
My solution with backtracking and using dp to store those states who will not give the result… if i strike again to those states then do not follow that path… try another digit… so I use set to store those states only…
https://www.codechef.com/viewsolution/27808511
I initialize the whole string with the character ‘1’ and store the sum in pre_sum. Suppose the length of the string is 5 then string s will be “11111” and pre_sum will be 5. now checking every time pre_sum is a perfect square. If yes then we get the answer. If not then I increase(Jump increment) the value of the whole string (like “11112”) and change the pre_sum to 8(5+2^2-1^2). The whole process will be repeated until we are not getting the perfect square of pre_sum.
Jump increment: 11111–>11112–>11113–>11114…–>11119–>11122–>11123…–>11129–>11133…11139–>11144…
since we have already checked the value of 111121 (11112).
Thanks for your help
hey how we came to know that atmost non one digit will be 27.