ENCODING - Editorial

editorial
, , , , ,
112

thanks for answering all my questions :wink: :+1:

113

I can’t understand the line equal_next=(equal & next_digit>vec[idx]), shouldn’t it be (equal & digit>vec[idx])?

114

We are seeing if after placing next digit what is the state of equal.

115

You said I can request for an unapproved editorial of CHGORAM and SYNBAC from you. How do I do that?

1 Like
116

Please upload CHGORAM, I’ve been searching for a plausible solution for over a week now, Or you could just submit your own code with few comments first, and later add an editorial. So we could think about the solution in the mean time

1 Like
117

There’s a Video Editorial for CHGORAM here:

and, though people are probably sick of me posting it by now, here’s my fully-documented submission (highly-commented code, plus high-level, Editorial-style overview). Not been proof-read :slight_smile:

https://www.codechef.com/viewsolution/25937827

4 Likes
118

Did you not take part in yesterday’s Cook-Off?

119

No, I’m a slow, slow old man and there’s no way I’d be able to compete with all you young whipper-snappers :slight_smile: Long Challenges only, for me!

2.5 hours for 5 questions? I’d spend longer than that agonizing over variable names XD

4 Likes
120

:smiley: but you seem to be a good problem solver, would have given us ‘young whipper-snappers’ a good competition. Anyway, I know you are one of the Competitive Programmers who writes very clean code, probably a habit you carried over from your experience as developer(saw your LinkedIn profile). So, you are an asset to the community. Nevertheless, see you in September Long and hitting 4 or higher star this time.

3 Likes
121

Thanks for the very kind words :slight_smile: I’m a very inconsistent problem solver - I’m quite often stumped for a long time over surprisingly simple things (coming from Hackerrank, it was a real eye-opener seeing what problems were classified as “Easy” here :)) - this is really not a good recipe for success with short challenges :slight_smile:

Anyway, while I’m here - I’d like to say how much I love the long-form format here - so much less stressful than Hackerrank, where in their equivalent (the “Week of Code”) you still only have one day to solve a challenge (if you want full marks on it), plus they have the “Additional Testcases” which just add to the pressure! I couldn’t believe it when I saw that you had a full 10 days to solve all the challenges here. It’s great :slight_smile:

4 Likes
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