Hi!
I was trying table sum question of INOI and I have been partially accepted
Here is my solution
#include
using namespace std;
int main() {
long long t,k;
scanf("%lld",&t);
long long a[t],add[t],sum[t];
for(long long i=0;i<t;i++)
scanf("%lld",&a[i]);
for(long long i=0;i<t;i++){
k=0;
for(long long j=i;j<t;j++){
add[k] = a[k] + j+1;
k++;
}
for(long long j=0;j<i;j++){
add[k] = a[k] + j+1;
k++;
}
sum[i] = *max_element(add,add+t);
}
for(long long i=0;i<t;i++){
printf("%lld ",sum[i]);
}
return 0;
}
Can anyone explain me how can I optimize my time in this question.
you are storing the value of answer in an array. You know more arrays means more memory and more memory means more time. But in the following code you can see in every test case it prints the answer before storing the next test case.
The most important you have used 3 “for” loops but my code has only one “for” loop. So your code’s time ia almost 3 times of my code’s time.
And I am using “std::max_element” which improves execution time.
I hope this helped you.
#include <iostream>
#include <vector>
#include <algorithm>
int main(){
int n;
std::cin >> n;
std::vector<int>nums(n);
for(int i=0;i<n;i++){
std::cin >> nums[i];
}
int max = 0;
for(int i=0;i<n;i++){
nums[i] += i+1;
if(nums[i] > max){
max = nums[i];
}
}
std::cout << max << " ";
int count = 1;
for(int i = n-1;i>0;i--){
nums[i] -= n;
std::cout << *std::max_element(nums.begin(),nums.end())+count << " ";
count++;
}
std::cout << std::endl;
return 0;
@only4 the complexity of this code is the same as the one provided by @olympiadcrack, which is O(n^2). You use one loop but you are using std::max_element which is O(n) itself. Please don’t confidently give wrong answers.
You are using the straightforward approach, which has complexity \mathcal{O}(n^2) because you are calculating the answer for all n rotations going over n elements for each. The problem can be solved in \mathcal{O}(n) with some clever thinking that will fetch you 100 points. However it requires a different approach from your current way of tackling it. Give it some thought. If you are still unable to solve it I will be happy to explain the solution
EDIT:
Assume the first row is 72314 (no particular significance). Let’s divide a rotation of the sequence 1234…n into 2 pieces, [start value to n] and [1 to end value]. When n=5, all rotations are shown below with | symbolizing the split between the pieces. . [7 2 3 1 4] 1 2 3 4 5 8 4 6 5 9 2 3 4 5| 1 9 5 7 6| 5 3 4 5| 1 2 10 6 8| 2 6 4 5| 1 2 3 11 7| 4 3 7 5| 1 2 3 4 12| 3 5 4 8
Now you can observe observe that each value before the split in the r^{th} rotation is just (r+the value at that index in the 0^{th} rotation). And each value after the split in any rotation is (r-N+the value at that index in the 0^{th} rotation). Let {max}_r(i, j) denote the maximum element from indices i to j in the r^{th} rotation. Then it is follows that {max}_r(0, i) equals r+{max}_0(0, i) for i<N-r. This condition refers to all values of i before the split. And {max}_r(j, N-1) equals r-N+{max}_0(j, N-1) for all j≥N-r. As you can guess, this is for all values after the split. You can verify these properties using the above example.
For each rotation r, we need to find the maximum value before the split, and the maximum value after the split, which are {max}_r(0, N-r-1) and {max}_r(N-r, N-1) respectively. The greater of these two is the overall answer for the rotation. From what we deduced earlier, {max}_r(0, N-r-1) = r+{max}_0(0, N-r-1) and {max}_r(N-r, N-1) = r-N+{max}_0(N-r, N-1). So can we get values like {max}_0(0, i) and {max}_0(j, N-1) in constant time? Yes we can, using prefix and suffix maximum arrays. Each of these can be calculated beforehand in \mathcal{O}(n).
Complexity is \mathcal{O}(n)
Pseudocode here.
AC submission here.
