Solution of Red Dragon

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 v_P + v_Q - floor(log₂(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 * log₂ 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 * log₂² 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 }