# PROBLEM LINK:

Table Sum (Past INOI Problems)

**Author :** admin3

**Editorialist :** Prakhar Kochar

# DIFFICULTY:

EASY

# PREREQUISITES:

Implementation , Maximum Prefix

# PROBLEM:

Given a sequence A containing N integers. There are N possible ways to form an another sequence B where construction of B follows the following order :

B_1 = [1, 2,

. . .N], B_2 = [2, 3,. . .N, 1],. . .B_N = [N, 1,. . .N-1]

Your task is to determine following value for each of the B_{ith} sequence

max (A_1 + B_{i,1} , A_2 + B_{i,2}, A_3 + B_{i,3}, β¦, A_n + B_{i,n})

# EXPLANATION:

## Brute-Force approach ! O(n^2)

Observe that we can generate sequence B_{i} from sequence B_{i-1} by increasing every value of B_{i-1} by 1 and decreasing B_{i-1,n-i+1} by N, β i β [1,N].

We can solve this problem without actually generating every sequence of B and make use of the observation above. Initially increment A_i by i β i β [1,N]. Now perform N iterations.In i_{th} iteration we have to perform following tasks :

Task 1 : Find max element in sequence A and print it.

Task 2 : Increment A_i by 1 β i β [1,N]

Task 3 : Decrement A_{n-i-1} by N β i β [1,N]

If we look closely we are making use of the above observation and cleverly incrementing and decrementing values of A to switch from one sequence of B to another to get our required maximum. Performing all the tasks in i_{th} iteration required a linear time, therefore overall time complexity will be O(n^2).

## Can we improve this time complexity of O(n^2) ?

Yes. In i_{th} iteration we can reduce time complexity of performing tasks from O(n) to O(log(n)) thereby reducing the overall time complexity to O(nlog(n))

How ? Make use of multiset or segment trees to perform task operations above. Now tasks in i_{th} operation looks like :

Task 1 : Find max element in data structure used say X_{max} and print (X_{max} + i - 1)

Task 2 : Find an iterator pointing to A_{n-i-1} . Erase this from the current data structure and insert (A_{n-i-1} - N) into the data structure used.

Here, we maintain an iterator which always points to (N-i-1)th element for i_{th} step. Instead of adding +1 to each element in each iteration, we just subtract N from the element being pointed out by the iterator. Since earlier in each step +1 is being added to every element, before printing max element we need to add number of iterations taken so far to get required maximum thatβs why we print (X_{max} + i - 1).

Therefore by changing data structure used for operations we get overall time complexity of O(nlog(n)) since insertion and deletion in multiset takes O(log(n)) time.

## Can we improve this time complexity of O(n(log(n)) any further ?

Yes. Initially increment A_i by i β i β [1,N]. Now maintain a maximum prefix array P where P can be calculated as

Pi = max(P_{i-1}, A_i) β i β [1,N]$

Initially P_n will contain the temporary maxima, therefore print it directly. Now we can use the same observations as used in above solutions to get to the required result. This time i will take values in following order [N, N-1, . . . 2] to get next N-1 solutions. The tasks in i_{th} operation looks like :

Task 1: Since we know in a right to left scan the maximumβs will decrease by N due to rotation of our B sequence. Therefore decrease P_i by N.

Task 2: P_i = max (P_i, P_{i+1}) + 1, this is to ensure that at ith iteration we still have overall maxima at P_i because it may happen that after performingTask 1, P_i < P_{i+1}

Task 3: P_{i-1} += cnt, increase value of P_{i-1} with number of iterations performed till now which is stored in cnt suppose. Since we know that maximum values to the left increases by 1 after every iteration (relate it to observation made in O(n^2) solution above). Therefore before moving forward we increases the max possible value to the left by cnt.

Task 4: Finally print max(P_i, P_{i-1}), P_i gives maximum from the right and P_{i-1} gives maximum from the left. Therefore max(P_i, P_{i-1}) gives the required maximum at ith iteration.

Since we are working on a single prefix array and time complexity of performing tasks in i_{th} iteration is O(1), therefore overall time complexity becomes O(N).

O(N^2) solution only yields 30 points **SUBTASK** **1**

O(Nlog(N)) and O(N) solutions yeilds full 100 points **SUBTASK** **2**

# TIME COMPLEXITY:

The best time complexity we obtained is O(N) .

# SOLUTIONS:

Solutions for every approach are provided to better understand the statements.

## Solution O(n^2) using Brute-Force

```
#include <bits/stdc++.h>
using namespace std;
#ifndef ONLINE_JUDGE
#include "debug.cpp"
#endif
#define int long long int
#define inf INT_MAX
#define mod 998244353
void f() {
int n; cin >> n;
vector<int> v(n);
for (int i = 0; i < n; i++) {
cin >> v[i];
v[i] += (i + 1);
}
int cnt = 0;
for (int i = 0; i < n; i++) {
int maxi = 0;
for (int j = 0; j < n; j++) {
maxi = max(maxi, v[j]);
v[j]++;
}
cout << maxi << " ";
v[n - i - 1] -= n;
}
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1;
while (t--) f();
}
```

## Solution O(nlog(n)) using Multiset

```
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define inf INT_MAX
#define mod 998244353
void f() {
int n; cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
multiset<int> sp;
for (int i = 0; i < n; i++) {
sp.insert(arr[i] + i + 1);
}
int cnt = 0;
for (int i = 0; i < n; i++) {
auto it = --sp.end();
cout << *it + cnt << " ";
sp.erase(sp.find(arr[n - i - 1] + n - i));
sp.insert(arr[n - i - 1] - i);
cnt++;
}
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1;
while (t--) f();
}
```

## Solution O(n) using Maximum Prefix

```
#include <bits/stdc++.h>
using namespace std;
#define int long long int
#define inf INT_MAX
#define mod 998244353
void f() {
int n; cin >> n ;
vector<int> arr(n + 2);
for (int i = 1; i <= n; i++)
cin >> arr[i] ;
for (int i = 1; i <= n; i++) {
arr[i] += i;
arr[i] = max(arr[i], arr[i - 1]) ;
}
cout << arr[n] << " " ;
int cnt = 0;
for (int i = n; i > 1; i--) {
arr[i] -= n ;
arr[i] = max(arr[i], arr[i + 1]) + 1 ;
cnt++;
arr[i - 1] += cnt ;
cout << max(arr[i], arr[i - 1]) << " " ;
}
cout << "\n" ;
}
int32_t main() {
ios::sync_with_stdio(0); cin.tie(0);
int t = 1;
while (t--) f();
}
```