Problem DGTMAGIC - QFUN2020: incorrect author's solution

,

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

#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