Блог пользователя ronak037

Автор ronak037, история, 4 года назад, По-английски

Hello guys, I hope you are doing well in this quarantine period. I want to share some small things from which my some question got WA instead of Accepted which needs to be taken care of while coding and I note down those points and also want to share with you. Maybe you already know them and maybe, for someone these are helpful.

  1. When we use pow function then it may give the wrong answer when we are using it for big values so instead, always add some changes while using it like instead of using directly, add 0.5 to it given value and then typecast into it int or long long as per the requirement. Example avoid writing pow(2,20), instead write (long long)(pow(2,20)+0.5). This will surely give the correct result.

[Edit]: please avoid using pow function as discussed in comments. Instead, use the divide and conquer method:

long long power(long long a,long long b)
{
    if(b==0) return 1;
    long long p = power(a, b/2);
    if(b&1) return p*p*a;
    else return p*p;
}
  1. Don't use sqrt function in a loop for comparison like this for(int i = 0; i <= sqrt(n); i++){} but precalculate the value of sqrt(n) and store it in different variable then use it in for loop. This is because if you don't precalculate the value then it may give TLE because every time loop will execute then every time it calculates sqrt(n).

  2. When we use v.size() for vector so this gives runtime error once in my solution because maybe I subtract some bigger value from its returned value which I didn't able to know during the contest then someone told me that .size() return unsigned long long value due to which this happens so from onwards I always start to typecast it into long long also such that that type of error will not come again. This is that solution: link

  3. Always typecast first value into a long double then use it in log function because otherwise, it may give the wrong answer due to some precision error in big values. Use log like this log((log double)z).

[Edit]: Instead of typecase you can also directly use logl function which automatically typecast and help to find the desired output.

These are some things that I learned during this quarantine period and this seems very small mistakes but very difficult to debug.

Thanks to all and also welcome other tips and suggestions. And please correct me if I am wrong somewhere.

  • Проголосовать: нравится
  • +26
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +15 Проголосовать: не нравится

I really though this was going to be a life lesson or something... :)

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +2 Проголосовать: не нравится

    lol...no, these are things only because of which sometimes I almost solved the question but not able to complete it and my rank goes down very much so I thought this will help others.

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Very important suggestions.

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +10 Проголосовать: не нравится
  • Avoid using $$$pow$$$. Calculate power with divide-and-conquer, main idea is $$$a^b=a^{b/2}*a^{b/2}$$$
Code
  • Try using $$$i*i <= n$$$, if $$$n$$$ is not static
»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

for(int i=1; i<=sqrt(n); i++) you can also write as for(int i=1; i*i<=n; i++) and also many times the value of n changes during the loop so precalculation won't work.

»
4 года назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Your pow solution doesn't work always. e.g.:

cout << ll(pow(LLONG_MAX, 1)+0.5) << ' ' << LLONG_MAX << '\n';

Output: -9223372036854775808 9223372036854775807

»
4 года назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится
  1. (long long)(pow(3, 39) + 0.5) gives 4052555153018976256 on my computer, which is an even number. In fact, $$$3^{39} = 4052555153018976267$$$. Don't use pow for exact computations.

  2. One can also write for (int i = 0; i * i <= n; ++i) or for (long long i = 0; i * i <= n; ++i) if n is large. I'm not sure that sqrt(n) can always handle a sufficient precision.

  3. In your solution factor.size() - 1 can be ULLONG_MAX if factor is empty. If you want to handle this separately, you can also handle the case when factor is of size 1 as well. One can instead write (int)factor.size() - 2 or create a define #define sz(x) (int)(x).size().

  4. There is indeed a log function of signature long double log(long double), but instead of casting an argument to long double one can use the function logl. By the way, adding a letter l to many other double functions make them work with long doubles as well (for example, powl, sinl etc).

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

You can also do

ll pow(ll a, ll b) {
    ll res = 1;
    while(b > 0) {
        if(b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

Where MOD is some number.