Help in a DP problem

→ Pay attention

Before contest
CodeTON Round 9 (Div. 1 + Div. 2, Rated, Prizes!)
4 days
Register now »

*has extra registration

→ Streams

DP Bitmask - Topic Stream

By Shayan

Before stream 07:27:31

View all →

→ Top rated

#	User	Rating
1	tourist	4009
2	jiangly	3823
3	Benq	3738
4	Radewoosh	3633
5	jqdai0815	3620
6	orzdevinwang	3529
7	ecnerwala	3446
8	Um_nik	3396
9	ksun48	3390
10	gamegame	3386

Countries | Cities | Organizations

View all →

→ Top contributors

#	User	Contrib.
1	cry	167
2	maomao90	163
2	Um_nik	163
4	atcoder_official	161
5	adamant	159
6	-is-this-fft-	158
7	awoo	157
8	TheScrasse	154
9	nor	153
9	Dominater069	153

View all →

→ Find user

→ Recent actions

Detailed →

rsazid99's blog

Help in a DP problem

By rsazid99, history, 7 years ago, In English

Jimmy writes down the decimal representations of all natural numbers between and including m and n, (m ≤ n). How many zeroes will he write down?

Input Input starts with an integer T (≤ 11000), denoting the number of test cases.

Each case contains two unsigned 32-bit integers m and n, (m ≤ n).

Output For each case, print the case number and the number of zeroes written down by Jimmy.

Sample Input Output for Sample Input

10 11

100 200

0 500

1234567890 2345678901

0 4294967295

Case 1: 1

Case 2: 22

Case 3: 92

Case 4: 987654304

Case 5: 3825876150

what will be the dp states ? as i used the concept of Digit dp , so my states are dp[my current position][my last number][is the number started][is my current digit equal to my target digit] but i am getting correct output for 1st 3 cases, is there anything i am missing ?

rsazid99
7 years ago
7

Comments (5)

Show archived | Write comment?

TooNewbie

7 years ago, # |

← Rev. 3 →

This algorithm should work, correct me if there are any mistakes. I will solve for 1 to n, you know how to fit this to your problem:

If number is ending with 9, then you can divide numbers from 0 to N (here you have to add additional case for 0 i.e. if m=0, then add 1 to answer) to 10 equal parts such that numbers in i'th part ends with digit i. Let solve(n) mean count of zeros from 1 to n. Then for each part there are solve(n/10) zeros besides part with 0 digit, though there are solve(n/10)+(n/10). (because of trailing 0's)

Otherwise, it is simple, answer is (count of zeros in n) + solve(n-1). This algorithm works in O(logN) with small constant.

Here is little C++ code:

intt solve (intt x) {
    if (x < 10) {
        return 0;
    }
    if (x % 10 == 9) {
        return 10 * solve (x / 10) + (x / 10);
    } else {
        return solve (x - 1) + c0 (x);
    }
}

→ Reply

rsazid99

7 years ago, # ^ |

can you please elaborate the line "Then for each part there are solve(n/10) zeros besides part with 0 digit, though there are solve(n/10)+(n/10). (because of trailing 0's)" , i didn't understand it

→ Reply

TooNewbie

7 years ago, # ^ |

If number is not ending by 0, then obviously answer for that is solve(n/10) (because last digit doesn't matters)

If number is ending by 0, then answer is that is solve(n/10) + (n/10), because there are n/10 numbers with ending 0 additionally.

→ Reply

rsazid99

7 years ago, # ^ |

if you don't mind, you can submit your code in this link http://www.lightoj.com/volume_showproblem.php?problem=1140

→ Reply

TooNewbie

7 years ago, # ^ |

Got AC.

Full code

/*
ID: usaco.t3
TASK: test
LANG: C++14
*/

#pragma GCC optimize ("O3")
/****Author: Barish Namazov****/
#include <bits/stdc++.h>

using namespace std;

/***TEMPLATE***/
#define intt long long

#define pii pair<intt,intt>
#define vi vector<intt>
#define vii vector<pii>

#define all(v) (v).begin(),(v).end()
#define rall(v) (v).rbegin(),(v).rend()

#define F first
#define S second
#define pb push_back

#define IO ios_base::sync_with_stdio(false);cin.tie();
#define endl '\n'

#define wtfis(x) cerr << "at line " << __LINE__ << ": " << #x << " = " << (x) << endl

const intt max3 = 1003;
const intt max4 = 10004;
const intt maxx = 100005;
const intt max6 = 1000006;
const intt max7 = 10000007;

const intt lg4 = 13;
const intt lg5 = 17;
const intt lg6 = 20;

const intt INF = 2LL * 1000000000;
const intt INFLL = 9LL * 1000000000 * 1000000000;
/***************/

intt powmod (intt a, intt b, intt mod) {
    intt res = 1;
    a %= mod;
    for (; b; b >>= 1) {
        if (b & 1)
            res = (res * a) % mod;
        a = (a * a) % mod;
    }
    return res;
}

intt gcd (intt a, intt b) {
    while (b > 0) {
        intt t = a % b;
        a = b, b = t;
    }
    return a;
}

intt lcm (intt a, intt b) {
    return (a / gcd (a, b)) * b;
}

intt is_prime (intt n) {
    if (n <= 1 || n > 3 && (n % 2 == 0 || n % 3 == 0))
        return 0;
    for (intt i = 5, t = 2; i * i <= n; i += t, t = 6 - t)
        if (n % i == 0)
            return 0;
    return 1;
}

/**************************/

intt c0 (intt x) {
    intt res = 0;
    while (x > 0) {
        res += (x % 10 == 0);
        x /= 10;
    }
    return res;
}

intt solve (intt x) {
    if (x < 10) {
        return 0;
    }
    if (x % 10 == 9) {
        return 10 * solve (x / 10) + (x / 10);
    } else {
        return solve (x - 1) + c0 (x);
    }
}

int main() {
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    IO;
    intt T;
    cin >> T;
    for (intt cs = 1; cs <= T; cs++) {
        intt a, b;
        cin >> a >> b;
        intt res = solve (b) - solve (a - 1);
        if (a == 0) {
            res++;
        }
        cout << "Case " << cs << ": " << res << endl;
    }
    return 0;
}

→ Reply