ENCODING - Editorial

editorial
, , , , ,
122

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!

3 Likes
123

Now that’s documentation! Really well explained. Thanks for the effort. :smile:

4 Likes
124

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…

  1. I calculated count in 2 states. What is the need of 3rd state ?
  2. What exactly is stored in dp[i][D][E] ? The solution of the subtree rooted at i (recursively) or the solution until i ?
  3. I didn’t understand how to compute that count and why is it actually needed ?
  4. 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 ! :pray:
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.

1 Like
125
  1. 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.
  2. dp[i][D][E] will store answer for number formed by string in range [1,i].
  3. If you get count, then you can get final answer as digit*count*10^k where (k is the appropriate power of 10) right?
  4. A block is a contiguous sequence of same digits.

What is it you are not clear with? The states? The recurrence? Or the implementation?

126

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

127

Yes, you got it right.

128

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.

129

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.

1 Like
130

hey how you have calculated loss I am very new to cp can you provide me any link to understand this I am unable to understand your code

131

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