Dont worry. I am taking my time to make sure that everyone who is searching for a plausible solution gets it at the editorial in first read.
Some things in it are…tricky to decide. I have a written version right now as well, but its not good enough and I am improving it to make it more user friendly. Watch out for my updates on invitation thread on when the unapproved one can be requested!
Hey guys, I’m trying this since a long time and wasn’t able to understand the editorial completely. So I came up with my own solution after reading the codeforces blog on Digit dp. Here is my solution for which I tried some testcases and they were correct. Link to my Encoding Solution - Getting TLE
I have some questions…
I calculated count in 2 states. What is the need of 3rd state ?
What exactly is stored in dp[i][D][E] ? The solution of the subtree rooted at i (recursively) or the solution until i ?
I didn’t understand how to compute that count and why is it actually needed ?
I didn’t understand some keywords like “new block is formed”…What is a block ?
It would be helpful if someone takes time and replies to my questions and I’m seriously stuck on this problem since a long time. Please help me out !
PS : I read the blog and coded it, but was not able to understand the idea of editorialist. @vijju123 If you can, Please spare some time to reply to this as I’m completely confused.
Regarding states, albeit different implementations may follow different states, I felt it having same set of states as the dp-table is pretty intuitive and easy to define and calculate.
dp[i][D][E] will store answer for number formed by string in range [1,i].
If you get count, then you can get final answer as digit*count*10^k where (k is the appropriate power of 10) right?
A block is a contiguous sequence of same digits.
What is it you are not clear with? The states? The recurrence? Or the implementation?
But I didn’t understand what is count for ?
Can you provide an example…
This is what I’m thinking of it as,
If UL = 12, then the numbers 02 and 12 have the digit - 2 at index 0 from the left, so the digit - 2 at that position always yields the same contribution, so we count all such occurrences, which is 2 here (digit 2 is occurring 2 times) and multiply that count with the contribution. Is this right ? Or is its purpose different here ? @vijju123
Does anybody who didn’t solve the problem after reading this tutorial solved the question? I mean editorial is best explained and I have read it fully but can’t still get it on my mind.
Did you try to take a look at setter’s solution and map the editorial to it? That can help.
I did not add an implementation section in this editorial because I wanted users to figure it out on their own, but in case someone isnt able to then setter’s code has every thing explained in editorial.
Hey am also getting the same verdict on my submission… ( RE (SIGSEGV) from 3-12 in the third subtask ). I guess my logic is same as that of editorial, i am not able to find why is it happening… Can you please help ?
My Submission: https://www.codechef.com/viewsolution/50145927