CRDGAME3 - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Division 1
Division 2
Video Editorial

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

DIFFICULTY:

Simple

PREREQUISITES:

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.

COMPLEXITY ANALYSIS:

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
2

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

1 Like
3

Can anyone please tell me,

  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
4
  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.
5

@jay_1048576, Thanks a lot!

6

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

7

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.

8

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
9

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

10

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.

11

Why I am getting wrong?? please help

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

}

13

if(c<10 && r<10)
cout << 1 << " " << 1 << endl;
else
{
int ans1=0,ans2=0;
if(c%9==0)
ans1=(c/9);
else
ans1=(c/9)+1;
if(r%9==0)
ans2=(r/9);
else
ans2=(r/9)+1;
if(min(ans1,ans2)==ans1)
cout << 0 << " " << ans1 << endl;
else
cout << 1 << " " << ans2 << endl;
}

// this code got AC

It is for those who are not understanding the editorial.
//Easy