First Impression (CC002) - Editorial

PROBLEM LINK:
Practice
Contest

Author:Srijan Agrawal
Tester:Yash Sharma
Editorialist:Yash Sharma

PROBLEM EXPLANATION:

Find the sum of alternate consecutive d odd numbers from the range L to R inclusive and the number of odd numbers between L and R (both inclusive) is a multiple of d.

DIFFICULTY:
Easy

PREREQUISITES:
None

EXPLANATION:

First thing we need to figure out is the number odd numbers between L and R and starting from first odd number sum of first d odd number can be calculated using summation formula of AP with common difference of 2. Let it be K , so the sum of next d odd numbers will be :thinking::thinking: :

This can be seen as we know that the difference between i^{th} number and (d+i)^{th} odd number is 2*d (take any example). so for all next d numbers the difference will become (d*2*d) i.e 2*d^2.

So the series will become : K, K + 2*d^2, K + 4*d^2, K + 6*d^2, K + 8*d^2 and so on. But we need the sum of alternate d odd numbers so our AP will be become K, K + 4*d^2, K + 8*d^2, K + 12*d^2 and so on.

Clearly this is an AP with common difference 4*d^2 and the sum of this AP with modulo 10^9 + 7 is our answer.

AUTHORS AND TESTERS SOLUTIONS :

Setter's Solution
  import sys
  #sys.stdin=open('input3.txt','r')
  #sys.stdout=open('output3.txt','w')
  mod=10**9+7
  t=int(input())
  for _ in range(t):
     d=int(input())
     l,r=map(int,input().split())
     if(l%2==0):
           l+=1
     if(r%2==0):
          r-=1
     first=l+(d-1)
     last=r-(d-1)
     #print(first,last)

     n=(last-first)//(4*d)+1
     #print(n)
     print((n*(first+last)*d//2)%mod) 
Tester's Solution
 #include <bits/stdc++.h>
 #define ll long long
 #define dl double
 #define rep(i,n)  for(int i = 0; i < n; i++)
 #define all(cont) cont.begin(), cont.end()
 #define rall(cont) cont.rbegin(), cont.rend()
 #define FOREACH(it, l) for (auto it = l.begin(); it != l.end(); it++)
 #define IN(A, B, C) assert( B <= A && A <= C)
 #define unique(a)       sort((a).begin(), a.end()), (a).erase(unique((a).begin(), 
 (a).end()),(a).end())
 #define Assert(x)       {if(!(x)){cerr<<"Assertion failed at line "<<__LINE__<<": " 
 <<#x<<" = "<<(x)<<"\n";exit(1);}}
 #define MP make_pair
 #define PB push_back
 #define INF (int)1e9
 #define mod 1000000007
 using namespace std;
 
 int main()
 {
       ll i,j,n,m,a,b,t,d,l,r,co;
       cin>>t;

       while(t--)
       {
          cin>>d;

          cin>>l>>r;

          if(l%2 == 0 && r%2 == 0)
          {
               n = (r-l)/2;
          }
         else
         {
             n = (r-l)/2;
             n = n+1;
         }

         co = n/(2*d);
         ll temp = n - (co*2*d);
         if(temp >= d)
         {
             co += 1;
         }

         if(l%2 == 0)
             l = l+1;

         co--;

         ll ans = (sum*(co+1)%mod+ (d*(co*(4*d + (co-1)* 
           (2*d)%mod))%mod)%mod)%mod;

         cout<<ans%mod<<"\n";
     } 

     return 0;
 }
1 Like

Can you please elaborate it how it becomes 2dd