pottiVJ's blog

By pottiVJ, history, 2 months ago, In English

I have attached 3 screenshots, one in local, another in CodeChef online compiler as well as submission on code forces. for Testcase 2 — case 4, gives correct output as expected in codechef online compiler as well as in local, but gives the wrong answer in codeforces submission. Can anyone please help.

question link : https://codeforces.com/contest/1737/problem/B submission : https://codeforces.com/contest/1737/submission/175028607

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

The same happens to me. The inbuilt sqrt give some precision error for long integers in different systems. You can either use sqrtl (made especially for long long) or find it simply using binary search.

The following code will have different results on codeforces vs my local machine.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

ll bs_sqrt(ll x) {
    ll left = 0, right = 2000000123;
    while (right > left) {
        ll mid = (left + right) / 2;
        if (mid * mid > x)
            right = mid;
        else
            left = mid + 1;
    }
    return left - 1;
}

int main() {
    ll l, r;
    cin >> l >> r;
    ll sql_1 = sqrt(l), sqr_1 = sqrt(r);
    ll sql_2 = sqrtl(l), sqr_2 = sqrtl(r);
    ll sql_3 = bs_sqrt(l), sqr_3 = bs_sqrt(r);
    cout << sql_1 << " " << sqr_1 << '\n';
    cout << sql_2 << " " << sqr_2 << '\n';
    cout << sql_3 << " " << sqr_3 << '\n';
    return 0;
}

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks! Thanks! Thanks! I learned sqrtl from your here and fixed some improper use of sqrt in my code, as a good result, it ACCEPTED!!! THANK YOU for your SQRTL!!!

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it
      • »
        »
        »
        »
        5 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        why do we need to start with right = 2000000123,we can also start with right = x right because sqrt(x) will be anyways less than x

        what is the significance here using the number 2000000123?

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Thank you so much