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