LSTBTF - Editorial

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest

Author: Bohdan Pastuschak
Tester: Yash Chandnani
Editorialist: Michael Nematollahi

DIFFICULTY:

Medium

PREREQUISITES:

DP

PROBLEM:

Given a positive integer N, you need to find the smallest beautiful N-digit number.

A number is said to be beautiful iff

  • It’s decimal representation has no 0's other than the leading ones.
  • The sum of the squares of all decimal digits of it is a perfect square.

QUICK EXPLANATION:

Since the order of digits does not affect the sum of squares of the digits, the digits of the optimal answer will be in non-decreasing order.
To make the number minimal, we want it to have as many 1's as possible, then as many 2's as possible and so on.
Guess and prove by inspection that the number of the digits greater than 1 in the optimal answer will not be big. Then, first try and see if there is an answer with N digits equal to 1. If there’s no answer, try N-1 and so on. Repeat this step for the digits 2 to 9 after.
To see if there’s an answer with a fixed number of 1's, use can[first][reqDigits][sum] which is true iff you can construct a number with reqDigit digits such that all of them are at least equal to first and the sum of their squares is equal to sum.

EXPLANATION:

Let sm(x) denote the sum of squares of the decimal digits of the number x.
Note that sm(x) does not depend on the order of the digits of x; so if we arrange the digits of x in any way, the sm of the resulting number will not change. This implies that for a beautiful number to be minimum, its digits have to be in non-decreasing order. We call this property “the moon property”.

Let x and y be two numbers with N digits that have the moon property. Because they’re of the same length, x is less than y if its decimal digit representation is lexicographically less than that of y. This means that since we’re looking for the smallest beautiful number, we want it to have as many 1's as possible, then as many 2's as possible and so on.

Let can[firstDigit][cntDigits][sumSquares] be a boolean dp array that is true iff you can construct a number with cntDigit digits whose smallest digit is at least firstDigit and whose sum of squares is equal to sumSquares. To give you some intuition, we’re interested in can[1][N][sum] where sum is a perfect square.

By inspection, we can see that there always exists a beautiful number of N digits for the given constraints, and that the maximum number of “non-one” digits in the smallest beautiful number of length N is 27.

Using the statements above, we can conclude that the required bounds for the can array are:

  • 2 \le firstDigit < 10
    The reason for the left-hand bound is that we iterate over the number of 1's manually.
  • 0 \le cntDigits \le 27
  • 0 \le sumSquares \le 27 * 9^2

Now that we have these constraints, we can compute the can array in O(F \times C^2 \times S), where F is the maximum value of firstDigit, C is the maximum value of cntDigits and S is the maximum value of sumSquares.
To see the transitions of the dp array, refer to the editorialist’s code.

Now that we have can, for each test case we start with setting the number of 1's equal to N and see if there is a beautiful number that has N 1's. If we fail, we decrease this number by 1 and try again.

To see if there’s a beautiful number of length N that has k 1's, we iterate over all possible perfect squares s and see if can[2][N-k][s-k \times 1^2] holds.

We can use the same idea repetitively to find the number of 2's, 3's and so on in the optimal answer.

The complexity of this part of the solution will be O(D \times C \times SQ + N), where D is the number of possible digits 10, C is the maximum number of “non-one” digits 27 (because that’s how many iterations the “while (true)” part in the code can take) and SQ is the number of perfect squares of interest sqrt(N \times 9^2).

To see an implementation of this solution for better understanding, refer to the editorialist’s code.

SOLUTIONS:

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
 
typedef long long LL;
typedef pair<int, int> PII;
typedef vector<int> VI;
typedef vector<double> VD;
#define MP make_pair
#define PB push_back
#define X first
#define Y second
 
#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define RFOR(i, b, a) for(int i = (b) - 1; i >= (a); --i)
#define ITER(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define ALL(a) a.begin(), a.end()
#define SZ(a) (int)((a).size())
#define FILL(a, value) memset(a, value, sizeof(a))
#define debug(a) cout << #a << " = " << a << endl;
 
const double PI = acos(-1.0);
const LL INF = 1e9 + 47;
const LL LINF = INF * INF;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
inline bool isSquare(int s)
{
	int t = sqrt(s);
	return t * t == s;
}
 
int n;
char dp[10][30][81 * 30];
int cnt1;
 
inline int f(int curr, int cnt, int sum)
{
	if (curr == 10)
		return cnt == 0 && isSquare(sum + cnt1);
		
	if (dp[curr][cnt][sum] != -1)
		return dp[curr][cnt][sum];
	
	int res = 0;
	FOR(i, 0, cnt + 1)
		res |= f(curr + 1, cnt - i, sum + i * curr * curr);
		
	return dp[curr][cnt][sum] = res;
}
 
int main()
{
	ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	//freopen("In.txt", "r", stdin);
	//freopen("In.txt", "w", stdout);
	
	int t;
	cin >> t;
	while(t--)
	{
		cin >> n;
 
		int cnt = -1;
		for(cnt1 = n; cnt1 >= 0; cnt1--)
		{
			FILL(dp, -1);
			cnt = n - cnt1;
			if (f(2, cnt, 0))
				break;
		}
		
		string s(cnt1, '1');
		assert(cnt != -1);
		int sum = 0;
		FOR(d, 2, 10)
		{
			bool fnd = 0;
			RFOR(i, cnt + 1, 0)
			{
				if (f(d + 1, cnt - i, sum + i * d * d))
				{
					sum += i * d * d;
					cnt -= i;
					FOR(j, 0, i)
						s.push_back('0' + d);
					
					fnd = 1;
					break;
				}
			}
			
			assert(fnd);
		}
 
		cout << s << endl;
	}
	
	cerr << "Time elapsed: " << clock() / (double)CLOCKS_PER_SEC << endl;
	return 0;
} 
Tester's Solution
#include <bits/stdc++.h>
using namespace std;
 
 
void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ','; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? "," : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifndef ONLINE_JUDGE
#define debug(x...) cerr << "[" << #x << "] = ["; _print(x)
#else
#define debug(x...)
#endif
 
#define rep(i, n)    for(int i = 0; i < (n); ++i)
#define repA(i, a, n)  for(int i = a; i <= (n); ++i)
#define repD(i, a, n)  for(int i = a; i >= (n); --i)
#define trav(a, x) for(auto& a : x)
#define all(x) x.begin(), x.end()
#define sz(x) (int)(x).size()
#define fill(a)  memset(a, 0, sizeof (a))
#define fst first
#define snd second
#define mp make_pair
#define pb push_back
typedef long double ld;
typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;
bitset<2500> b[30];
void pre(){
	b[0][0]=1;
	repA(i,1,28){
		repA(j,1,9){
			b[i]|=b[i-1]<<(j*j);
		}
	}
 
}
int sum = 0;
char t;
bool square(int x){
	int y = sqrt(x);
	return (y*y==x)||((y+1)*(y+1)==x)||((y-1)*(y-1)==x);
}
void solve(){
	int n;
	scanf("%d%c",&n,&t);
	assert(t=='\n');
	assert(n>=1&&n<=1000000);
	sum+=n;
	assert(sum<=1000000);
	int nn=min(n,28);
	int s = n-nn;
	string ans = string(s,'1');
	repD(i,nn,1){
		bool fg=0;
		repA(j,1,9){
			s+=j*j;
			rep(k,2500) if(b[i-1][k]&&square(s+k)) {
				ans+='0'+j;
				fg=1;
				break;
			}
			if(fg) break;
			s-=j*j;
		}
		if(!fg) {
			cout<<-1<<'\n';
			return;
		}
	}
	cout<<ans<<'\n';
}
 
int main() {
	cin.sync_with_stdio(0); cin.tie(0);
	cin.exceptions(cin.failbit);
	pre();
	int n;
	scanf("%d%c",&n,&t);
	assert(t=='\n');
	assert(n>=1&&n<=100);
	rep(i,n) solve();
	return 0;
}
Editorialist's Solution
#include<bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
 
#define F first
#define S second
 
const int XX = 29;
 
bool can[11][XX][XX * 81];
set<int> squares;
 
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	for (int i = 0; i*i <= (int)1e8; i++) squares.insert(i*i);
	can[10][0][0] = true;
	for (int sm = 0; sm < XX * 81; sm++)
		for (int first = 9; first > 0; first--)
			for (int cnt = 0; cnt < XX; cnt++)
				if (cnt == 0)
					can[first][cnt][sm] = (sm == 0);
				else{
					can[first][cnt][sm] |= can[first+1][cnt][sm];
					for (int t = 1; t <= cnt && t * first*first <= sm; t++)
						can[first][cnt][sm] |= 
							can[first+1][cnt-t][sm - t*first*first];
				}
 
	int te;	cin >> te;
	while (te--){
		int n; cin >> n;
		int rem = n, curSm = 0;
		for (int i = 1; rem && i <= 9; i++) {
			int cnt = rem;
			while (true){
				bool success = false;
				for (auto x: squares) {
					int tempSum = curSm + cnt*i*i;
					success |= tempSum <= x && 
						x-tempSum < XX*81 && can[i+1][rem-cnt][x-tempSum];
				}
				if (success)
					break;
				cnt--;
			}
 
			rem -= cnt;
			curSm += cnt*i*i;
			while (cnt--)
				cout << i;
		}
		cout << "\n";
	}
	return 0;
}
4 Likes

Solution using backtracking:
https://www.codechef.com/viewsolution/27732112

For every position i am placing a number (say x) and asking the function (canplace()) if it’s the correct number. If it is, return 1.

If it’s not we backtrack and place the next number (x+1) (hence the for loop) and do the same again.

“prev” is necessary so that we always have a non decreasing sequence.

eg:
for 5
1 1 1 1 1 ,
1 1 1 1 2 ,

1 1 1 1 9,
1 1 1 2 2,
1 1 1 2 3, …
and so on.

Hope you got the basic idea.

24 Likes

Your solution was simple to understand. I implemented a recursive version based on your solution :slight_smile:

https://www.codechef.com/viewsolution/27873717

5 Likes

@hetp111, thanks for the solution.

I tried to implement your solution in python. But, am getting TLE for two cases. Could you please help me where am doing wrong?

https://www.codechef.com/viewsolution/27872134

1 Like

Nice , Het Patel !

1 Like

@snehith26 try submitting same code in PyPy 3.5…Even I was getting TLE for those two test cases in python…I submitted in PyPy and got AC
https://www.codechef.com/viewsolution/27857898
https://www.codechef.com/viewsolution/27857836

1 Like

@watcher how to prove that this system is always consistent ? (i.e, not a " −1 ")
well best thing to ask is … how did you realize that ?

3 Likes

@the_pythor thanks! But when i submit the same code in pypy3, it am getting SEGV for all the tests in subtask2. Do i need to make any changes for submitting in pypy3.

Please note that to allow recursion depth more than 1000, i used sys.setrecursionlimit. Would be very helpful if you help me to overcome this!

LMAO I didn’t know dp but solved it in the most ridiculous way possible. I legit used 8 nested for loops, yes EIGHT. Did hell lotta optimisations and this is what i ended up with. And it takes just 0.08s max.
https://www.codechef.com/viewsolution/27823461

5 Likes

Noone will prolly understand what i did but i just wanted to put out the shit i went through to get to the solution xD

3 Likes

LMAO ME TOO

@hetp111 too simple solution , really very easy to understand

1 Like

This is the very good extended version of problem project Euler 171
https://projecteuler.net/problem=171

You can try to find the answer for each N from 1 to 10^6. The fact that you’re only interested in the number of ones makes it quicker to answer (but it will still take some time for the program to finish).

My approach was rather different. It is more complicated, but fast for large N in that the time of solution does not increase with N.

First note that a typical solution may be divided into 3 parts: (1) leading 1s, (2) some digits 2 to 8 non-descending order, (3) trailing 9s. Not all of these parts are present in all solutions.

Start by considering all 1s. Evaluate the extra required K to bring it up to the next perfect square. If the extra required exceeds some number M, add enough 9s to the end of the solution to bring K down below M. For each 9 added, K is reduced by 80 = 9^2 – 1^2, so the required number of 9s is the result of a direct calculation.

Look up in a pre-calculated array what the solution is for this K, if any. Then try the next perfect square, in case this leads to a smaller solution overall. Continue trying each perfect square in turn until we are sure that no solution better than the present one can be found.

The question then remains as to how large the pre-calculated array needs to be. By experiment I found that the largest value of K such that

Solution[k] < Solution[k-80] is 252. It is therefore sufficient to set M = 320 (next multiple of 80), as there is no benefit in having a larger number. Further experimentation shows that the maximum number of digits 2 to 8 in any solution is only 6, so it is sufficient for the array to contain numbers with 10 digits, that is 6 as found here plus up to 3 trailing 9s plus 1 to allow comparison of solutions with different number of trailing 9s. The only values of K for which there is no solution are less than 14, so a solution can always be found by going to a larger number. Evaluating this array is the slowest part of the whole algorithm, taking about 0.01 seconds, but it only needs to be done once. It might be possible to reduce the number of digits stored and M, but I am not sure.

All possible solutions are stored as arrays of decimal digits, making it easy to work with digits.

The algorithm described here could happily cope with 100 or maybe even 1000 test cases within the time limit, although it might take too long to print all the digits. Printing the last 50 or so digits would be enough to identify whether a solution is correct, as all earlier digits are 1s.

You can see my solution at https://www.codechef.com/viewsolution/27724733

4 Likes

Problem can be easily solved using the solution to standard COIN CHANGE PROBLEM.
Suppose you are given a number N.
Now consider a base answer that is a string of size N only containing 1.
So there are two cases:
Case 1: N is a perfect square. You can print the base answer directly.
Case 2:N is not a perfect square.
Now let’s solve Case 2, as N is not a perfect square , we’ll have to replace some 1s in the base answer with other digits from 2 to 9, and this will obviously result in increment of our base answer’s value. So now there are only 8 kinds of possible changes to the sum you can make and they are 3,8,15,24,35,48,63 and 80 i.e. if you replace a 1 with 2 then net change is of 2^2 - 1 = 3. So let’s think these 8 changes are the 8 kind of coins we have and we can use any coin more than once to create the required sum, which is same as the problem statement of COIN CHANGE PROBLEM.

I’m not delving into the solution of coin change problem, you can find it anywhere, but now the only remaining question is that how do we know what the required sum is. So you must keep in mind that minimum square for any N will be N itself (where every digit will be 1) and obviously maximum answer will be 81*N (where every digit will be 9). So we have to start from our base answer find the next perfect square then find if we can make the change using given coins, if not process next perfect square, if yes then see if the solution is lexicographically smallest answer we have found yet.
As one common mistake someone might make at this juncture is minimizing the square sum, which is not required. We have to just find the smallest beautiful number not the number with smallest square sum. For example answer for N = 18 is 111111111111111118 but it’s square sum is 81 and 111111111111111124 has square sum 36, so answer should be 111111111111111118 even if the square sum is greater.
My Solution

12 Likes

@s5960r , what is sid and momo in your code?
is it helpful or you have written it just for fun?
please tell me.

That’s nickname of me and my partner :stuck_out_tongue:

I solve this question using bfs.
which is very faster and easy to understand :grinning:

obs1: maximum count of digit 2 - 9 in final are 25
obs2: maximum count of digit 2 -8 in final are 5

so, used bfs algorithm,check possiblity for 5 digit numbe
time =O(5^7), which is very faster :sweat_smile:
my solution link:
https://www.codechef.com/viewsolution/27747020

you can use dfs also.

7 Likes

Is there any way to implement the same approach in Python? Python doesn’t allow this much depth for recursion. Can anyone suggest me any trick to do this?