thanks for answering all my questions
I can’t understand the line equal_next=(equal & next_digit>vec[idx]), shouldn’t it be (equal & digit>vec[idx])?
We are seeing if after placing next digit what is the state of equal.
You said I can request for an unapproved editorial of CHGORAM and SYNBAC from you. How do I do that?
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
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
Did you not take part in yesterday’s Cook-Off?
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 Long Challenges only, for me!
2.5 hours for 5 questions? I’d spend longer than that agonizing over variable names XD
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.
Thanks for the very kind words 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
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
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!
Now that’s documentation! Really well explained. Thanks for the effort.
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
Yes, you got it right.
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 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
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