PROBLEM LINK:
Setter- Choudhury Istasis Mishra
Tester- Choudhury Istasis Mishra, Adhyyan Sekhsaria
Editorialist- Abhishek Pandey
DIFFICULTY:
EASY
PRE-REQUISITES:
Prefix and Suffix Sums (…or {(Prefix\space Sums)}^{4} 
)
PROBLEM:
For every element of the array, we need to calculate contribution of other cities if it became capital. Contribution of j'th city to i'th city is given by A_j* \sum_{k=2}^{d}{k\choose2} where d=|i-j|+1.
QUICK EXPLANATION:
Once you take the array as an input, get a copy of it (say prefix[n]), and perform prefix-sum algorithm 4 times on it. Similarly make a new array suffix[n] and do suffix sum of it 4 times. The answer is now simply prefix[i-1]+suffix[i+1] for city i.
EXPLANATION:
While I am sure this question gave many contestants a headache to solve during contest, the idea behind it was surprisingly simple. In the editorial, I will give a very brief view of solutions of other sub-tasks and primarily focus on the full solution.
Subtask-1-
Merely simulating what the question demands will do. Such an algorithm will be running in O({N}^{3}), and since N\le1000 for subtask 1, we should try to keep operations basic and simple. A pre-calculation of n\choose2 for all values of N can help.
Subtask-2-
The basic concept behind this one was pre-calculating all the values of n\choose2, calculating the prefix-sum of then to obtain \sum_{k=2}^{i}{k\choose2}, and then AGAIN using prefix sum to obtain \sum_{i=1}^{j}(\sum_{k=2}^{d}{k\choose2}) which would be answer for city i if population is 1.
Full Solution-
So far we have been doing a lot of prefix sums. Time to take it to the next level 
For now, let us simulate what happens if we do prefix sum. Lets say, we want to know contribution of an element, arr[i]=k in prefix sum of elements from [i+1,N].
Currently, our array is - [...,arr[i],arr[i+1],arr[i+2]....]. Since I want to highlight only contribution of arr[i]=k in elements occurring after index i, let me represent it as [k,0,0,0,0] for now.
What happens on doing prefix sum of this first time? We have to focus on contribution of k for now.
Doing prefix sum first time-
Arr=[k,k,k,k,k]
Contribution of arr[i] in all those elements is k after first time.
What if we do prefix sum again? Doing it second time, we get-
Arr=[k,2*k,3*k,4*k,5*k]
The contribution became equal d*k where d=|i-j|+1. Now, recall that {n \choose2}= n*(n-1)/2 which is nothing but sum of all numbers from [1,n-1]. This gives an intuition that, what if we do prefix sum again? We will get the required sum of numbers!
After third prefix sum-
Arr=[k,3*k,6*k,10*k,15*k].
Look at coefficients of k !! Are they not of the form of “Sum of natural numbers from 1 to …”??
If we take an index j such that j>i, we can verify from above observations that the coefficient of k is nothing but sum of natural numbers from 1 to |j-i|+1=d. Recall that contribution of a city to itself is 0. Hence, obviously in final answer, we will need to add something like prefix[i-1] to get contribution for cities upto i. If coefficient of k at i'th index is sum of natural numbers till i, then coefficient at (i-1)'th index will be n*(n+1)/2-n=n*(n-1)/2={n \choose 2}. In terms of problem/question, we will get d \choose 2.
Now the idea is quite clear! We just need to do prefix sum one more time to make contribution of element arr[i] equal to \sum_{i=1}^{j} {d \choose 2}
After fourth prefix sum, it becomes-
Arr=[k,4*k,10*k,20*k,35*k]
Remember that I just simulated contribution of a single element for demonstration purposes only. When we do prefix sum, the appropriate contribution of every element is added up . In other words, The contribution of i'th element gets appropriately added up to respective elements after it.
To add contribution of i'th element to elements before it, we simply use suffix sum in a similar fashion
Once done, we can clearly state answer as Ans=prefix[i-1]+suffix[i+1] (Recall that contribution of city to itself is 0, and prefix[i] is for contribution of cities upto index i and vice versa). You can refer to editorialist’s solution for more details
SOLUTION:
Click to view
#include <bits/stdc++.h>
using namespace std;
#define int long long int
const int mod = 1e9+7;
#undef int
int main()
{
#define int long long int
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin>>t;
while(t--)
{
int n;
cin>>n;
vector<int> v(n+1);
for(int i = 1;i<=n;i++)
cin>>v[i];
vector<int> pre(n+1), suf(n+2);
for(int i = 1;i<=n;i++)
pre[i] = (pre[i-1]+v[i])%mod;
for(int i = 1;i<=n;i++)
pre[i] = (pre[i-1]+pre[i])%mod;
for(int i = 1;i<=n;i++)
pre[i] = (pre[i-1]+pre[i])%mod;
for(int i = 1;i<=n;i++)
pre[i] = (pre[i-1]+pre[i])%mod;
for(int i = n;i>0;i--)
suf[i] = (suf[i+1]+v[i])%mod;
for(int i = n;i>0;i--)
suf[i] = (suf[i+1]+suf[i])%mod;
for(int i = n;i>0;i--)
suf[i] = (suf[i+1]+suf[i])%mod;
for(int i = n;i>0;i--)
suf[i] = (suf[i+1]+suf[i])%mod;
vector<int> cost(n+1);
for(int i = 1;i<=n;i++)
cost[i] = (pre[i-1]+suf[i+1])%mod;
for(int i = 1;i<=n;i++)
cout<<cost[i]<<" ";
cout<<endl;
}
return 0;
}
Click to view
/*
*
********************************************************************************************
* AUTHOR : Vijju123 *
* Language: C++14 *
* Purpose: - *
* IDE used: Codechef IDE. *
********************************************************************************************
*
Comments will be included in practice problems if it helps ^^
*/
#include <iostream>
#include<bits/stdc++.h>
using namespace std;
int mod=pow(10,9)+7;
int main() {
// your code goes here
#ifdef JUDGE
freopen("input.txt", "rt", stdin);
freopen("output.txt", "wt", stdout);
#endif
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
int t;
cin>>t;
while(t--)
{
int i,n;
cin>>n;
int arr[n];
for(i=0;i<n;i++)cin>>arr[i];
int pre[100010]={0},suff[100010]={0};
for(i=1;i<=n;i++)
{
pre[i]=arr[i-1];
suff[n-i+1]=arr[n-i];
}
/**Simulate what happens when we do prefix sum 4 times.
* Take example of pre[5]. Let arr[1]=k. What is contribution of arr[1] after 4 prefix sum to pref[5]?
* First iteration-->pre[1]=pre[2]=pre[3]=pre[4]=pre[5]= k
* Second iteration---> pre[2]=2k pre[3]=3k pre[4]=4k pre[5]=5k
* Coefficient of k in pre[i]=i.
* Third iteration ---> pre[2]=3k pre[3]=6k pre[4]=10k pre[5]=15k;
* Note now coefficient of k in pre[i]= (i+1)C2
* Fourth Iteration --->pre[2]=4k pre[3]=10k pre[4]=20k pre[5]=35k.
* Last prefix sum gave us the needed values
*/
for(int j=1;j<=4;j++)
{
for(i=1;i<=n;i++)
pre[i]=(pre[i-1]+pre[i])%mod;
for(i=n;i>0;i--)
suff[i]=(suff[i+1]+suff[i])%mod;
}
for(i=1;i<=n;i++)
cout<<(pre[i-1]+suff[i+1])%mod<<" ";cout<<endl;
}
return 0;
}
CHEF VIJJU’S CORNER 
1. Some related problems for practice-