Editorial - SPLINT

PROBLEM LINK:

Practice
Contest

Author: John Zakkam
Tester: Saurabh Singh
Editorialist: John Zakkam

DIFFICULTY:

MEDIUM

PREREQUISITES:

Math, Observations.

PROBLEM:

An integer x is called special if for every positive integer y such that y \gt x, \frac{x}{f(x)} \le \frac{y}{f(y)} holds.
Where f(d) is a function which denotes the sum of digits in the decimal representation of d.
Now, we have are given a range [A, B] and we have to find (B - A + 1) special numbers, specifically meaning to find the sequence of special numbers starting from the A^{th} special number to the B^{th} special number.

EXPLANATION:

Let g(N) be the integer n \ge N that minimises the value of f(x) i.e; \frac{x}{f(x)}. So we start with N = 1 and by repeating N \leftarrow f(N + 1), we can list all special numbers in increasing order. Now we’ll have to just find g(N) for a given range [A, B].

One thing we could do is just find all the special numbers from [1, B] and print [A, B] special numbers.
Now, we’ll make an interesting observation which is that, g(N) can be obtained always by changing the least important k digits of N to 9 for some k. Let x = g(N), let x_i denote the i^{th} digit of the number x. Assume that x > N and the d^{th} digit is the most significant digit (the first) where x and N differ (note that x and N always have the same number of digits), we have to prove that x_0 = \dots = x_d = 9 i.e; 99999...999 is always a special number.

As a fun task you can try to prove this.

If you're too lazy, here's the proof

Suppose for some i < d, x_i < 9. Let y be the integer obtained by changing x_i to 9 and x_d to x_{d - 1}. Clearly, N \le y \le x and f(y) \ge f(x) holds. Now this contradicts the minimality of \frac{x}{f(x}. Hence, x_0 = \dots = x_d = 9.

We know that x_0 = \dots = x_d = 9, x_d is unknown and x_{d+1} \dots are the same as corresponding digits of N. Let z be the value of x in case x_d = 0, and let w = x_d. Then, we getc x=z+w *10^d, f(x) = f(z) + w , and \frac{x}{f(x)} = \frac{z+w*10^d}{f(z) + w}. Since this is a monotonous function of w, the optimal value of w is either the smallest valid value (the d^{th} digit of N ) or the largest valid value (9). We know that d^{th} digit is the digit where x and N differ, thus, x_d= 9. Now we have to find out (B-A+1) values for x. For each value in the range compute the value of \frac{x}{f(x)}, and g(N) is the one that minimizes this value.

meme for the problem

SOLUTIONS:

Setter's Solution
#pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
#define endl '\n'
typedef long long int ll;

const ll maxn = 1e5 + 7;
const ll mod = 1e9 + 7;

ll sum_dig(ll x) {
	ll res = 0;
	while(x > 0) res += (x % 10), x /= 10;
	return res;
}

void solve() {
	ll x, a, b;
	cin >> a >> b;
	x = b;
	vector<ll> ans;
    ll y = 1, z = 1;
    for (ll i = 0; i < x; ++i) {
        if (y * sum_dig(y + z) <= (y + z) * sum_dig(y)) {
            ans.push_back(y);
            if ((y + z) * sum_dig(y + z + z) > (y + z + z) * sum_dig(y + z)) z *= 10;
            y += z;
        }
    }
	for(int i = a - 1; i < b; i++) cout << ans[i] << endl;
	return;
}

int main() {
	ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
	ll t = 1;
	// cin >> t;
	while (t--) solve();
	return 0;
}

I liked how one guy coded the solution here have a look at the solution lol.


PS: I tried to explain it as properly as I could. Please let me know if there are any mistakes or if something is unclear or any other approaches. I hope people enjoyed Peas of Code