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

Doubt regarding sqrt function in G++ 17 and 23
Автор Dark_Knight_3, история, 2 месяца назад, По-английски

In the recent Codeforces Round 976 (Div. 2) and Divide By Zero 9.0 contest, I submitted my solution for 2020B - Да будет свет! in C++ 23. There, I got the wrong answer on G++ 23, but after the contest, I solved it by changing the language to G++ 17, and it got accepted. So what was the problem? Should I be using G++ 17 or G++ 23? What should be considered when using the built-in sqrt() function? Like precision, etc.. G++ 17 solution 283662762 G++ 23 solution 283597439

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

»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Dark_Knight_3 (previous revision, new revision, compare).

→ Ответить
»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Auto comment: topic has been updated by Dark_Knight_3 (previous revision, new revision, compare).

→ Ответить
»
2 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

You should be using either sqrtl or binary search.

→ Ответить
»
2 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

sqrt() uses floating point, so its not "reliable". Use floating point in CP as less as you can. Use binary search.

→ Ответить
»
2 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

Actually when you need precise answer for large inputs always go for sqrtl instead of sqrt because sqrt returns a floating interger where as sqrtl returns value in double which has more accuracy than float so using sqrtl is always a better choice irrespective of compiler(But compilers do make significant difference in TC)..Hope this helps

→ Ответить
»
2 месяца назад, # |
← Rev. 2   Проголосовать: нравится +1 Проголосовать: не нравится

I made a blog about why not to use C++ 17 Here

If some problems work only in C++ 20 / C++ 23 and some other Problems work only in C++ 17, we need a fix for this problem.

→ Ответить
  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Ok, I will read the blog.

    → Ответить
  • »
    »
    2 месяца назад, # ^ |
    ← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

    I doubt that you've calculated the complexity of that solution. I can force your solution to do about sqrt(N) operations per test case, multiply that by the number of cases and it's not as small as you think.

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

      Bro, the 2 solutions are the exactly same except for one being C++ 17 and the other one being C++ 20.

      Let's say that I didn't calculate the time complexity.

      But still, the other one is accepted.

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

        Let's quote the blog: "I calculated the time complexity and it is way smaller than the time limit."

        No you didn't.

        Some differences of runtime are to be expected. There's some weird behavior of some C++ version that happens when you read something using cin and do some operations inbetween, I'm not sure exactly how.

        Still for most problems that you'll find out there if you have a good solution that won't matter.

        → Ответить
    • »
      »
      »
      2 месяца назад, # ^ |
      ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

      Are you discussing this solution .

      void solve()
{
    ll k;
    cin >> k;
    ll n = sqrtl(k);
    n += k;
    ll c = sqrtl(k);
    // cout << n -(int)sqrt(n)<< " ";
 
    while (true)
    {
        if (n - (ll)sqrtl(n) != k)
        {
            n++;
            c++;
        }
        else
        {
            break;
        }
        // n++;
        // c++;
    }
    cout << c + k << "\n";
}

      Maybe the complexity is taken down by adding sqrt(k) in the first time of answer as it is necessary to be added, and then n++ would work as there would be a lot of difference between the next two consecutive perfect square numbers when we go for large values.

      → Ответить
»
2 месяца назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

I usually write a custom function to fix this and it works all the time ¯_(ツ)_/¯

→ Ответить
  • »
    »
    2 месяца назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    The custom function that you use is using binary search or something else.

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

      nah, I still use sqrt(x) but I've solved the precision error by integer multiplication.

      → Ответить
      • »
        »
        »
        »
        2 месяца назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        Ok, I understood it by reading one of your solutions. It is a good method. Thankyou(ෆ˙ᵕ˙ෆ)♡.I will also use this.

        → Ответить
»
2 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

https://codeforces.me/contest/2020/submission/283800077 this is wa

https://codeforces.me/contest/2020/submission/283666517 this is ac

i dont know why

→ Ответить
  • »
    »
    2 месяца назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    https://codeforces.me/blog/entry/134539 In this blog, they had talked about this if I remove these three lines from your code, it is AC // #pragma GCC optimize("Ofast") // #pragma GCC optimize ("unroll-loops") // #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native") But I don't know the reason.

    → Ответить