Problem Overview

A pyramid consists of N levels numbered from top (level 1) to bottom (level N). Each level i contains exactly 2*i - 1 cells arranged in a centered row. The bottommost row (level N) holds a permutation of integers from 1 to 2*N - 1. Values in upper layers are derived by taking the median of three values directly beneath each cell: the one directly below, and its left and right diagonal neighbors.

Given the complete sequence of numbers at the base level, determine the single value that appears at the apex (topmost cell) of the pyramid.

Efficient Approach Using Binary Search

Direct simulation would require evaluating all levels upwards, leading to O(N²) complexity due to the triangular structure. Instead, we apply an optimized strategy based on binary search over possible values.

We perform a binary search on the range [1, 2*N - 1]. For each candidate value mid, we transform the problem into working with a boolean representation where:

• A cell is marked true if its value is greater than mid
• Otherwise it's marked false

This reduces the computation to analyzing patterns of true/false propagation through the pyramid levels.

Key insight: During upward propagation, when two adjacent cells have the same boolean state (true/true or false/false), their influence tends to dominate towards the center. Therefore, scanning outward from the central position of the base can help detect dominance quickly.

The algorithm proceeds as follows:

1. Initialize low = 1 and high = 2*N - 1 for binary search bounds
2. While low ≤ high:
   • Compute mid-point guess
   • Convert base array into boolean form relative to mid
   • Scan symmetrically outward from the middle index of the base
   • If a pair of identical booleans (both true or both false) is found first during scan:
     • Adjust search direction accordingly (left if dominated by falses, right otherwise)
   • Handle edge case where alternating pattern exists by checking the first element

#include <bits/stdc++.h>
using namespace std;

const int MAX_N = 100005;
int data[2 * MAX_N];
int size;

bool evaluate(int threshold) {
    int center = size;
    for (int offset = 0; offset < size; ++offset) {
        // Check left side pair
        if ((data[center - offset] > threshold) && (data[center - offset - 1] > threshold)) {
            return false; // Too large, move left
        }
        if ((data[center - offset] <= threshold) && (data[center - offset - 1] <= threshold)) {
            return true;  // Too small, move right
        }
        
        // Check right side pair
        if ((data[center + offset] > threshold) && (data[center + offset + 1] > threshold)) {
            return false;
        }
        if ((data[center + offset] <= threshold) && (data[center + offset + 1] <= threshold)) {
            return true;
        }
    }
    
    // Fallback: check parity of first element
    return (data[1] <= threshold);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    cin >> size;
    for (int idx = 1; idx <= 2*size - 1; ++idx) {
        cin >> data[idx];
    }
    
    int lower = 1;
    int upper = 2*size - 1;
    int result = upper;
    
    while (lower <= upper) {
        int pivot = (lower + upper) / 2;
        if (evaluate(pivot)) {
            result = pivot;
            upper = pivot - 1;
        } else {
            lower = pivot + 1;
        }
    }
    
    cout << result << "\n";
    return 0;
}

Time Complexity: O(N log N)