Sports Pairs
National Olympiad — Municipal round
Submission name: sport.cpp
Problem summary
Students are ordered by height and turn left (L) or right (R). Repeatedly remove adjacent students facing each other. Find the number remaining first in a line, then in a circle where the tallest and shortest are neighbours. The input lists students from tallest to shortest, which is right-to-left in the line.
Input
One string of L and R, starting with the tallest student.
Output
Two lines: survivors in the line; survivors in the circle.
Constraints
The number of students is less than 2^22.
Worked example
An independently prepared example for this explanation.
Input
LRRL
Output
2 0
Solution analysis
- In the input order, facing neighbours appear as LR, not RL. Match each R with an unmatched preceding L if possible.
- For the line, unmatched L and unmatched R are the survivors.
- In a circle any remaining opposite directions can meet across the boundary. The final count is the absolute difference between the original L and R counts.
Why it works
Line matching removes exactly the facing pairs exposed by previous deletions. A reduced line has all unmatched R before all unmatched L. Closing it into a circle repeatedly pairs these two ends until only one direction remains.
Watch out. Input order is reversed relative to ordinary left-to-right drawings; preserve this orientation.
Commented C++17 solution
An independently written complete program with standard headers.
// Key idea: Line matching removes exactly the facing pairs exposed by previous deletions. A reduced
// line has all unmatched R before all unmatched L.
#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<limits>
#include<numeric>
#include<set>
#include<map>
#include<tuple>
#include<cstdint>
#include<functional>
#include<cmath>
using namespace std;
int main(){
string s;
cin>>s;
int left=0,unmatchedR=0,totalL=0,totalR=0;
for(char c:s){
if(c=='L'){
left++;
totalL++;
}
else{
totalR++;
if(left){
left--;
}
else{
unmatchedR++;
}
}
}
cout<<left+unmatchedR<<'\n'<<abs(totalL-totalR)<<'\n';
}