Lovely Numbers of Charan (NPLQ19B) - Editorial

editorial
1

PROBLEM LINKS :

Contest : (CodeChef: Practical coding for everyone)

Setter : Charan Sriramula

Tester : Charan Sriramula

Editorialist : Charan Sriramula

DIFFICULTY :

Easy Medium

PREREQUISITES :

Digit DP

PROBLEM :

Given 3 integers L,R,K . We need to find the total number of integers in between L,R (inclusive) which satisfies the condition : absolute difference between any two consecutive digits of a integer should be atmost K.

EXPLANATION :

1.Let F(l,r) be the total no.of numbers in between land r (incl) which satisfies the given condition.
2.So we re write the above F(l,r) as F(1,r) - F(1,l-1) .First we find the total valid numbers from 1 to r and then we substract them from 1 to l-1. So we now focus on finding answer for F(1,n).
3.Lets say we are at a index i , if the prefix of numbern (from 0th index to i-1 th index ) is same as the prefix of the number we have formed till now (till i-1 th index) then at index i , we can only fill digits from 0 to digit_at_index_i_in_n . Else we can place any digit ( make sure that there are no leading zeroes).
4. This way we can ensure that the numbers formed are always <= n.
5. But we also need to ensure that the differeneceb/w any two adjacent digits is atmost K , so we use previously placed digit as one of the state in recurrence.
6. Lets say the previously placed digit is some pnow at current index we can only place digits whise absolute diff with p is atmost K.
7. So the reccurrence looks like dp(index, previous_digit, prefix_checker)
Place all valid digits at “index” i.e, abs(previous_digit - current_digit <= K) and evaluate prefix_checker and call this function.

Comment for any queries ! Happy Coding :slight_smile:

Digit Dp blog on CF : (Digit DP - Codeforces)

COMPLEXITY ANALYSIS :

Time Complexity : O( 20 \cdot 10 \cdot 2 \cdot 2 \cdot 10 ) per test case !

SOLUTION LINKS :

Setter 
#include<bits/stdc++.h>
using namespace std;
typedef long double ld;
typedef long long int ll;

const ll logx=30;
const ll N=3e5+5;
const ll M=10;
const ll mod=998244353;
const ll INF=1e9+5;
const double PI = 3.14159265358979323846;

#define ints(n) scanf("%d",&n)
#define intp(n) printf("%d\n",n)
#define longs(n) scanf("%intd",&n)
#define longp(n) printf("%intd\n",n)

inline ll mul(ll a, ll b){ return (a * 1ll * b) % mod; }
inline ll sub(ll a, ll b){ ll c = a - b; if(c < 0) c += mod; return c; }
inline ll add(ll a, ll b){ ll c = a + b; if(c > mod) c -= mod; return c; }

#define f first
#define s second
#define pb(x) push_back(x)
#define pf(x) push_front(x)
#define mp(x,y) make_pair(x,y)
#define GCD(a,b) __gcd((a),(b))
#define all(v) v.begin(),v.end()
#define bits(x) __builtin_popcountll(x)
#define LCM(a,b) ((a)*(b))/GCD((a),(b))
#define ms(dp,val) memset(dp,val,sizeof(dp))
#define fast ios_base::sync_with_stdio(false);cin.tie(NULL);
template<typename T> T power(T x,T y){T ans=1;while(y>0){if(y&1LL) ans=(ans*x)%mod;y>>=1ll;x=(x*x)%mod;}return ans%mod;}

#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
    cerr << name << " : " << arg1 << '\n';
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
    const char* comma = strchr(names + 1, ',');cerr.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);}

ll l,r,k;
vector<ll> vec;
ll dp[20][10][2][2];

void Digits(ll cur)
{
  vec.clear();
  while(cur){vec.pb(cur%10);cur/=10;}
  reverse(all(vec));
}

ll F(ll idx,ll las,ll f,ll s)
{
  ll res=0;
  if(idx==vec.size()){return 1;}
  if(dp[idx][las][f][s]!=-1){return dp[idx][las][f][s];}
  if(f)
  {
    for(ll i=0;i<vec[idx];i++)
    {
      if(idx==0){res+=F(idx+1,i,0,s|(i!=0));}
      else
      {
        if(!s){res+=F(idx+1,i,0,s|(i!=0));}
        else
        {
          ll dif=abs(las-i);
          if(dif<=k){res+=F(idx+1,i,0,s|(i!=0));}
        }
      }
    }
    if(!s){res+=F(idx+1,vec[idx],1,s|(vec[idx]!=0));}
    else
    {
      ll dif=abs(las-vec[idx]);
      if(dif<=k){res+=F(idx+1,vec[idx],1,s|(vec[idx]!=0));}
    }
  }
  else
  {
    for(ll i=0;i<=9;i++)
    {
      if(idx==0){res+=F(idx+1,i,0,s|(i!=0));}
      else
      {
        if(!s){res+=F(idx+1,i,0,s|(i!=0));}
        else
        {
          ll dif=abs(las-i);
          if(dif<=k){res+=F(idx+1,i,0,s|(i!=0));}
        }
      }
    }
  }
  return dp[idx][las][f][s]=res;
}

int main()
{
  ll t;
  cin>>t;
  while(t--)
  {
    ms(dp,-1);
    cin>>l>>r>>k;
    Digits(r);
    ll ans=F(0,0,1,0);
    ms(dp,-1);
    Digits(l-1);
    ans-=F(0,0,1,0);
    cout<<ans<<endl;
  }
}
2 Likes