Encoding Approach (August Long Challenge)

Can anybody help in deriving the approach , who easily or eventually comes to the solution of encoding?
(Encoding) Aug Long Challenge

1 Like

It is a typical digit DP problem. I think you’ll like the editorial. :smiley:

5 Likes

Waiting for your editorial :smile:

Hope so… I tried it from the day 3 and was still unable to come up with any concrete logic. :expressionless: . Can you or anybody provide me pre-requisites to solve these type of problem unless this is pure logical question ?

hope this helps.

I haven’t gotten around to writing the high-level overview, yet, but hopefully the code is clear enough to figure out the approach :slight_smile:

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

2 Likes

Could you please provide which test it is failing, because i have stress tested it a lot and compared with accepted solution. please help me, at least provide one counter case.thanks in advance.
solution

YOU CAN VIEW MY SUBMISSION IT USES ONLY PRECOMPUTATION AND HASHING PART WHICH IS NOT AT ALL A SUPER DYNAMIC PROGRAMMING . look at the solution…
encoding precomputation algo

1 Like

I have been in coding for a 3 months now and saw these type of codes for most great coders. Where is these types of codes can be learned please tell if any great site. Like templates high order functions and so many high level things in your code. Thank you. Lovely code!

1 Like

You’re too kind :slight_smile:

In terms of language features, really any good introductory textbook for C++ (very preferably covering C++11 onwards!) will contain all the concepts I’ve used.

The rest is just naming and organisation - I try to make it as close to readable-in-English as I can get, and break out discrete bits of functionality so that they don’t clutter up the high-level flow of the code.

The absolute best piece of advise I’ve ever been given is: “Write code as if the person who will be maintaining it in the future is a psychopath - who knows your home address.” :wink:

1 Like

112 lines in python with brute force and optimized both

1 Like

Nice one… But if u document it properly with comments and logic behind certain lines… It will be more help… Although it is already clean code to look at … Thanks :slight_smile:

I always code clean as code is self explanatory I think…thanks

I haven’t read the editorial yet but what I did was :
Make 2 dp arrays, one denoting how many lesser numbers on left side are possible under modulo of the ith digit of given number (i hope you got the part when we find for (1,r) - (1,l) + (l, l) which would be our answer ) as well as for the right side (2nd dp) but on right side, also find number of greater numbers possible than right side (which is trivial after you find the lesser part for the right side, think about it a bit ), and then apply some Maths about if ith digit is a particular digit, and possible left and right parts, with subtraction about if ith and (i-1)th digits are same (which we would have already included in our answer ), and add all these possibilities to get the answered under modulo.

1 Like

permutations see this

Please tell us your approach not your solution because your solution are never going to help us anyway without approach.

My approach do not use DP.

Let’s suppose N = 10^k - 1, \forall k big enough.

f(N) = (\sum_{i=0}^9i)(10^{2(k-1)}+9(10^{k-2})\sum_{i=2}^k10^{k-i})

which can be written in a better form of course.
The same idea allow us to compute f(N) for N = x(10^k) - 1, 1 \le x \le 10 in a similar way.

Now let’s take N = d_1d_2...d_k, where d_i is the i_{th} most significant digit.
For each i we know how to find f(d_i(10^{k - i}) - 1).
Now, let N' = d_{i+1}d_{i+2}...d_{k}, we have to add d_i(10^{k-i})(N') and f(N'), that we can find by recursion.

This is not the whole algorithm of course. Sometimes we should subtract something but now i have not enough time to give more details.