ADDNDIV - Editorial

editorial
, , ,
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
32

Therefore, I Created this Post.

@admin, Please Do Take Up Feature of 12 Hr Hacking [Similar to CodeForces], That Would Really Improve the Test Cases, in case Tester has Missed it Out.

2 Likes
33

I am sorry earlier I tried this overflow trick but it gave Wrong answer.
Now I tried the same but using long long and it gave Runtime Error.
Thanks.
But I tried this problem using u128int (just to see what will happen) and used that same overflow trick, but that code gave me Wrong Answer, instead of Runtime Error.Link
Any reason why it didn’t gave Runtime Error?

1 Like
34

Glaring issue in this one - if you indented your code properly, you’d probably spot it straight away :slight_smile:

1                                                       
6 2
3 Likes
35

Maybe the flag simply doesn’t work with u128int :frowning:

2 Likes