oversayan's blog

By oversayan, history, 6 weeks ago, In English

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;
		}

		// correct answer
		sl ans = maxunos - neg;

		cout << ans << nl;
	}

	cout << flush;
	return 0;
}
 
 
 
 
  • Vote: I like it
  • +8
  • Vote: I do not like it

»
6 weeks ago, # |
  Vote: I like it +4 Vote: I do not like it

i wont call it easier solution .. but this is definitely a unique approach ... Great :)

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # ^ |
      Vote: I like it 0 Vote: I do not like it

    The solutions you provided are interesting.

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # |
  Vote: I like it 0 Vote: I do not like it

I generated all the numbers that we should find lol. My attempt: 115229597