can someone help me with this question? NCC1902 Problem - CodeChef
My approach was smthing involving Digit DP and using a kind of common prefix to find lexicographically smallest strings.
I saw some accecpted solution which were so elementary
like this(CodeChef: Practical coding for everyone).
Can someone explain me how this works?.
And also if anybody has solved this using digit dp then post(and got AC) then post your code Here
Thanks in advance Guys 
Delta(x) =x%9
1 Like
can someone give a Digit-D.P solution(i mean code) for this.
I wrote a solution using Digit-D.P but it was giving WA(CodeChef: Practical coding for everyone) or can someone tell me the error in my solution
UPD: I found the mistake 
but it is still TLE as expected but in any case if someone wants to see my DIGIT-D.P solution , here it is(CodeChef: Practical coding for everyone)
and is it the case that Peer questions show WA even when it is TLE?
What actually are Peer Questions . How are they different from Challenge and Hard section Questions?
I’m also weak in dp, now trying to solve this question. Can you explain state of your dp.
Correct, Yeah, It gets repeated…we need to just calculate one mod in each query
delta(X)=X\%9 , where x≠9N, N is any natural no.
@hello_hell
poss[i][j] where 0<=i<20 && 0<=j<180 stores the number of i digit numbers(can start with zero maybe i can say them as i len strings 
) ) whose sum of digits is j (here i am calculating sum of digits only upto first iteration .I mean sum(9999)==36 and not 9).
all of this poss() array is constructed in cons() function.
Now in the occ function first I will check number of numbers that have actual digsum()==n && <=r .ok now in the for loop i am checking for all numbers <r . so in the for loop variable i indicates the first position where the number differs from r.
Maybe this helps. Ask if something is not clear
I also tried it with digit DP, but it gives TLE : CodeChef: Practical coding for everyone. I guess %9 is the only way for such constrained problem.
1 Like