PROBLEM LINK:
Author: Sanchit Raina
Tester: Prajwal Sonwane
Editorialist: Sanchit Raina
DIFFICULTY:
SIMPLE
PREREQUISITES:
Math
PROBLEM:
A shopkeeper in Starling City, sells ARROWS. He has decided to sell them for ₹1 for the first day,₹2 for next 2 days, ₹3 for next 3 days … ₹N for next N days. He sells only 1 arrow on a single day.
OLIVER, being the VIGILANTE buys all the available ARROWS on any day. Diggle is wondering the amount OLIVER needs to pay to the Shopkeeper after N days.
Since Diggle is busy right now. Can you find this amount for him?
QUICK EXPLANATION:
To find sum of the series 1 + 2 + 2 + 3 + 3 + 3 … upto N terms
EXPLANATION:
Here, we are required to find the sum of series, S(N) = 1 + 2 + 2 + 3 + 3 + 3 + 4 + 4 + 4 + 4 ... upto N terms.
The solution is easy(for smaller N), a simple loop to add all the numbers in the series, :
int sum=0,k=1,times=0;
for(int i=1;i<=n;i++){
sum=sum+k,times++;
if(times==k)times=0,k++;
}
But, for N \leq 1e9, this solution is surely going to lead to TLE. So, we need to think of improvising the solution.
Hint
Think of breaking down the series into some known sums, which can be calculated in O(1). Think before you see the full solution.
Full Solution
Ideally, this can be written as S(N) = S(K) + (K+1) + (K+1) + (K+1) …
, where S(K) = (1 * 1) + (2 * 2) + (3 * 3) + … + (K * K) = \sum_{n=1}^{n=K} n^{2},
and (K+1) is added N-x times, where x is the greatest integer less than N, such that it can be \sum_{n=1}^{n=K} n^{2}, i.e. sum of first K terms of the form a^{2}
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define ll long long
#define TEST ll T;cin>>T;while(T--)
using namespace std;
int main() {
TEST {
ll n;
cin >> n;
ll start = 0, i = 1;
while (start + i <= n) {
start += i;
i++;
}
ll k = i-1;
ll sum_of_k_sqaure_upto_i_minus_1 = (k*(k+1)*(2*k+1))/6;
ll ans = sum_of_k_sqaure_upto_i_minus_1;
ans += (n - start) * i;
cout << ans << '\n';
}
return 0;
}
Link to AC Solution : (CodeChef: Practical coding for everyone)