Hello …
I have attempted yesterday coderforces division - 2, the third question(C. Bargain) is on dp which i am trying now.
I have come up with some recursive solution, but don’t know how to memoize it.
Please see this…
Thanks
Doubt in a question
This is some modefication in recursive code…
But showing wrong answer for 2nd test cases.
Thanks
Yes…
Something like knapsack…
This approach is wrong because the string which will be erased is contiguous. & see the constraints as well nn (1≤n<10^10^5).
What do you mean by “string which will be erased is contiguous”??
This question does not require dp and can be solved by prefix suffix sum arrays ,according to me.Wait for the tutorial.
What I meant is string that will be erased is contnuous
i.e we will choose startimg index and end index and erase everything between them
Hey @ashishnnnnn
This problem deep dives into properties of substrings and numbers. so we need to remove all possible n*(n+1)/2 substrings from the string and sum up the decimal value of remaining shrinked string. For example remove 0 from 107 it becomes “17”==1*10 +7*1=17. Cool.
Calculate contribution of each digit in the possible sum is one way to solve to this problem…
lets say you want to calculate the contribution of ith digit. let this digit be d[i].
If we remove any substring from the front of the digit d[i]. then total substrings to remove ==(i*(i+1))/2. and for this substrings removal place value for d[i] still remains same as place value is counted from backwards. thus place value =n-1-i. thus total contribution if I remove substrings from front is
S1=10n−1−i∗((i∗(i+1))/2)∗d[i].S1=10n−1−i∗((i∗(i+1))/2)∗d[i].
where d[i] is the digit.
Now removing substrings from back of i. lets say total digits at back of i is k=(n-1-i). Now if I remove all k numbers then ith digit comes at 0th place value if I remove k-1 length substring from back then d[i] comes at 1st place value. If I remove k-2 length substring then d[i] comes at second position. thus it is building an AGP. Also notice k length substring at back=1, k-1 =2 , k-2 =3; thus this sequence goes like .
S=1∗101−1+2∗102−1+3∗102…k∗10k−1.S=1∗101−1+2∗102−1+3∗102…k∗10k−1.
so contribution of removal from back is S2= (S*d[i]).So overall contribution of d[i] is S1+S2 . Sum up this for all i digits . precompute this AGP sequence and for each i get answer in O(1).
Thus time complexity is O(N)
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.