ARRCENT - Editorial

PROBLEM LINK:

Contest
Practice

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} :stuck_out_tongue: )

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 :slight_smile:

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 :slight_smile: . 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 :slight_smile:

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 :slight_smile:

SOLUTION:

Setter

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

Editorialist

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 :smiley:

1. Some related problems for practice-

7 Likes

Hats off to the problem setter, such a great problem.

5 Likes

Can you explain the suffix part as the prefix part is straight forward;

like for n=5 (consider 1 indexing)

 here x(i) is i*(i+1)*(2*i+1)/12 - i*(i+1)/4;

 answer would be 

for i=1 [a(2)x(2)+a(3)x(3)+a(4)x(4)+a(5)x(5)]

for i=2 a(1)x(2) + [a(3)x(3)+a(4)x(4)+a(5)x(5)]

for i=3 a(1)x(3)+a(2)x(2) + [a(4)x(4)+a(5)x(5)]

for i=4 a(1)x(4)+a(2)x(3)+a(3)x(2) + [a(5)x(5)]

for i=5 a(1)x(5)+a(2)x(4)+a(3)x(3)+a(4)x(2)

So finding the second term is easy but how to find the first term

i mean efficiently as if running simple loop gives time complexity of O(n^2)

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 or ,in other words, \binom {d}{2}.

It should be \binom{d + 1}{2}. I think it will be clearer to write that, for j > i, the coefficient of k in arr[j - 1] is the sum of natural numbers from 1 to |(j - 1)−i|+1=d - 1, which is equal to \binom{d}{2}, since j - 1 is the index which will store the answer for the j^{th} index. Please correct me if I’m wrong.

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^{j}_{i=1} \binom{d}{2}.

I don’t get how it is \sum_{i = 1}^{j} \binom{d}{2}. Shouldn’t it be \sum_{x = i, x \not = j}^{j} \binom{d}{2}, where d = |j - x| + 1? Also, this would be stored at arr[j - 1], right?

Recall that contribution of city to itself is 0, and prefix[i] is for contribution of cities before index i and vice versa.

Isn’t prefix[i] for contribution of cities before and including i for the (i + 1)^{th} city? Isn’t it the reason we’re using prefix[i - 1] for the i^{th} city?

Please answer my queries, these few things have been preventing me from understanding the editorial completely.

@the_extractor

Isn't prefix[i] for contribution of cities before and including i for the (i+1)th city? Isn't it the reason we're using prefix[i−1] for the ith city?

Yes. While writing that i was not aiming at a formal definition, my aim was to refer to roughly what prefix[i] and suffix[i] are. My aim was on “what is it prefix of” rather than “prefix from x to y”. I think “cities upto i” is more suitable word here. Thanks. :slight_smile:

It should be (d+1C2). I think it will be clearer to write that, for j>i, the coefficient of k in arr[j−1] is the sum of natural numbers from 1 to |(j−1)−i|+1=d−1, which is equal to (dC2), since j−1 is the index which will store the answer for the jth index. Please correct me if I'm wrong.

The problem which I faced while explaining this was - see the formula. We are adding prefix[i-1] to the answer. It means, if I am adding j'th index to answer, then actually I am calculating contribution of (j+1)'th index - due to which I wrote d\choose 2. I need to reword it. I apologise.

I don't get how it is ∑j∗i=1(d2). Shouldn't it be ∑j∗x=i,x≠j(d2), where d=|j−x|+1? Also, this would be stored at arr[j−1], right?

Sorry I didnt get your question here. But please refer to implementation for details. I pasted the solutions so you guys can view while @admin fixes link. :slight_smile:

1 Like

@vijju123 Thanks! I get it now.

Sorry I didnt get your question here.

What I want to know is, \sum_{i=1}^j {d \choose 2} simply means we are adding the contributions of all the cities before a given city, right?

Also, how do you use that different font?

i=2 to d sum( C(i,2)) is equal to (d-1)d(d+1)/6. We could use this to calculate contribution as function of d. Now to caculate answer each element can be computed on O(n) time as sum(a[j]*cost(d(i,j)). which can be done in O(n^2) time total. or you can notice that it’s a convolution and use fft to reduce convolution time to O(nlogn).

I did solve it but did convolution in O(n^2) time and could implement fft.
https://www.codechef.com/viewsolution/19286316

Its more like

for i=1 [a(2)x(2)+a(3)x(3)+a(4)x(4)+a(5)x(5)]

for i=2 a(1)x(2) + [a(3)x(2)+a(4)x(3)+a(5)x(4)]

for i=3 a(1)x(3)+a(2)x(2) + [a(4)x(2)+a(5)x(3)]

for i=4 a(1)x(4)+a(2)x(3)+a(3)x(2) + [a(5)x(2)]

for i=5 a(1)x(5)+a(2)x(4)+a(3)x(3)+a(4)x(2)

Also, not sure what you are trying to ask. Can you be more clear?

Thank you!

1 Like

Suffix part is exact repetition of prefix part. Please see editorialist’s solution.

DIFFICULTY:
EASY
Are u sure ??

2 Likes

Its like, if you get the intuition/trick, its easy - else its impossible. I tried for 3 days but couldnt find any other alternate approach.

1 Like

Thanks for tagging @aryanc403

1 Like

But Difficulty != implementation only.
Difficulty != How easy it is to reach a soln = intuition/trick + implementation .

1 Like

xD. What can a poor editorialist do? :o

2 Likes

Yes, that is right. Thank you for helping me improve the editorial :slight_smile:

The 4th prefix sum is just to get contribution for every city before i

Okay. How do you use the different font when you are replying to someone?

What different font? I didnt get it? You surely dont mean the latex one, right?

In your answer above ( ARRCENT - Editorial - #5 by vijju123 - general - CodeChef Discuss ), you have written the first line (Isn’t prefix[i] for … for the ith city?) in a different font. I’m asking about that.

Omg I am so sorry, it slipped my mind to answer it. For that different text, I use ` symbol.

Just enclose the text within a pair of ` (no spaces between text and symbol + no new lines )and it will turn into telephonic text (i dont remember if it was the correct name) xD