Problem DGTMAGIC - QFUN2020: incorrect author's solution

,

Problem link: https://www.codechef.com/QFUN2020/problems/DGTMAGIC.

In problem Digits & Magic, we need to calculate, how many digits have number A^B in number system with base i for 2 \le i \le 20.

Obvious solution:

  • If a=0, then all answers are 0;

  • If a>0, then ans_i = \lfloor1+\log_i A^B\rfloor = \lfloor1+B\log_i A\rfloor = \left\lfloor1+B\cdot\dfrac{\ln A}{\ln i}\right\rfloor.

But in the second part, there is precision error: computer can’t store all infinite number of digits, so float numbers can be a bit incorrect. And I’ll prove that all accepted solutions and author’s solution are wrong.

For example, let A=1000, i=10. Then A^B = 1000^B = 10^{3B}. This number in decimal system is “one and 3B zeros”, so it is 3B+1 digits. Really, ans_i = \lfloor1+B\log_i A\rfloor = \lfloor1+B\log_{10}1000\rfloor = \lfloor1+3B\rfloor = 3B+1.

I wrote this solution: https://www.codechef.com/viewsolution/35763447. It uses such approach and gets AC:

if(a==0)
{
    for(int i=2;i<=20;i++)
        cout<<1<<" ";
}
else
{
    for(int i=2;i<=20;i++)
        cout<<int(1+b*(log(a)/log(i)))<<" ";
}

Then I added that for A=1000 and i=10, answer is 3B+1: https://www.codechef.com/viewsolution/35763481. This solution must be AC too, but it gets WA:

if(a==0)
{
    for(int i=2;i<=20;i++)
        cout<<1<<" ";
}
else
{
    for(int i=2;i<=20;i++)
        if(a==1000&&i==10)
            cout<<3*b+1<<" ";
        else
            cout<<int(1+b*(log(a)/log(i)))<<" ";
}

And then I replaced 3B+1 with 3B: https://www.codechef.com/viewsolution/35763490.
This solution must get WA, but it gets AC:

if(a==0)
{
    for(int i=2;i<=20;i++)
        cout<<1<<" ";
}
else
{
    for(int i=2;i<=20;i++)
        if(a==1000&&i==10)
            cout<<3*b<<" ";
        else
            cout<<int(1+b*(log(a)/log(i)))<<" ";
}

If I am not mistaken, all accepted solutions and author’s solution are wrong. Does anyone know correct solution?

UPD. You can run my code with some values of B and see that it outputs 3B. For example: https://ideone.com/Ry3ijc (B=100000).

5 Likes

logl giving correct output for a=1000 ,i=10

But still incorrect for a=2^{25}, b=100000 and i=2. It gives answer 2500000, but correct answer is 2500001. Code: https://ideone.com/hy0ieC.

1 Like

ya exactly !
author need to clear the bug and address it

//code by usernameharsh
#include<bits/stdc++.h>

using namespace std;
#define ll long long int
#define co cout<<
#define ld long double
//scanf("%lld %lld\n",&A,&B);

//driver program
int main()
{
ll T,A,B,n;
scanf("%lld\n",&T);

while(T--)
{
    scanf("%lld %lld\n",&A,&B);
    n=pow(A,B);
    if(A==0)
        for(ll i=2;i<=20;i++)
            co 1<<" ";
    else
        for(ll i=2;i<=20;i++)
	        if(A==1000&&i==10)
                cout<<3*B+1<<" ";
            else
	            cout<<(ll)(1+(B*(log(A)/log(i))))<<" ";
    co "\n";
}

return 0;

}

ya i also tried don’t know why it gives WA
it s totally logical

if i remove if condition as you stated then my solution gets
AC