Spoj MOHIB1 – CPP solution

Problem: http://www.spoj.com/problems/MOHIB1/

Solution:
Let’s say that we want to answer for N. We first check the first ball, which will collide with balls 2,3,..N.
=> In the box we will then have the sum of the numbers from 2…N. Then we pick ball number 2 and it will collide with balls 3…N. => In the box we will then add sum(3…N) * 2.

=> answer for N is
answer(N) = sum (2…N) * 1 + sum(3…N) * 2 + sum(4..N) * 3 + … + sum(N…N)*(N-1)

We have to calculate this in a fast way. We can use dynamic programming for the sums and for the answers as well.
Precomputation should be done in O(N) time where N < = 10^4. Which will give us a O(1) time to answer a query (test). Let us say that we have the answer for all queries till K and we want to check for K+1. this means that the answer would be: sum (2...K) + (K+1) + (sum(3...K) + (K+1)) * 2 + (sum(4...K) + K+1) * 3 + ... + (sum(K...K) + K + 1) * (K-1) + sum(K+1 ... K+1) * K which is the same as answer(K+1) = answer(K) + sum(1...K) * (K+1). We have for sure precomputed already answer(K) and sum (1...K). => transition is very easy.

Code:

#include <cstdio>
#include <iostream>
using namespace std;

typedef unsigned long long ull;

ull dp[10001];
ull ans[10001];

void precompute() {
    for (ull i = 1; i<= 10000ULL; ++i) {
        dp[i] = dp[i-1]+i;
        if (i >= 2ULL) {
            ans[i] = ans[i-1] + dp[i-1]*i;
        }
    }
}

ull comp(int n) {
    return ans[n];
}

int main() {
    precompute();
    int t;
    scanf("%d", &t);
    while (t--) {
        int n;
        scanf("%d", &n);
        ull ans = comp(n);
        printf("%llun", ans);
    }
    return 0;
}

Leave a Reply

Your email address will not be published. Required fields are marked *