ALGOCUP1 - Editorial

PROBLEM LINK:

Practice
AlgoCup Contest

Author: Sobhagya singh dewal
Tester: Sankalp Gupta

DIFFICULTY:

EASY-MEDIUM

PREREQUISITES:

Math

PROBLEM:

Sum of multiplication of each ordered pair of integers from L to R

QUICK EXPLANATION:

(Square of sum of L to R)-(sum of squares of L to R)

EXPLANATION:

We are using the identity:

( a+ b+ c+ d)^2 = a^2 + b^2 + c^2 + d^2 + 2ab +2bc +2ac + 2ad + 2bd + 2cd

2ab +2bc +2ac + 2ad + 2bd + 2cd = ( a+ b+ c+ d)^2 - (a^2 + b^2 + c^2 + d^2)

Extending the above identity for large number of variables will provide the below expression:

sum=(\sum_{i=1}^{r}a_{i})^{2}-\sum_{i=1}^{r}a_{i}^{2} = ((\sum_{i=1}^{l}a_{i})^{2}-\sum_{i=1}^{l}a_{i}^{2})

And we have formulas for sum of first n natural numbers and sum of squares of first n natural numbers .

SOLUTIONS:

Setter’s Solution
#include<bits/stdc++.h>
#define int long long int
int mod=1e9+7;
using namespace std;
 
int power(int x, int y, int p)
{
    int res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
        res = (res * x) % p;
        y = y >> 1;
        x = (x * x) % p;
    }
    return res;
}
int imod(int a, int m)
{
    return power(a, m - 2, m);
}
 
int squre(int n)
{
    int ans=n;
    ans=((n+1)*ans)%mod;
    ans=((2*n+1)*ans)%mod;
    ans=(ans*imod(6,mod))%mod;
    return ans;
}
 
int linear(int n)
{
    int ans=(n*(n+1))/2;
    return ans%mod;
}
 
int32_t main()
{
    int tt;
    cin>>tt;
    while(tt--)
    {
        int l,r;
        cin>>l>>r;
        int xx=(squre(r)-squre(l-1)+10*mod)%mod;
        int yy=(linear(r)-linear(l-1)+10*mod)%mod;
        int zz=(yy*yy-xx+10*mod)%mod;
        cout<<zz<<"\n";
    }
}
Tester's Solution
#include<bits/stdc++.h>
#define ll long long int
#define ull unsigned long long int
#define vi vector<int>
#define vll vector<ll>
#define vvi vector<vi>
#define vvl vector<vll>
#define pb push_back
#define mp make_pair
#define all(v) v.begin(), v.end()
#define pii pair<int,int> 
#define pll pair<ll,ll>
#define vpii vector<pii >
#define vpll vector<pll >
#define ff first
#define ss second
#define PI 3.14159265358979323846
#define fastio ios_base::sync_with_stdio(false) , cin.tie(NULL) ,cout.tie(NULL) 
ll power(ll a,ll b){ ll res=1; while(b>0){ if(b&1) res*=a; a*=a; b>>=1;} return res; }
ll power(ll a,ll b,ll m){ ll res=1; while(b>0){ if(b&1) res=(res*a)%m; a=(a*a)%m; b>>=1;} return res;}
bool pp(int a,int b) {return a>b;}
using namespace std;
ll m=1e9+7;
 
ll mul(ll a,ll b){
    return (a*b)%m;
}
 
ll qube(ll a){
    ll res=a;
    res = mul(res,a+1);
    res = mul(res,2*a+1);
    res = mul(power(6,m-2,m),res);
 
    return res;
}
 
void solve(){
    ll l,r;
    cin>>l>>r;
    assert(r<=1e8&&r>=l&&l>0);
    ll sum=0;
    ll lint = r*(r+1) - l*(l-1);
    lint = lint/2;
    lint = lint%m;
    ll rint = (qube(r) - qube(l-1) + m)%m;
    sum = (mul(lint,lint) - rint + m)%m;
    cout<<(sum)<<"\n";
}
 
int main()
{
    fastio;
    int t;
    cin>>t;
    assert(t<=1e5&&t>0);
    while(t--){
        solve();
    }
 
    return 0;
}
1 Like

I think both the provided solutions are wrong, @sank_1611 can you check this.

You’re right. Tester’s solution looks wrong. And in setter’s, I don’t know why the code is made so complex with mod. And what’s 10*mod is doing in main()?

Sorry from my side for this, actually tester’s solution is completely replaced by some other code, but Setter’s solution is correct if we take mod of xx and yy variables. You can find same code with a AC verdict on Codechef
Solution

Sorry if you find the code complex, actually I use to add 10*mod whenever I am taking mod after subtraction because It save me from negative values, and badly I know only this method for avoiding negative values after mod.
Here you may find how to avoid negative values after mod
mod

Both Solutions are updated.

Thanks for the update!

If you don’t perform modulus operation correctly at each step then theoretically using 10*MOD can also fail, but if you perform modulus correctly at each step then you would just need to add MOD once to handle negative numbers.

I got your point, but I mostly use 10*MOD .
But yeah it will be fine if you just use MOD