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; }