The year is 2022. Red Dragon - the latest spacecraft launched by SpaceX - is already on its way towards Mars. Its main objective is collecting and analyzing Martian soil.
The surface of Mars is seen as a linear array of N consecutive coordinates. Each coordinate i (1 ≤ i ≤ N) has associated some integer value vi describing how interesting that portion of soil appears to be, according to engineers' estimates.
The mission description is, as follows:
- Instead of landing, the capsule hovers at a safe distance.
- Two rovers are launched from it. Each of them lands at some coordinate on the planet, denoted by r1 and r2, respectively.
- Each rover collects information about the piece of soil underneath it. The total value gained is equal to vr1 + vr2.
- Afterwards, the rovers need to meet in order to share and send back their pieces of information. The value lost through fuel consumption is equal to floor(log2 (r2 - r1)).
Your goal is to choose where to place the rovers such that the mission is as successful as possible. Formally, you need to maximize the expression vr1 + vr2 - floor(log2 (r2 - r1)).
Input
The first line of input contains a single integer N.
The second line of input contains N integer values: v1, v2, …, vN.
Output
A single integer: the maximum value of the given expression.
Restrictions
- 1 < N ≤ 105
- -230 ≤ vi ≤ 230
- r1 < r2
Sample
| Input | Output |
|---|---|
| 5 5 6 -9 1 10 | 15 |
The solution to this problem comes with a few key observations:
- The value of the logarithm factor will never exceed log N, since all valid indices belong to the interval [1, N].
- For a fixed starting index P, the next indices (P+1, P+2, …, N) can be split into groups, each having a specific value for the logarithm factor. So, in order to maximize the value vP + vQ - floor(log2(Q - P)), one must take the maximum value among all the groups.
Based on the implementation, time and space complexity may differ. We will provide two different implementations:
Cosmin Rusu: O(N * log2 N)
This solution has the best time complexity among all the solutions and it uses the RMQ data structure.
1 #include <iostream> 2 #include <string.h> 3 #include <fstream> 4 5 using namespace std; 6 7 const int maxn = 100005; 8 const int maxlg = 18; 9 10 int rmq[maxlg][maxn * 10]; 11 12 int main() { 13 int n; 14 cin >> n; 15 memset(rmq, -0x3f3f3f3f, sizeof(rmq)); 16 for(int i = 1 ; i <= n ; ++ i) 17 cin >> rmq[0][i]; 18 19 for(int i = 1 ; i < maxlg ;++ i) 20 for(int j = 1 ; j <= n ; ++ j) { 21 rmq[i][j] = max(rmq[i - 1][j], rmq[i - 1][j + (1 << (i - 1))]); 22 } 23 24 long long ans = -0x3f3f3f3f; 25 for(int i = 1 ; i < n ; ++ i) { 26 for(int lg = 0 ; lg < maxlg ; ++ lg) { 27 int st = i + (1 << lg); 28 ans = max(ans, 1LL * rmq[0][i] + rmq[lg][st] - lg); 29 } 30 } 31 cout << ans << '\n'; 32 }
Petru Trîmbiţaş: O(N * log22 N)
Here's the simplest way to do this:
1 #include <iostream> 2 #include <set> 3 #include <cstdio> 4 #define DN 100005 5 using namespace std; 6 7 typedef pair<int,int> per; 8 int n,v[DN],rez=-(1<<30); 9 set<per, greater<per> > s[20]; 10 11 int main() { 12 //freopen("1000.in","r",stdin); 13 cin>>n; 14 for(int i=0; i<n; ++i) cin>>v[i]; 15 for(int i=1; i<n; ++i) { 16 for(int j=1,ind=1; i-j>=0; j<<=1,++ind) { 17 if(s[ind-1].find(make_pair(v[i-j],i-j))!=s[ind-1].end()) s[ind-1].erase(s[ind-1].find(make_pair(v[i-j],i-j))); 18 s[ind].insert(make_pair(v[i-j],i-j)); 19 } 20 for(int j=0; j<20; ++j) if(s[j].size()) rez=max(rez,v[i]+s[j].begin()->first-(j-1)); 21 } 22 cout<<rez; 23 }
