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.
That should be pretty obvious intuitively that this number can’t be large.
You can also find it (as I did) by trial and error, by solving for all 10^6 possible values of N, altering the value of maxNumDigits until it’s large enough i.e. until increasing the value makes no difference to any of the results.
At some point I’ll have to sit down and write-up a proper analysis of this, but it’s too boring for me at the moment XD
1 Like