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

Автор 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 Проголосовать: не нравится