CLASH WILDCARD - OLIVER

PROBLEM LINK:

Practice

Contest

Author: Sanchit Raina

Tester: Prajwal Sonwane

Editorialist: Sanchit Raina

DIFFICULTY:

SIMPLE

PREREQUISITES:

Math

Sum upto N, N^2

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, :abacus: :

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)