Remove Nested Staircase Boards
National Olympiad — National round (2019 season)
Submission name: stairs.cpp
Problem summary
Boards join equal-height steps when all intermediate steps are lower, including adjacent equal steps. For q=1 count boards; for q=2 remove the fewest so no remaining board lies beneath another. Shared endpoints are allowed.
Input
N q and N heights.
Output
Board count for q=1, or minimum removals for q=2.
Constraints
4 ≤ N ≤ 100000; q is 1 or 2; heights 1…100.
Worked example
Input and output for the worked example discussed below.
Input
11 2 4 3 2 3 2 3 4 4 1 1 4
Output
2
Solution analysis
- Keep a decreasing stack of heights with their latest indices. Pop strictly smaller heights as a new step arrives. An equal top supplies precisely its visible equal-height predecessor and creates one board; replace that top’s index.
- Board intervals are nested or have disjoint interiors. Crossing different-height boards would put a forbidden higher step inside the lower board, while equal-height crossings have forbidden equal interior steps.
- Thus maximizing non-nested boards is interval scheduling. Boards appear in increasing right-endpoint order; keep one whenever its left endpoint is at least the last kept end. Minimum removals equal total minus kept.
- The sample has six boards. Keeping [2,4],[4,6],[7,8],[9,10] gives four compatible boards, so remove two.
Why it works
The stack finds exactly each legal predecessor; laminar intervals are non-nested exactly when interiors are disjoint, making earliest-finish greedy optimal.
Watch out. Pop strictly smaller heights, update an equal top after use, and allow boards to share endpoints.
Commented C++17 solution
An independently written complete program with standard headers.
// The stack finds exactly each legal predecessor; laminar intervals are non-nested exactly when interiors are
// disjoint, making earliest-finish greedy optimal.
#include<iostream>
#include<utility>
#include<vector>
using namespace std;
int main(){
int count,query;
cin>>count>>query;
vector<pair<int,int>>stack;
int boards=0;
int kept=0;
int lastEnd=-1;
for(int index=0;index<count;index++){
int height;
cin>>height;
while(!stack.empty()&&stack.back().first<height){
stack.pop_back();
}
if(!stack.empty()&&stack.back().first==height){
int left=stack.back().second;
boards++;
if(left>=lastEnd){
kept++;
lastEnd=index;
}
stack.back().second=index;
}
else{
stack.push_back({height,index});
}
}
cout<<(query==1?boards:boards-kept)<<'\n';
}