ENCODING - Editorial

PROBLEM LINK:

Div1
Div2
Practice

Setter- Claudiu Babin
Tester- Suchan Park
Editorialist- Abhishek Pandey

DIFFICULTY:

Medium

PRE-REQUISITES:

Digit DP, Dynamic Programming (in general)

SYMBOLS USED:

There are lot of symbols used in this editorial, which are defined below.

Let me define the following variables-

  • UL= Upper Limit for x.
  • i= Current Index in the number.
  • i_{next}= Next index in the number
  • D_{next}= The next digit we are placing at the next index.
  • D= The digit we are considering placed at Current Index.
  • E_{Next}= If after placing the next digit, is the number equal to UL if we consider all digits from Most Significant Digit to digits at the position we placed D_{next} at. This takes a value of 1 if equality holds, else 0. A value of 0 denotes that the number is < UL
  • E= If considering digits from Most Significant Digit to D placed at Current Position, is my number equal to UL. Like above, takes value of 1 or 0 based on if equality holds. A value of 0 tells that the number is < UL

I know they are a lot of symbols, but we will be using them to denote things in the entire editorial, so please bear with me!

PROBLEM:

Given a function f as defined in the problem, find the value of f(x) for \forall x , x\in [L,R]

QUICK-EXPLANATION:

Key to AC- Realize that it is a classical Digit DP problem.

Realize that the value for f(x) for range [L,R] = Value of f(x) in range [1,R]- Value of f(x) in range [1,L-1]. Hence, we only need to implement this such that we are able to find all valid x \leq R, and then later reuse to find all valid x \leq L-1 and subtract it from the answer.

Realizing this, define a 3-D dp table of form dp[position][digit \ placed][equal \ or \ not].

With above defined, we can frame our dp recurrence as below, with obvious check of not making x > UL

  • If D_{next}==D:
    dp[i_{next}][D_{next}][E_{Next}] =\sum_{E=0}^{E=1} dp[i][D][E] as then no new block is formed. And contribution of older blocks is already computed in previous states.
  • If D_{next} \neq D:
    dp[i_{next}][D_{next}][E_{Next}] =\sum_{D=0,D \neq D_{next}}^{D=9} \sum_{E=0}^{E=1} (dp[i][D][E] + Count \ of \ valid \ x\ with \ D_{next} \ at \ i_{next} * Appropriate \ power \ of \ 10 *D_{next}).

Appropriate power of 10 can easily be obtained from N_{UL}-i where N_{UL} is number of digits in UL and i follows 1-based indexing. With the power calculated, we can easily find 10^{N_{UL}-i}. In terms of time complexity, it is better to precompute all required powers of 10 in O(N) in an array and later use it.

To find the count of valid x \leq UL considering things only upto index i, again, simply repeat the recurrence!!

Define num[index][digit][equal] as table and notice that-

num[i_{next}][D_{next}][E_{Next}]= \sum _{D=0}^{D=9} \sum_{E=0}^{E=1} num[i][D][E] - with the obvious check that we are not making x > UL. Remember that I am starting from most significant digit, and considering all numbers that can be formed by considering things in range [0,i] only. The answer for index (i+1) will be calculated using our dp, and so do not worry about it right now!

The intuition of recurrence is can now be summarized as-

I can place D_{next} at end of all valid x which-

  • End with any digit D which is less than UL already. ( E=0, D \in [0,9] \implies \sum _{D=0}^{D=9} num[i][D][0] )
  • End with all digits \leq Digit at i’th position in UL if my number so far is equal to UL so far. Let the i’th digit at UL by D_i. So this case is for (E=1,D\in[0,D_i] \implies \sum_{D=0}^{D=D_i} num[i][D][1] )

With these 2 calculated, we can calculate the final answer and be done with the question! The final recurrence obtained is-

  • If D_{next}==D:
    dp[i_{next}][D_{next}][E_{Next}] =\sum_{E=0}^{E=1} dp[i][D][E] as then no new block is formed. And contribution of older blocks is already computed in previous states.
  • If D_{next} \neq D:
    dp[i_{next}][D_{next}][E_{Next}] =\sum_{D=0,D \neq D_{next}}^{D=9} \sum_{E=0}^{E=1} (dp[i][D][E] + num[i][D][E]* 10^{N_{UL}-i} *D_{next}).

EXPLANATION:

First of all, if you are new to digit dp, or if the quick explanation felt completely alien to you, visit the Digit dp blog linked at Codeforces. This problem is pretty standard application of digit dp, so make sure to read and drill the pre-requisites in your head :slight_smile: .

Next thing, the quick explantion has everything needed to solve the problem. We will just get into the various “Why” and “How” of the stuff mentioned there and expand along those lines in the explanation.

You will very much benefit from the editorial if you are able to achieve the following-

  • Read and understand the digit dp blog at pre requisites.
  • Understand a little dp in general. Classical problems like LIS, LCS are a good start.

Now, my hands had been itching to write a digit dp editorial since loong - simply because not a lot of good content is available on internet. So bear with me as this editorial is going to have many sections. We will discuss the following-

  • Some basic introduction to digit dp, followed by How do I know its digit dp? How do I break the query into Ans_{[L,R]} = Ans_{[1,R]}- Ans_{[1,L-1]}
  • How do I know the number of states? How do I see what states I need?
  • Figuring out the dp-recurrence.

Cool and clear? Read the pre-requisites if you’re new? Great, Lets begin!

Digit DP - Intro

The first thing I want to say here is, if you are one of those guys who feel that “Digit DP is some other branch of Dynamic Programming which I need to specifically learn” then just take a minute and throw that misconception into the nearest thrash can.

Digit dp is nothing but a normal dynamic programming. The only reason this got a separate name is because the same ideology/format is followed to solve a LOT of problems based on it. All that you need to learn this is understanding basic dynamic programming in first place, and then looking at the blog I linked in the pre requisites. If you know basic dynamic programming, you will realize that you are able to solve/invent digit dp solutions yourself without realizing it!

Now, onto how do I know that this was a digit dp question? Simple, because this question shares the common signs of a digit dp question! We need to tell if some numbers, in a huge range, satisfy some property or not. And frankly, no clear number theory stuff comes to mind, especially something which would run for numbers upto 10^{100000}. If you look at the link in pre-requisite, you will notice similarities.

Now, the query part. I think we all agree that its trivial to see that since we want the sum of f(x) in range [L,R], we can easily break it down to sum of f(x) in range [1,R]- sum of f(x) in range [1,L-1].

States

Now, lets talk about states.

A very common question in all dynamic programming problems is that-

“How do I know that its 1-D dp, or 2-D dp, or a 3-D dp?”

Simple solution - Don’t think in terms of number of states! First, think of what things do you require to differentiate between all the states!

If you are reading this section, I assume we are clear on why it is a DP problem. So, jumping straight to the point, lets think of what things we need to know to be able to differentiate between the states-

  • Obviously the position where we are placing the digit matters. Placing a digit at somewhere near the starting of the number is different from placing it somewhere in middle etc.
  • We also need to know what digit we are placing! For each digit, there are different contributions to the answer!
  • Realize that we cannot place all digits from 0-9 just like that. We need to make sure that the number must be \leq UL or not! Hence, we also need to keep track of if the number became < UL already due to some previous digit we placed or if its still ==UL so far.

Hence, we get 3 states-

  • The position i , from [1,N]
  • The digits d we are placing, from [0,9]
  • If the number is still equal to UL or has become smaller than UL already - A boolean value having value [0,1]

Think over it a little, and see what we are able to see that we are able to differentiate between all the states in this manner. Also, note that the number of states is feasible! We just calculate answer for the state and use memoization.

DP- Recurrence

Let us now discuss the DP- Recurrence.

In quick explanation, we saw something as “Count of valid x \le UL with digit D_{next} at given index”. Lets first discuss this.

I will make one thing clear, its not a compulsion to make 2 tables here - we are doing that only for improved clarity. Exact number of dp-tables and states depend on what insights and observation you made and hence on the direction of your approach.

Lets make a table num[index][digit][equal\_\ or\_\ not] which denotes that "Number of numbers I can form considering digits in range [0,index], ending with “digit” with status of equality as defined in variable "equal \ or \ not"".

The recurrence for this is easy to derive!

Lets say I know the count of numbers ending with digit D \in[0,9] at index (i-1). Let me denote it by G_{i-1,D}. Similarly, count of numbers ending with digit D at index i is G_{i,D}.

We see the following easily-

  • If my number x has already become smaller than UL, then the count of numbers ending with digit D at index i is sum of numbers ending with any digit D_{prev} \in[0,9] at index (i-1). Meaning, G_{i,D}= \sum_{D=0}^{D=9} G_{i-1,D}
  • If my number x has so far been equal to UL, then G_{i,D} = \sum_{D=0}^{D=D_i} G_{i-1,D} where D_i is the corresponding digit at index i in UL. The intuition is same as above.

Now, how to comfortably implement it? The easiest hack is to include the state of equality in the dp-table as well!

So let me define num[index][digit][equal\_\ or\_\ not] as G_{i,D,E} where each variable has same meaning as told in quick explantion.

Our recurrence just transforms to-

  • \large G_{i_{next},D_{next},E_{next}}= \sum_{D=0}^{D=9} G_{i,D,0} + \sum_{D=0}^{D=D_i}G_{i,D,1} where we know i_{next} , D_{next} and E_{next} when placing the next digit, and D_i is the corresponding digit at UL

With this calculated, all that is left is to simply do what the problem says!! Take some time to get this recurrence if you’re facing any doubts.

Create the final dp[index][digit][equal] table similar to above. Now, according to the question, 2 cases can arise-

  • D_{next} == D - For this case, no new contribution is done to the dp-table as a block of digits cannot contribute multiple times. So we get dp[i_{next}][D_{next}][E_{Next}] =\sum_{E=0}^{E=1} dp[i][D][E] - with the check that x does not exceed UL
  • D_{next} \neq D - For this case, a new block is formed, so we add the appropriate contribution here. We get dp[i_{next}][D_{next}][E_{Next}] =\sum_{D=0,D \neq D_{next}}^{D=9} \sum_{E=0}^{E=1} (dp[i][D][E] + Count \ of \ valid \ x\ with \ D_{next} \ at \ i_{next} * Appropriate \ power \ of \ 10 *D_{next}).
    The “syntax” or “format” of this dp recurrence is “Sum of previous contributions + Valid Count * Appropriate power of 10 * Digit we placed” Note that, we can simply pre compute the powers of 10 to use at start of our program, so its easily available. And the “Valid Count” is already calculated as seen in our previous discussion above.

The final answer for this can be easily extracted as \sum_{D=0}^{D=9} \sum_{E=0}^{E=1} dp[N_{UL}][D][E]. Note that our UL, as seen above in query decomposition part, is R and L-1. To get answer for L-1 even more easily, realize that you don’t need values of our table where E=1 , i.e. where x==L. The E=0 accounts for all x < L.

The setter has implemented it in a very neat, iterative manner. I’d like to encourage you to give a try, and then compare it with setter’s code given below-

Setter''s DP
num[0][0][1] = 1;
for(int idx = 0;idx < sz(vec);idx++)
{
	for(int digit = 0;digit < 10;digit++)
	{
		for(int equal = 0;equal < 2;equal++)
		{
			int idx_next = idx + 1;
			for(int next_digit = 0;next_digit < 10;next_digit++)
			{
				if(equal && (next_digit > vec[idx])) break;
				int equal_next = (equal & (next_digit == vec[idx]));
				add(num[idx_next][next_digit][equal_next],num[idx][digit][equal]);
				add(dp[idx_next][next_digit][equal_next],dp[idx][digit][equal]);
				if(next_digit != digit) add(dp[idx_next][next_digit][equal_next],(((num[idx][digit][equal] * p[(sz(vec) - 1 - idx)]) % mod) * next_digit) % mod);
										// ^^ if the next digit is equal to the current one, we shouldn't change the sum, else we should add 10^idx * next_digit.
			}
		}
	}
}

SOLUTION

Setter
# pragma GCC optimize("Ofast")
# pragma GCC optimization ("unroll-loops")
# include "bits/stdc++.h"
std::pair<int,int> DR[] = {{-1,0},{0,1},{1,0},{0,-1},{-1,1},{-1,-1},{1,1},{1,-1}};
# define ll long long
# define clock (clock() * 1000.0 / CLOCKS_PER_SEC)
# define rc(s) return cout << s,0
# define rcg(s) cout << s;exit(0)
# define _ ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
# define db(x) cerr << #x << " = " << x << '\n'
# define pb push_back
# define mp make_pair
# define all(s) s.begin(),s.end()
# define sz(x) (int)((x).size())
using namespace std;
 
 
// SOLUTION STARTS HERE
# define int ll
 
 
const int mod = 1e9 + 7;
 
int num[1 << 17][10][2],dp[1 << 17][10][2]; // dp[index][digit][equal_or_not] - the sum of f(x) up to index, such that the last digit is digit and it is still equal to the initial number iff equal_or_not == 1
int p[1 << 17];
int t;
 
void add(int &x,int val)
{
	x += val;
	if(x >= mod) x -= mod;
}
 
pair<int,int>f(vector<int>vec) // pair<sum of all f less than x,sum of all f less than or equal to x>
{
	for(int idx = 0;idx <= sz(vec);idx++)
	{
		for(int digit = 0;digit < 10;digit++)
		{
			for(int equal = 0;equal < 2;equal++)
			{
				dp[idx][digit][equal] = num[idx][digit][equal] = 0;
			}
		}
	}
	num[0][0][1] = 1;
	for(int idx = 0;idx < sz(vec);idx++)
	{
		for(int digit = 0;digit < 10;digit++)
		{
			for(int equal = 0;equal < 2;equal++)
			{
				int idx_next = idx + 1;
				for(int next_digit = 0;next_digit < 10;next_digit++)
				{
					if(equal && (next_digit > vec[idx])) break;
					int equal_next = (equal & (next_digit == vec[idx]));
					add(num[idx_next][next_digit][equal_next],num[idx][digit][equal]);
					add(dp[idx_next][next_digit][equal_next],dp[idx][digit][equal]);
					if(next_digit != digit) add(dp[idx_next][next_digit][equal_next],(((num[idx][digit][equal] * p[(sz(vec) - 1 - idx)]) % mod) * next_digit) % mod);
											// ^^ if the next digit is equal to the current one, we shouldn't change the sum, else we should add 10^idx * next_digit.
				}
			}
		}
	}
	pair<int,int>ans = {0,0};
	for(int digit = 0;digit < 10;digit++)
	{
		ans = mp((ans.first + dp[sz(vec)][digit][0]) % mod,(ans.second + dp[sz(vec)][digit][0] + dp[sz(vec)][digit][1]) % mod);
	}
	return ans;
}
 
int32_t main(){_
	//freopen("input","r",stdin);
	p[0] = 1;
	for(int i = 1;i <= 100005;i++) p[i] = (p[i - 1] * 10) % mod;
	cin >> t;
	while(t--)
	{
		int lnum,rnum;
		string l,r;
		vector<int>vecl,vecr;
		cin >> lnum >> l;
		cin >> rnum >> r;
		for(auto it : l) vecl.pb(it - '0');
		for(auto it : r) vecr.pb(it - '0');
		cout << (mod + f(vecr).second - f(vecl).first) % mod << '\n'; // sum of f(x) for x in l..r = (sum of f(x) for x in 1..r) - (sum of f(x) for x in 1..l - 1) 
	}
	return 0;
}
Tester(KOTLIN)
const val MOD = 1000000007

class ModInt constructor(n: Long) {
  private val v = (n % MOD + MOD) % MOD

  override fun toString(): String = v.toString()

  operator fun plus(other: ModInt) = ModInt(v + other.v)

  operator fun minus(other: ModInt) = ModInt(v - other.v)
  operator fun unaryMinus() = ModInt(-v)

  operator fun times(other: ModInt) = ModInt(v * other.v)
  operator fun times(other: Int) = ModInt(v * (other % MOD + MOD))
  operator fun times(other: Long) = ModInt(v * (other % MOD + MOD))

  fun inv(): ModInt = when(v) {
    1L -> ModInt(1)
    else -> ModInt(MOD % v).inv() * (MOD - MOD / v)
  }
  operator fun div(other: ModInt) = this * other.inv()
  operator fun div(other: Long) = this * ModInt(other).inv()
  operator fun div(other: Int) = this * ModInt(other.toLong()).inv()
}

const val MAX_LEN = 100000
val POW10 = run { var pw = ModInt(10).inv(); List<ModInt>(MAX_LEN * 2 + 50) { pw *= 10; pw } }
val COEF_9_20 = ModInt(9) * ModInt(20).inv()
val COEF_99_200 = ModInt(99) * ModInt(200).inv()

fun f(s: String): ModInt {
  var ret = ModInt(0)
  val l = s.length
  for(i in 0 until l) {
    if(i == 0 || s[i] != s[i-1]) {
      ret += POW10[l - i - 1] * (s[i].toInt() - 48)
    }
  }
  return ret
}

fun g(s: String): ModInt {
  var ret = ModInt(0)
  val l = s.length
  for(i in 1 until l) {
    if(i == 0 || s[i] != s[i-1]) {
      ret += POW10[l - i - 1] * (s[i].toInt() - 48)
    }
  }
  return ret
}

val tb0 = List<ModInt>(MAX_LEN+1) { len -> if(len >= 1) POW10[len * 2] * 99 / 200 - POW10[len] * 9 / 20 else ModInt(0) }
val tbs = List<ModInt>(MAX_LEN+1) { len -> if(len >= 1) -POW10[2*(len-1)] else ModInt(0) }

fun solve(s: String): ModInt {
  var ret = ModInt(0)
  var pref = ModInt(0)
  for(i in 0 until s.length) {
    for(c in 0 until s[i] - '0') {
      // tb[len-i-1][c]
      ret += pref * POW10[s.length - i - 1]
      if(i == 0 || s[i-1] - '0' != c) {
        ret += (POW10[s.length - i - 1] * c) * POW10[s.length - i - 1]
      }
      ret += tb0[s.length - i - 1] + tbs[s.length - i - 1] * c
    }
    if(i == 0 || s[i] != s[i-1]) {
      pref += POW10[s.length - i - 1] * (s[i] - '0')
    }
  }
  ret += pref
  return ret
}

fun main(args: Array<String>) {
  val _NUM_TESTS = readLine()!!.toInt()
  require(_NUM_TESTS in 1..10)

  repeat(_NUM_TESTS) {
    val (Lnum, L) = readLine()!!.split(" ")
    val (Rnum, R) = readLine()!!.split(" ")
    require(L.length in 1..100000)
    require(R.length in 1..100000)
    require(L.length == Lnum.toInt())
    require(R.length == Rnum.toInt())
    require(L.all{ it in "0123456789" })
    require(R.all{ it in "0123456789" })
    require(L[0] != '0')

    println(solve(R) - solve(L) + f(L))
  }
}

Time Complexity=O(N)
Space Complexity=O(N)

CHEF VIJJU’S CORNER :smiley:

With respect to the statement below, answer the following questions-

  • “An alternate way to solve the question is that, simply use dp[i_{next}][D_{next}][E_{Next}] =\sum_{D=0,D \neq D_{next}}^{D=9} \sum_{E=0}^{E=1} (dp[i][D][E] + Ct(D_{next},i)* Appropriate \ power \ of \ 10 *D_{next}) where Ct(D_{next},i) is total number of valid numbers possible with digit D_{next} at index i.”
    • Comment on feasibility of this solution. Is this solution Dynamic Programming?
    • Highlight about how you plan to calculate Ct(D_{next},i) or argue why calculating it is difficult.
    • Our final answer by dp comes out to be correct. How does dp account for it? (Hint - Previous contribution is added for every D_{next} - i.e. it is added multiple times to accommodate for increase in digit!)
Setter's Notes

We can notice that the sum of f(x) for x in L..R = (sum of f(x) for x in 1…R) - (sum of f(x) for x in 1…L-1).

We can calculate sum of f(x) for x in 1..K using dp. We will denote dp[index][digit][equal\_or\_not] - the sum of f(x) up to index, such that the last digit is digit and it is still equal to K iff equal_or_not == 1. With being still equal to K, I mean the digits up to index are the same as the digits in K up to index. Also, note that here, index 1 is the leftmost digit, as opposed to the definition in the statement. We go through the digits from the most significant digit, so that we can do it lexicographically. We should also use num[index][digit][equal\_or\_not] which is the same as the dp array, but stores only the number of possible numbers that satisfy the conditions in the states. The transitions become quite straightforward .

Ending Notes

I know this editorial is slightly longer than required - it just becomes a little hard to give the intuition behind the dp you used. That being said, the point of editorial being lengthy was to make sure you people understand it, so please point out any parts which are unclear and which you feel can be improved!

Clarification on purpose of E and UL

We broke down query into 2 parts right? One for calculating answer for upto R, and then upto L-1. UL is the appropriate upper bound, i.e. either R or L-1 (or L - depending on your implementation) depending on our need. Basically UL is the upper bound for which we are calculating answer.

E basically tells if "After placing this digit, is my number equal to UL at indices [0,i] " or more simply, "Are all digits in range [0,i] in my current number same as that of UL".

E_{next} tells the same for (i+1) if we place the digit d there. You may refer to setter’s solution.

Related Problems
22 Likes

Here is my code without using DP.simple string processing in O(n)
Solution

9 Likes

Nice!

But pure code with no explanation or comments is useless to the majority. Can you explain your approach and why it works?

6 Likes

I will prepare explanation in elegant way within sometime.
Thank you.

4 Likes

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

Here’s My code i don’t know if it’s same as editorial or not but here’s what i did.

  1. The f(x) <= (x)
  2. So f(L) + f(L+1) …f( R ) <= L + L+1 …+ R
  3. Now my Approach was to find ps1 = f(1) + f(2) …f(L-1)
    and ps2 = f(1) + f(2) …f( R )
  4. Now find ps2-ps1 lets call this “Something”
  5. Subtract this “SOmething” from L + L+1 … R
1 Like

Thanks!!

I am very much interested in your method!! Ultimately, a code only tells me what you did - not why you did it :slight_smile:

1 Like

Yeah, but this is just the query decomposition part. Real question is how you found ps1 and ps2 :stuck_out_tongue:

1 Like

Well a if there is a repetetion of digits anywhere in number then it means that it will contribute to this “something.” Say 123445 here 44 is repeating so the contribution to something will be
( 122*10 + 5) * 4 * 10

I checked contributions for 11,22,33,44,55,66,77,88,99 at every position if u see my code

and used formula to find sum of L to R and subtracted this something
Hard to explain while typing but i think those who have solved would get me :laughing:

1 Like

I had also solved this way but the problem is the number of numbers needed to be calculated in this way were huge .So,got only partially correct.

1 Like

Yeah but you had to find answers % 1000000007 so i stored numbers in such a way from beginning. In my code i have 2 array for each L and R. at any position I just get my (numbers.less)mod 100000007 from that array

for example if the number is 123456

this my array would be like
prefix[0]= 1 mod p;
prefix[1]= 12 mod p;
prefix[2]= 123 mod p;
prefix[3]= 1234 mod p;
prefix[4]= 12345 mod p;

This is the code snippet which did that.

for(int i=1;i<l_dgt;i++){
            csuma[i]=((csuma[i-1]*10)%mod+Character.getNumericValue(l.charAt(i)) )%mod;
}

same for last digits, you create a suffix array

1 Like

ohh!! Nice
I had also calculated prefix and suffix multipiers in my AC solution but instead of storing them in an array I updated their value while tracing the array.

That would have been more efficient then. Great. :+1: :smile:

Did this without DP, I will share my algo -

There’s three cases to be considered
strictly decreasing -
consider the string 5432 ( R) the ans (L being 1) should be 14630495
now if you take a close look sum of all the nums upto 5432 is 14756028

The difference being 125533.
The algo is all about calculating the difference, i.e n x (n+1)/2 - ans

How to calculate it for strictly decreasing nums ?
heres how it follows-
5432 -> 500x499/2 + 40x39/2 + 3x2/2 = 125533 (skip the last digit)

for strictly increasing,
5678-> 500x499/2 + 500x100 + 60x59/2+ 60x10+7x6/2+7x1 = 177148

now for nums with duplicate digs
1111 -> 100x99/2 + 100x12 +10x9/2 + 10x2 + 1x0/2 +1x1 = 6216
Where did I get the 100x12 ? (1)1((11)+1), same for 10x2 -> 1(1)1(1+1)

My solution https://www.codechef.com/viewsolution/25826769

Now calculate the both L-1 and R in this fashion and the ans is the difference.
Now build this up in reverse order while taking MOD

Also apologies this is really not the nicest explanation. But you can get an idea.

8 Likes

My solution was purely logical. Please correct me if I am wrong here
Idk if this is digit dp indirectly.

  • I break question into two subproblems i.e. ans(L,R) = ans(1,R) - ans(1,L) + find(L) .
    PS: we can also do ans(1,R) - ans(1,L-1) but instead of subtracting 1 from string, I did brute force check for L and added that part.
  • Now let’s see how to find ans(1,N) where N can have 10^5 digits.
    Let’s assume that N can have D digits.
    Now ans(1,N) will have contribution of each position P where 0 \le P \lt D.
    And each position will have some contribution of digit m where 1 \le m \le 9 ( because 0 will contribute 0).
    Hence,
    ans(1,N) = \sum_{P=1}^{D-1} \sum_{m=1}^{9} 10^P*m*ans2(m,P,N).
    Where ans2(m,P,N) denotes number of times digit=m will be at Pth position and digit at (P+1)th position either don’t exist or is not equal to m in all natural number less than equal to N.
  • So now if we can solve ans2(m,P,N) in O(1) then all over complexity will be O(D*9)=O(D) where D is number of digits in R.
  • Now let’s understand how to approach ans2(m,P,N).
    ans2(m,P,N) = ans3(m,P,N) - ans4(m,P,P+1,N)
    where ans3(m,P,N) denotes number of times Pth digits = m in all natural numbers less than equal to N.
    and ans4(m,P,P+1,N) denotes number of times both pth and (p+1) th digit are equal to m.
  • Now we can easily solve ans3(m,P,N) and ans4(m,P,P+1,N) in O(1) after we precompute prefix and suffix values. Meaning
    if N=12451
    I will precompute ( prefix part)
    10000
    12000
    12400
    12450
    12451
    and I will also precompute (Suffix part)
    00001
    00051
    00451
    02451
    12451
    Note that precompute those values under \mod 10^9+7.
    Time complexity of this precomputation is O(D) as well
How to solve ans3(m,P,N) and ans4(m,P,P+1,N) ?

/10 , /100 helps :stuck_out_tongue:
If you need more hints then let me know I will try to explain.

Here is the link to my solution :
https://www.codechef.com/viewsolution/25676942
Neater code with comments :
https://www.codechef.com/viewsolution/25943813
PS: I can write a neater code as well. Ping me if required.

4 Likes

Broooo, i did the same…so my approach was not alone :smile:

btw don’t you think ans(L,R)=ans(1,R)−ans(1,L -1) ?

1 Like

same as me ?
I can’t see whom are you replying to. Discuss issue :frowning:
Yup let me edit that.

1 Like

@l_returns replying to you! :laughing:

1 Like

okay I am also glad that you did same approach :slight_smile:

1 Like

can anyone share video editorial for similar problem. It would be great help

3 Likes

You mean video editorials of problems listed under related problems?