Proficient.
Put your skills to the test.

Problem summary

A length-K code list is formed recursively: prefix each given digit to the preceding list, reversing that list for odd zero-based digit positions. Digits may repeat. For indices A…B, find the largest code number and the greatest absolute difference between digit sums of neighboring codes.

Constraints

1 ≤ N ≤ 100; 1 ≤ K ≤ 10,000; 1 ≤ A < B ≤ min(10¹⁸,Nᴷ), implying N≥2.

Worked example

An independently prepared example for this explanation.

3 2 3 5
7 1 5

75 6

Solution analysis

1. A recursive list consists of N equal blocks, one for each prefix digit. Odd-numbered blocks reverse their suffix list. For an interval, recurse only into its two partial boundary blocks; every fully covered block can be summarized immediately.
2. A summary stores the lexicographically maximum fixed-length code, first and last digit sums, and the largest neighboring difference. Combining consecutive blocks takes the maximum of their internal differences and the difference between the former last sum and latter first sum. A full depth-d list has maximum digit repeated d times. Its largest internal difference is the largest difference between adjacent input digits, since reflected traversal changes only one digit at a time.
3. Cap powers Nᵈ at 10¹⁸+1. Whenever the first block is already longer than B, the entire interval has the first digit as a fixed prefix; remove these leading levels iteratively. At most sixty levels then remain. For 7,1,5 with K=2 and indices 3…5, the selected codes are 75,15,11, yielding maximum 75 and difference 6.

Why it works

Induction on depth gives the recursive block order. Mirroring interval endpoints correctly converts a reversed child into its forward interval; reversing its summary swaps first and last sums while preserving the maximum and internal difference. Full-block summaries follow from the reflected list’s single-coordinate transitions and attainable all-maximum-digit code. Concatenation considers every internal adjacent pair and exactly each inter-block boundary pair, while fixed-length lexicographic comparison equals numeric order. Thus the combined summary answers both questions exactly.

Watch out. Reverse by input position parity, not digit value. Keep code strings to avoid overflow. The maximum number is printed without redundant leading zeroes. Saturate powers instead of overflowing 64-bit arithmetic.

An independently written complete program with standard headers.

#include<algorithm>
#include<cstdlib>
#include<iostream>
#include<numeric>
#include<string>
#include<vector>
// Algorithm: A recursive list consists of N equal blocks, one for each prefix digit.
using namespace std;
struct Summary{
    string maximum;
    int first=0,last=0,difference=0;
    bool empty=true;
};
vector<int>digits,firstSum,lastSum;
vector<unsigned long long>powerSize;
int greatestDigit,greatestDifference;
Summary interval(int depth,unsigned long long left,unsigned long long right){
    if(left==0&&right+1==powerSize[depth]){
        return {string(depth,static_cast<char>('0'+greatestDigit)),firstSum[depth],lastSum[depth],
            depth?greatestDifference:0,false};
    }
    Summary result;
    unsigned long long block=powerSize[depth-1];
    int firstBlock=static_cast<int>(left/block);
    int lastBlock=static_cast<int>(right/block);
    for(int i=firstBlock;i<=lastBlock;i++){
        unsigned long long begin=i==firstBlock?left%block:0;
        unsigned long long end=i==lastBlock?right%block:block-1;
        if(i%2){
            unsigned long long saved=begin;
            begin=block-1-end;
            end=block-1-saved;
        }
        Summary child=interval(depth-1,begin,end);
        if(i%2){
            swap(child.first,child.last);
        }
        child.maximum.insert(child.maximum.begin(),static_cast<char>('0'+digits[i]));
        child.first+=digits[i];
        child.last+=digits[i];
        if(result.empty){
            result=child;
        }
        else{
            result.maximum=max(result.maximum,child.maximum);
            result.difference=max({result.difference,child.difference,abs(result.last-child.first)});
            result.last=child.last;
        }
    }
    return result;
}
int main(){
    int n,k;
    unsigned long long a,b;
    cin>>n>>k>>a>>b;
    digits.resize(n);
    for(int&digit:digits){
        cin>>digit;
    }
    greatestDigit=*max_element(digits.begin(),digits.end());
    greatestDifference=0;
    for(int i=1;i<n;i++){
        greatestDifference=max(greatestDifference,abs(digits[i]-digits[i-1]));
    }
    const unsigned long long cap=1000000000000000001ULL;
    powerSize.assign(k+1,1);
    firstSum.assign(k+1,0);
    lastSum.assign(k+1,0);
    for(int depth=1;depth<=k;depth++){
        powerSize[depth]=powerSize[depth-1]>cap/n?cap:min(cap,powerSize[depth-1]*n);
        firstSum[depth]=digits[0]+firstSum[depth-1];
        lastSum[depth]=digits.back()+(n%2?lastSum[depth-1]:firstSum[depth-1]);
    }
    int depth=k;
    string prefix;
    while(depth>0&&powerSize[depth-1]>=b){
        prefix+=static_cast<char>('0'+digits[0]);
        depth--;
    }
    Summary result=interval(depth,a-1,b-1);
    string maximum=prefix+result.maximum;
    size_t nonzero=maximum.find_first_not_of('0');
    cout<<(nonzero==string::npos?"0":maximum.substr(nonzero))<<' '<<result.difference<<'\n';
}