Proficient.
Put your skills to the test.

Problem summary

A hidden array has exactly one maximum-sum nonempty contiguous segment. You may only compare the sums of two nonempty segments through compare_segments. Implement find_max(N,left,right). Each oracle comparison costs the combined lengths of its two segments, so minimizing only the number of calls is insufficient.

Source clarification. This is a grader-linked comparison problem. The official O(N log N) divide-and-conquer method is explained at https://infos.infosbg.com/files/Contests/ETI/2018/B/analyses/B1_namuhs_analysis.pdf

Constraints

2 ≤ N ≤100000. The source does not give a numeric bound on hidden values; the solver itself performs no arithmetic on them.

Worked example

Original statement sample.

5
2 -3 5 -2 3

3 5

Solution analysis

1. Split the index interval into two halves. Return three descriptions for each half: its best prefix, best suffix, and best nonempty segment. Store endpoints rather than sums; only the grader knows the underlying values.
2. The merged best prefix is either the left half’s prefix or the whole left half followed by the right prefix. Compare those two contiguous intervals directly. The suffix is symmetric. The best segment is the best left segment, best right segment, or the left suffix joined to the right prefix. Four oracle calls combine the two children.
3. For2,−3,5,−2,3, a crossing candidate joining the suffix containing5 to the right contribution−2,3 gives sum6 at[3,5]. Compare it with the internal half-winners. Every recursion level compares intervals whose total lengths are O(N), so the grader’s linear-cost comparisons lead to O(N log N), not quadratic work.

Why it works

Every prefix either ends in the left half or contains all of that half and a right prefix. The suffix statement is symmetric. Every segment either lies wholly in one child or crosses the middle, in which case its two parts are a left suffix and right prefix. The four comparisons therefore preserve all three optimum descriptions by induction from one-element intervals.

Watch out. Official submission is grader-linked code without main and with #include "namuhs.h". The LOCAL branch is a runnable mock, not the original stdin submission format. Leave LOCAL undefined for the supplied grader. Do not compare empty segments or implement a linear-number-of-calls Kadane variant whose long comparisons can total O(N²).

Grader-ready implementation by default: it includes namuhs.h and exposes find_max without main. For the complete runnable local mock, compile with -DLOCAL or add #define LOCAL at the top. The mock reads the displayed sample and assumes compared sums fit long long; the actual solver never computes hidden sums.

#include<iostream>
#include<vector>
using namespace std;
#ifdef LOCAL
vector<long long>hiddenValues;
// Local stand-in for the supplied grader API; the solver never reads values.
bool compare_segments(int left1,int right1,int left2,int right2){
    long long first=0;
    long long second=0;
    for(int i=left1;i<=right1;++i){
        first+=hiddenValues[i];
    }
    for(int i=left2;i<=right2;++i){
        second+=hiddenValues[i];
    }
    return first>=second;
}
#else
#include"namuhs.h"
#endif
struct Result{
    int prefixEnd;
    int suffixStart;
    int bestLeft;
    int bestRight;
};
Result solve(int left,int right){
    if(left==right){
        return {left,left,left,left};
    }
    int middle=left+(right-left)/2;
    Result first=solve(left,middle);
    Result second=solve(middle+1,right);
    Result result;
    result.prefixEnd=
        compare_segments(left,first.prefixEnd,left,second.prefixEnd)?first.prefixEnd:second.prefixEnd;
    result.suffixStart=compare_segments(first.suffixStart,right,second.suffixStart,right)
        ?first.suffixStart
        :second.suffixStart;
    result.bestLeft=first.bestLeft;
    result.bestRight=first.bestRight;
    if(compare_segments(second.bestLeft,second.bestRight,result.bestLeft,result.bestRight)){
        result.bestLeft=second.bestLeft;
        result.bestRight=second.bestRight;
    }
    if(compare_segments(first.suffixStart,second.prefixEnd,result.bestLeft,result.bestRight)){
        result.bestLeft=first.suffixStart;
        result.bestRight=second.prefixEnd;
    }
    return result;
}
void find_max(int n,int&left,int&right){
    Result result=solve(1,n);
    left=result.bestLeft;
    right=result.bestRight;
}
#ifdef LOCAL
int main(){
    int n;
    cin>>n;
    hiddenValues.resize(n+1);
    for(int i=1;i<=n;++i){
        cin>>hiddenValues[i];
    }
    int left,right;
    find_max(n,left,right);
    cout<<left<<' '<<right<<'\n';
}
#endif