Header Ad

HackerEarth Shil and Square Sum problem solution

In this HackerEarth Shil and Square Sum problem solution, Shil has an array of N elements A1 , A2, ... ,AN . He also has an integer K. He wants to find out the value of Square Sum for every i from 1 to N-K+1.
The value of Square Sum for certain i is defined as Σ1≤ j ≤ K (j2 Ai+j-1).


HackerEarth Shil and Square Sum problem solution


HackerEarth Shil and Square Sum problem solution.

#include<bits/stdc++.h>
using namespace std;
#define rep(i,n) for(int i=0;i<n;i++)
#define ll long long int
#define pi pair<ll,ll>
#define pii pair<pi,int>
#define f first
#define mp make_pair
#define mod 1000000007
#define s second
#define pb push_back
ll a[1000011];
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0);
freopen("input-10.txt","r",stdin);
freopen("output-10.txt","w",stdout);

ll N,K;
cin >> N >> K;
for(int i=1;i<=N;i++){
cin >> a[i];
}
ll sum=0;
ll sum1=0;
ll sum2=0;
for(ll i=1;i<=K;i++){
sum+=(i*i*a[i])%mod;
sum1+=(i*a[i])%mod;
sum2+=a[i];
sum%=mod;
sum1%=mod;
sum2%=mod;
}
cout<<sum<<" ";
for(ll i=K+1;i<=N;i++){

sum+=sum2;
sum-=2*sum1;
sum+=(K*K*a[i])%mod;

sum1-=sum2;
sum1+=(K*a[i])%mod;

sum2-=a[i-K];
sum2+=a[i];

sum%=mod;
if(sum<0) sum+=mod;

sum1%=mod;
if(sum1<0) sum1+=mod;

sum2%=mod;
if(sum2<0) sum2+=mod;

cout<<sum<<" ";
}
}


Second solution

#include<bits/stdc++.h>

#define bs 1000000007

const int N = 1200050;

using namespace std;

int n, k;
long long ar[N];
long long pref[N];
long long s;
long long deriv;

int main(){
ios_base::sync_with_stdio(0);

cin >> n >> k;

for (int i = 1; i <= n; i++)
{
cin >> ar[i];
}

for (int i = 1; i <= n; i++)
{
pref[i] = pref[i - 1] + ar[i];
pref[i] %= bs;
}

for (int i = 1; i <= k; i++)
{
s += 1ll * i*i%bs*ar[i] % bs;
}
s %= bs;

cout << s;

for (int i = 2; i <= k; i++)
{
deriv += (2 * i - 1)*ar[i] % bs;
}

for (int i = 2; i <= n - k + 1; i++)
{
s = s - ar[i - 1] + bs;
s %= bs;
s -= deriv;

while (s < 0)
s += bs;

deriv = deriv - 3 * ar[i] + bs;
deriv %= bs;
deriv -= 2 * (pref[i + k - 1] - pref[i]) % bs;
while (deriv < 0)
deriv += bs;
s += ar[i + k - 1] * k%bs*k%bs;
s %= bs;
deriv += (2 * k + 1) * 1ll * ar[i + k - 1] % bs;
deriv %= bs;
cout << " " << s;
}

cout << endl;

return 0;
}

Post a Comment

0 Comments