ADDNDIV - Editorial

editorial
, , ,
12

Ohh, thanks a lot then.

13

I agree coding the naive solution is useful for testing. But would you submit the code if the if there was penalties on wrong answers (like Cook-offs)? Isn’t the point of the constraints of the questions meant to think outside the box and not just the most straight forward solution that exists? Even though this solution just works, it is not exactly the intended solution ( the editorialist clearly mentions this). It is also possible that I don’t waste precious time on coding a solution which I know for a fact is too slow, just to get a verdict which is TLE.
I’m not asking to re-judge all solutions, I understand that is unfair. But shouldn’t we have strong test cases to start with. In the editorial it also mentioned that this approach will time out, so should it not time out?

Most of the solutions submitted TLE on T = 100000, a = 982451653 and b = 982451653 (This is valid as per the constriants).

2 Likes
14

Absolutely agree with Kabra Neel. I made ~5-6 submissions, of which the later 2 were naive, but, nevertheless correct solutions and got TLE’ed. I thought of implementing O(n) sieve of eratosthenes (the exact same solution which passed for others) but then decided against it as I thought it would be futile.

Also, this seems to be trend for a lot of problems these days. If you cannot make proper testcases, why make the constraints tighter? Astoundingly thoughtless.

1 Like
15

Wow, this is a really clever solution!!!

Although it is glaringly obvious now that I’ve read your solution, I kept racking my brain, but, it didn’t occur to me that after all the primes up to sqrt(10e9) have been divided from ‘a’, there can only be at most one factor left which has to be a prime in itself.

1 Like
16

I think that your mistake was not realizing how close you were to getting accepted. Did you benchmark your code on your computer with a large random testcase?

1 Like
17

You can also use this for checking for overflow.

3 Likes
18

No, I did not.

While I do know how to use timers to find running time of a program, is there any established/preferred way of doing this for CP?
Also, a few more questions along similar lines, if you may please answer:

  1. Is there any guide/template/references which covers these and other such things (as before you pointed, I never thought of doing this in a live round of CP and I usually just try to compute complexity by hand).

  2. Also, how to proceed about it (if there’s any generic way at all or, rather a checklist) once you figure the time complexity is hovering around the allowed limit.

19

Thanks! Was informative and would be a nice addition to anybody’s repertoire of debugging.

1 Like
20

In complexity analysis of the editorial:

The number of prime factors in the factorisation of a is \le \log a

I can’t seem to reason why. Can somebody please explain why?

21

Say any number N is made of K primes so we can say that

N=p_1^{\alpha_1} \times p_2^{\alpha_2} \dots p_K^{\alpha_K} \\

since \alpha_i \ge 1 \ \forall \ 1 \le i \le K

N \ge p_1\times p_2\times p_3 \dots p_K

Also any prime p_i \ge2

\implies N \ge 2^K \\ \boxed{\therefore \log N \ge K}
4 Likes
22

I don’t know what is happening.
Same solution gave TLE in contest (TLE solution) and now giving accepted (Accepted)

You can check. The code is exact same.

I was trying to upsolve by looking at others solution and found that some of them got accepted with the similar solution -

For example - accepted 1
accepted2

Can anyone give me any reason for that??

@infinitepro

Funny Edit : Same solution is giving TLE in 2 test cases now - HAHAHAHA

23

could you pls tell me, why i’m getting WA, I checked for every prime factor!!

https://www.codechef.com/viewsolution/51723447

24

Can anyone help me with my submission ?? Submission
What I tried to do is that I just go over all the powers of b such that b is less than 1e17 and checked everytime, whether a is perfectly dividing b or not.
Maybe it’s wrong because of Overflow, but I tried this and it didn’t gave me Runtime Error.
Thank You.

25

I have tried O(sqrt(a)) giving TLE
for 1sec sqrt(10^9) shouldnt give TLE right?

#include<bits/stdc++.h>
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int a,b;
cin>>a>>b;
int x = 2;
bool f = true;
while(x<=sqrt(a))
{
if(a%x == 0)
{
a=a/x;
if(b%x !=0 )
{
f=false;
break;
}
}
else x++;
}
if(a>2 && b%a !=0) f = false;
if(!f) cout<<“NO\n”;
else cout<<“YES\n”;
}
return 0;
}

26

this is also i have tried many times
but in this solution i dont think anything is wrong
https://www.codechef.com/viewsolution/51680500
this is my solution

27

Thanks , can you please provide some test case where my code fails. My approach is , i calculate all the prime factors of a and checking them against b , if b % prime_fact != 0 for any prime factor , the ans will be NO else YES.

28 
void solve()
{

    int a,b;
    scc(a)
    scc(b)

    bool ok = 0;
    for(int i=0;i<=50;i++)
    {
        if(bigmod(b,i,a) == 0) ok = 1;
    }
    if(ok)puts("YES");
    else puts("NO");

}

Is this the correct solution?
It got ac.

29

Interesting: it’s trivial to make this overflow: Add and Divide - Can some tell where it fails? - #2 by ssjgz

Can you link to your submission that uses the “check for overflow” trick?

2 Likes
30

i think i understood what is wrong with our approach
suppose we have b=1e9 and their exist an a for which b raised to power 4 or 5 is divisible
then b power 5 will overflow even unsinged long long int
so that’s that our approach dosen’t work for larger numbers

31

Yes, the logic is correct.

Given constraints, a \leq 10^9 so the highest power of any prime in a can be \log _2 a \leq 30. So you just need to check till maximum b^{30} if a ~ | ~ b.

Although you implementation is very repetitive, it works.

1 Like