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 performing Task 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();
}