### oversayan's blog

By oversayan, history, 6 weeks ago,

Hello, I'm a beginner in competitive programming.

I really enjoyed the 1520B problem called Ordinary Numbers : https://codeforces.com/problemset/problem/1520/B

I observed that @MikeMirzayanov's tutorial uses a brute-force method to solve this : https://codeforces.com/blog/entry/90342

However, it is possible, to solve the problem without using bruteforce, at all.

Here's my solution which has been accepted by the virtual judge : https://codeforces.com/contest/1520/submission/119706686

I hope it's useful to you all. After all, we'll all learn together.

Thank you :)

// URL  : https://codeforces.com/problemset/problem/1520/B
// NOTE : Really good problem. Loved the logic behind it. AMAZING PROBLEM!!!
//

#include <iostream>
#include <algorithm>
#include <cmath>

#pragma GCC optimize("O3")

#define sl long long
#define nl "\n";

using namespace std;

sl memo[100];

int main()
{
ios_base::sync_with_stdio(false);
cin.tie(nullptr);

sl t;
cin >> t;

// create a memoization table using which we can create unique numbers
// just from the first digits of some number we're currently analyzing
//
memo[0]  = 0;
memo[1]  = 1;
memo[2]  = 11;
memo[3]  = 111;
memo[4]  = 1111;
memo[5]  = 11111;
memo[6]  = 111111;
memo[7]  = 1111111;
memo[8]  = 11111111;
memo[9]  = 111111111;
memo[10] = 1111111111;
memo[11] = 11111111111;
memo[12] = 111111111111;
memo[13] = 1111111111111;

// for [0] = 0 unique numbers as range is 1<=n<=10^9
// for [1:10] = 9 unique numbers for 1 digit numbers
// for [10:100] = 9 unique numbers for 2 digit numbers
// for [100:1000] = 9 unique numbers for 3 digit numbers
// for [1000:10,000] = 9 unique numbers for 4 digit numbers
//
while(t--)
{
sl n;
cin >> n;

// number of digits in the number
sl ndigits = floor(log10(n)+1);

// maximum possible unique numbers for a digit of length ndigits
sl maxunos = ndigits * 9;

// get the first digit of n
sl fdigit = n/pow(10, ndigits-1);

// get the unique number that starts with fdgit and ends with fdigit
// and contains ndigits digits : 12345 -> 11111 ; 41234 -> 4444
//
sl m =  memo[ndigits]*fdigit;

// incase the given n is not a unique number, we need to analyze
// what's the correct number of unique numbers present in the given
// range. we need to do this, since maxunos needs to be corrected.
//
sl neg = 0;

if(n<m)
{
neg = 9-fdigit+1;
}
else
if(n>=m)
{
neg = 9-fdigit;
}

sl ans = maxunos - neg;

cout << ans << nl;
}

cout << flush;
return 0;
}


• +8

 » 6 weeks ago, # |   +4 i wont call it easier solution .. but this is definitely a unique approach ... Great :)
 » 6 weeks ago, # |   0 During that contest I implemented a somewhat similar solution 115250768 in Ruby programming language. But it doesn't have memoization, because time complexity is $O(\log n)$ even without memoization and this is good enough. The "brute force" solution from the editorial is also effectively $O(\log n)$.Here's a conversion of the same solution to C++: 119738023. Arbitrarily large values of $n$ are supported as long as the answer fits in int. Memoization can be easily added too for making it $O(1)$.
•  » » 6 weeks ago, # ^ |   0 The solutions you provided are interesting.
•  » » » 6 weeks ago, # ^ |   0 It's very similar to yours, because many parts of it are the same (replicating the first digit, etc.). But I'm actually wrong about the time complexity when dealing with arbitrarily large $n$. Because comparing strings is not $O(1)$, unlike comparing numbers stored in 32-bit or 64-bit variables.
 » 6 weeks ago, # |   0 I generated all the numbers that we should find lol. My attempt: 115229597