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

Автор Abito, история, 12 месяцев назад, По-английски

Don't use sqrt because precision issues

Also here is implementation to find floor(sqrt(x))

#define int long long
int sqrt(int x){
    int l=1,r=1e9+5,ans=0,mid;
    while (l<=r){
        mid=(l+r)/2;
        if (mid*mid<=x){
            ans=mid;
            l=mid+1;
        }else r=mid-1;
    }return ans;
}

It seems std::sqrt works fine in C++17 though. Also sqrtl seems to give correct results

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

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

I used sqrtl and AC B in my first try

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

    I'm not sure about sqrtl, but I think it might have precision issues too. I think coding sqrt using binary search can be best because it's dealing with integers.

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

      yeah binary search implementation is great

      but usually sqrtl works. Sad for you u solved only A :((

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

        It's ok, I'm used to heavy drops

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

        Sad for you u use alt to reply :((

        • »
          »
          »
          »
          »
          12 месяцев назад, # ^ |
            Проголосовать: нравится -20 Проголосовать: не нравится

          Sad for you u are expected to have -51 rating change as expected by carrot :((

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

            I used sqrtl and AC B in my first try

            Sad for you, your blogs talks about people breaking the contest rules, yet u break them and admitting it :((

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

              Hmm. I guess your logic has some holes. What proves to you I use alt accounts in contests? Maybe, I used sqrtl and submitted on my main account during contest time and I just use this alt account for sharing some useful piece of info as I don't like writing from my main.

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

                I just use this alt account for sharing some useful piece of info as I don't like writing from my main.

                Could you provide an example ?

                Based on what I've seen in your blogs, it appears to me that you engage in contribution farming

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  12 месяцев назад, # ^ |
                  Rev. 4   Проголосовать: нравится -14 Проголосовать: не нравится

                  More holes in your logic. Wasn't sharing the helpfulness of sqrtl() in such problems for c++20 something useful? that it got +29 ups. Another past incidence, a colleague of yours Yousef_Sameh asked for help regarding map and unordered_map and I explained why the HashMap got TLE thru hacks, here
                  And isn't this your comment and this also . It looks to me you engage in contribution farming.

                  Aren't those mentioned comments contribution farming? Besides most of my contribution was got from catching cheaters who spoil the platform or thanking Mike for his efforts like this blog

                  However, PEACE out! I see this discussion of no relation to the post

                  Good luck for your CP journey.

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

                What proves to you I use alt accounts in contests?

                Well, technically you are newbie.

            • »
              »
              »
              »
              »
              »
              »
              7 недель назад, # ^ |
              Rev. 5   Проголосовать: нравится +18 Проголосовать: не нравится

              I found the blog on recent actions, and found this ultra funny 😂

              I break contest rules ? Then what about you, pro div2E solver 😂 ? 5

              You can check here.

              Is atcoder_merchant your alt ? (I guess yes by >90%) And I know that Wegz-Saleny is your alt. (bas wegz 7kaya wla eh r2yak, b7bo bsra7a ? Eskndrya gamda fash5 w account da 7kaya brdo mmmkn ytft7 mno mwade3 ktyyr ama nrag3 submission xD)

              • »
                »
                »
                »
                »
                »
                »
                »
                7 недель назад, # ^ |
                  Проголосовать: нравится -27 Проголосовать: не нравится

                Hello There.

                Yes, I admit that Wegz-Saleny was my alt.

                During the contest, I was taking part with my alt, I switched with my main to take a look at the leaderboard, to take a look at my peers.

                That's when I submitted my main instead of my alt in Problem C, resulting in my solutions getting skipped.

                I have stopped doing this action from that time (participating with alt) and instead participating with my main and not caring about the end result and I regret that action.

                I don't know who is atcoder_merchant.

                Lastly, I would advise you to go practice, touch grass, or do something useful. Paying attention to others is an indicator of insecurity.

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 недель назад, # ^ |
                  Rev. 5   Проголосовать: нравится -8 Проголосовать: не нравится

                  You and your alt solved Div2E. So pro 😂. I think I know that alt btw, and it isn't yours xD Btw, the skip had been for E 😉

                  In addition, alting became prohibited per Mike's Single acc policy. You can check the blog that you downvote. It includes lots of examples on those alts smurfing.

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

                  Heap_OverFlow

                  Ever consider stepping away from these types of blogs/comments? Maybe it's time to find a life, bro! xD

                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  7 недель назад, # ^ |
                  Rev. 4   Проголосовать: нравится -19 Проголосовать: не нравится

                  I shouldn't tell info about my life here bro, but I have ✪ω✪

                  I would advise you to stop farming contribution Abdelaleem. Hey!! One more _Sage. Active 17 min ago. This is ur alt it was named Abdelaleem-OR-Yousef ✪ω✪ Let me add it in the blog. For the reader, to verify, https://codeforces.com/profile/Abdelaleem-OR-Yousef

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

      sqrtl works fine for numbers up to $$$2^{62}$$$, which is imo enough for most cases. source

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

I just used plain old sqrt (with long double) and brute forced the correct value assuming that the precision error is at most +/-10

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

This gave me AC with sqrt

Code

Upd: Maybe I Just made 2 mistakes that are Canceling each other

  • »
    »
    12 месяцев назад, # ^ |
      Проголосовать: нравится -19 Проголосовать: не нравится

    You might get hacked/fst

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

      I tried to hack me now, In Local i got WA but in codeforces i got AC(Unsuccesfull hacking attempt) I think i'm lucky today. I switched to GNU C++20 (64) and got WA too

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

      you are wrong

      std::sqrt precision is good enough to work on integers (at least up to long long)

      (edit: in c++ 17)

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

Can anyone give an actual example where you should use binary search instead of std::sqrt? Never had any precision problems for integers with sqrt

Edit: it seems like there are no problems on c++ 17 but when I switch to c++ 20 it fails. Either way, writing binary search for sqrt seems too boring, just use c++ 17

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

G(n);
if(n==1)
{
    print(0);
    return;
}
if(n==2 or n==3)
{
    print(1);
    return;
}
cout<<(ll)sqrt(n-1)<<nl;




//binary search
G(n);
ll l=0,r=INF;
while(l<=r)
{
    ll mid=l+r>>1;
    ll ert=mid*mid;

    if(ert>=n)
    {
        r=mid-1;
    }
    else
    {
        l=mid+1;
    }
    // debug(ert);
}
print(r);
»
12 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

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

I upsolved some questions today and done this, i feltit magic, changing compiler ot 20, it get to wrong answer Like there undefined behavior with those built ins. Did a google dork for codeforce about sqrt with binary search as i remember encountering on leetcode, and found this great way. Thank