 # CRDGAME3 - Editorial

Author: Aryan Agarwala
Tester: Данило Мочернюк
Editorialist: Ritesh Gupta

Simple

Number Theory

# PROBLEM:

You are given two numbers A and B. We define the power of a number as the sum of its digits. Let’s suppose X and Y are those numbers for which their power is A and B respectively. If A has more digits than B then print “1 ” and number of digits in A else print “0 “ and number of digits in B.

# QUICK EXPLANATION:

For a number P, we can say that the minimum number of digits used to found the number X whose power is equal P, is equal to:

minimum number of digits required = (P + 8)/9

# EXPLANATION:

We know that there are 10 digits possible i.e. from 0 to 9, As we want to create the number with the use of a minimum number of digits, we should use digit 9 as much possible which means for any power P, if we want to find out the number for which P is the power with a minimum number of digits then all the digits are 9 except 1. If the P is divisible by 9 then all the digits are 9 only.

Now to construct the number, we should use 9 as it is the highest possible digit. Hence we can say that:

• 1 \le sum \le 9 => at least 1 digit
• 10 \le sum \le 18 => at least 2 digit
• 19 \le sum \le 27 => at least 3 digit
• and so on.

Hence by dividing the (final power + 8) from 9, will tell the minimum number of digits that can be needed to form the final power. By this, we can easily answer the question.

TIME: O(1)
SPACE: O(1)

# SOLUTIONS:

Setter's Solution
Tester's Solution
``````#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define x first
#define y second
#define sz(a) ((int)(a.size()))
using namespace std;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1000 * 1000 * 1000;
int main()
{
int T;
cin >> T;
assert(1 <= T && T <= 1000000);
while(T--)
{
int pc, pr;
cin >> pc >> pr;
assert(1 <= pc && pc <= 1000000);
assert(1 <= pr && pr <= 1000000);
int cnt1 = (pc + 8) / 9;
int cnt2 = (pr + 8) / 9;
cout << (cnt2 <= cnt1) << " " << min(cnt1 , cnt2) << endl;
}
}
``````
Editorialist's Solution
``````#include <bits/stdc++.h>

using namespace std;

int main()
{
int t;
cin >> t;

while(t--)
{
int a,b;
cin >> a >> b;

a += 8;
a /= 9;
b += 8;
b /= 9;

cout << (a >= b) << " " << min(a,b) << endl;
}
}
``````

### Video Editorial

2 Likes

If anyone likes VIDEO EDITORIAL YOU CAN CHECK THIS OUT- LINK

1 Like

1. how time complexity is O(LogN)? To me, it looks like O(1).

2. Why we have added 8 in the formula?
I got some idea by looking at
"
1 <= sum <= 9
10 <= sum <= 18
"

In which case we need to add “any other” digit.

1. For “Power Sum”, Rather than allowing 10 digits (0 to 9), what if we have provided fewer digits say [1,2,3,4] Or [1,3,5]. In that case, how will we modify the formula?
1 Like
1. The complexity is O(log10 N) which is equal to the number of digits in N.
2. We want ceil(N/9) which can be easily obtained using (N+8)/9. In fact, any ceil(a/b) can be obtained using (a+b-1)/b.
3. The solution will no longer be a simple greedy solution but a DP solution instead.

@jay_1048576, Thanks a lot!

Can you provide any example regarding to DP solution? It will be helpful.

Hey, a recursive solution could probably be something like:
dp(x) = dp(max(x-9, 0)) + 1
dp(0) = 0

But this is obviously too slow.

I think that you could do this fast by making some large matrix and performing exponentiation, but it would be overkill.

Suppose you are allowed to use only the digits {1,3,4} and the power you want is 6. The most optimal way is 33 but greedy will give you 411.

The dp solution could be something like for every power x the minimum number of digits required can be calculated as
for(i:digits_allowed)
dp[x]=min(dp[x-i]+1,dp[x]);
You can also store the digits required for each x using vectors.

1 Like

Check out Screencast Tutorial for this problem: https://www.youtube.com/watch?v=eNzMABbKOXs&list=PLz-fHCc6WaNIrJbPDdoWUscRqMZPEiqzQ

Please add an official editorial for SUBSFREQ. In all other editorials, they are only telling how to reach to the math formula. I had done that but the terms need to be calculated in efficient manner. I want help with that.

#include <bits/stdc++.h>
using namespace std;

#define loop(i,n) for(int i=0;i<(n);i++)
#define forr(i,a,b) for(int i=(a);i<=(b);i++)
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while(t–!=0)
{
int a,b;
cin >> a >> b;
assert(1 <= a && a <= 1000000);
assert(1 <= b && b <= 1000000);
if(a%9!=0) a = a/9 + 1;
else a = a/9;

``````    if(b%9!=0) b = b/9 + 1;
else b = b/9;

if(b<=a) cout << 1 << " " << b << endl;
else cout << 0 << " " << a << endl;

}
``````

}