epsilon_573's blog

By epsilon_573, history, 5 years ago, In English

So I was looking through my WA verdict on today's Educational Round Problem C. It failed on the following case,

But when I run the test locally for the first 12 queries (couldnt access the full test case), It gives the expected output.

Submission : https://codeforces.me/contest/1342/submission/78206445

What is the problem here? I don't quite get it. Thanks for the help :)

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

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

run your code with "Clang++17 Diagnostics". this compiler will found a bug

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

    Same code on submitting with C++17 gets accepted. Funnily enough, I use C++14 locally.

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

      CLANG C++ DIAGNOSTICS! it is not simple c++17 compiler. clang can found some mistakes such as RE (division by 0, out of bounds array etc). I try to run your code with it and it found a mistake. you can find this compiler on codeforces (problemset->custom test, then choose this compiler and run with a sample) it will found a mistake and give you a report

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I understand that but how can just changing language version change WA to AC? Try to submit my code with C++17 (GNU)

»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

On the 12th query, the floor((db)r/(db)lcm) == (db)r/(db)lcm statement evaluates to true in C++14 and false in C++17. I assume that some change in C++17 changed floating point arithmetic.

In general, just avoid using floating point if possible. They're painful to debug and not consistent on different compilers. This problem can be solved without floating point, so if you want you can try rewriting your solution again with that strategy. I personally would rather not have the correctness of my code depend on the compiler I'm using.

  • »
    »
    5 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    But it gives expected output even with C++14 when testing locally.

    Also can you share your approach for the problem? I tried to look at your code but I don't get it.

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

      My solution splits the query into x blocks of size a*b, with one (potentially empty) block left over.

      The answer for each block is the same, and can be calculated in O(A*B) time by iterating through from 0 to a*b and checking if (i % a) % b == (i % b) % a. I don't know how to rigorously prove this, but it's probably in the editorial.

      Then for the last partial block, the answer can be calculated with a prefix sum that was calculated beforehand. Many solutions got hacked with TLE because they didn't calculate the prefix sum for the partial block.

      So we have sum[i] which holds the count of numbers that meet the condition in the problem from 0 to i. For each full block we add sum[a*b - 1], and then for the last block add sum[M % (a*b)] where M is the size of the query you're trying to solve.

      Also, for simplicity, each query with L, R is converted into ans(R) - ans(L-1) to ensure that the blocks line up.

      Some solutions used lcd(a, b) instead of a*b, and they're faster than mine. But both should pass.

      You should probably read the actual editorial as well. It will almost certainly make more sense than what I just wrote.

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

        No, it does make perfect sense. I actually wrote a brute force solution and noticed a pattern that (i % a) % b == (i % b) % a only when i lies in the range [ n*LCM , n*LCM + max(a,b) ) where n is any integer and I am counting such blocks in my answer.

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        I submitted a solution 78241725 that failed on the 48405th query of test case 2. Instead of precalculating all numbers from 0 to a*b, and then using the periodic property of that, I used this idea.

        1. (i%a)%b will be equal to (i%b)%a for all i from l to b (l included, b excluded)

        2. For every b numbers after i (i included), where i%lcm==0, the value of (i%a)%b will be equal to (i%b)%a.

        I computed this count, taking care of left and right limits, but funnily enough my testcase 2 failed at 48405th query, seems some corner case is missing.Any help will be appreciated. PS. I managed to solve the way you did later after the contest, and it worked.

        #include <bits/stdc++.h>
        
        // definitions
        #define F first
        #define S second
        #define all(x) x.begin(), x.end()
        #define clr(x) memset(x, 0, sizeof(x))
        #define rep(i, l, r) for (long long i = (l); i < (long long)(r); i++)
        #define repb(i, r, l) for (long long i = (r); i > (long long)(l); i--)
        #define pb push_back
        #define mod1 998244353
        #define mod 1000000007
        #define MAX_CHAR 256
        
        using namespace std;
        typedef vector<long long> vl;
        typedef vector<char> vc;
        typedef vector<string> vs;
        typedef vector< pair<long long, long long> > vp;
        typedef vector<tuple<long long , long long , long long> > vtup;
        typedef deque <long long> dq;
        typedef long double ld;
        typedef long long ll;
        typedef unsigned long long ull;
        
        
        // standard functions
        ll gcd(ll x, ll y) {
            if (x < y) return gcd(y, x);
            if (y == 0) return x;
            return gcd(y, x % y);
        } 
         
        
        
        ll modexp(ll x, ll ex, ll modp) {
            ll ans = 1ll;
            while (ex > 0) {
                if (ex & 1ll) ans = (ans * x)%modp;
                ex >>= 1ll;
                x = (x * x)%modp;
            }
            return ans;
        } 
         
        ll nCrModp(ll n, ll r, ll p) 
        { 
            ll C[r+1]; 
            memset(C, 0, sizeof(C)); 
          
            C[0] = 1; 
            for (ll i = 1; i <= n; i++) 
            { 
                for (ll j = min(i, r); j > 0; j--) 
                    C[j] = (C[j] + C[j-1])%p; 
            } 
            return C[r]; 
        }
         
        bool isPrime(ll n) 
        { 
            if (n <= 1)  return false; 
            if (n <= 3)  return true;  
            if (n%2 == 0 || n%3 == 0) return false; 
          
            for (ll i=5; i*i<=n; i=i+6) 
                if (n%i == 0 || n%(i+2) == 0) 
                   return false; 
          
            return true; 
        } 
         
        vl countFreq(ll arr[], ll n) 
        { 
            unordered_map<ll, ll> mp; 
            vector <ll> v;
            
            for (ll i = 0; i < n; i++) 
                mp[arr[i]]++; 
           
            for (auto x : mp) 
                v.pb(x.second);
            
            return v;
        }
        
        ll binarySearch(ll arr[], ll l, ll r, ll x) 
        { 
            while (l <= r) 
            { 
                ll m = l + (r - l) / 2; 
                if (arr[m] == x) 
                    return m; 
                if (arr[m] < x) 
                    l = m + 1; 
                else
                    r = m - 1; 
            }
            return -1; 
        }
        
        const ll MAXSIEVE=(1e3);
        ll spf[MAXSIEVE];
        void sieve() 
        { 
            spf[1] = 1; 
            for (ll i=2; i<MAXSIEVE; i++) 
                spf[i] = i; 
        
            for (ll i=4; i<MAXSIEVE; i+=2) 
                spf[i] = 2; 
          
            for (ll i=3; i*i<MAXSIEVE; i++) 
            { 
                if (spf[i] == i) 
                { 
                    for (ll j=i*i; j<MAXSIEVE; j+=i) 
                        if (spf[j]==j) 
                            spf[j] = i; 
                } 
            } 
        }
        
        ll countDivisibles(ll A, ll B, ll M) 
        { 
            // Add 1 explicitly as A is divisible by M 
            if (A % M == 0) 
                return (B / M) - (A / M) + 1; 
          
            // A is not divisible by M 
            return (B / M) - (A / M); 
        }
        
        // code beigns in main
        int main()
        {
            
            ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
            ll t;
            cin >> t;
            
            while(t--)
            {
                ll a,b;
                cin >> a >>b;
                
                if(a>b)
                    swap(a,b);
                ll lcm=(a*b)/gcd(a,b);
                ll q;
                cin >> q;
                
                rep(i,0,q)
                {
                    ll l,r;
                    cin >> l >> r;
                    
                    ll tot=r-l+1;
                    ll count=countDivisibles(l, r, lcm);
                    
                    ll ini=0;
                    rep(j,l,r+1)
                    {
                        if(j<b)
                            ini++;
                        else
                            break;
                    }
                    ll last=r+1;
                    repb(j,r,l-1)
                        if(j%lcm==0)
                        {
                            last=j;
                            break;
                        }
                    
                    ll oth=max(b*(count-1),0ll);
                    oth+=min(b,r-last+1);
                    tot=tot-(oth+ini);
                    
                    cout << tot << " ";
                }
                cout << endl;
            }
        }