Smallest Balanced Kingdom Expansion
National Olympiad — Regional round (2009 season)
Submission name: king.cpp
Problem summary
Expand a kingdom a positive integer distance west and east. Given nondecreasing production values for each distance, minimize the total distance yielding equal cheese and bread production.
Input
An odd N, then(N−1)/2 western production values and the same number of eastern values.
Output
The least total distance, or0 if no equal production is possible.
Constraints
N is positive, odd, and below1000; production lists are positive nondecreasing integers at most1000000.
Worked example
Input and output for the worked example discussed below.
Input
13 2 3 6 7 7 9 1 4 5 6 9 11
Output
7
Solution analysis
- Each list index plus1 is the corresponding expansion distance. We need an equal value from the two sorted lists with the smallest index sum.
- Keep one pointer per list. If one value is smaller, advance only that pointer: it cannot match the other current value or any later value. The first equality uses the earliest possible common value and its earliest indices.
- In the sample, cheese value6 first occurs at western distance3 and bread value6 at eastern distance4. Their total is7. The later common value9 requires distances6 and5, which cannot improve the total.
Why it works
Discarding a smaller current value cannot lose a match with the other list’s current or later values. At the first equality, no earlier common pair was possible; all later pairs have no smaller index in either list, so none has a smaller index sum.
Watch out. Lists are cumulative production by distance, not individual land yields. Do not sum their entries. Preserve first occurrences of duplicates and output0 only when no match exists.
Commented C++17 solution
An independently written complete program with standard headers.
#include<iostream>
#include<vector>
using namespace std;
int main(){
int n;
cin>>n;
int length=(n-1)/2;
vector<int>west(length);
vector<int>east(length);
for(int&value:west){
cin>>value;
}
for(int&value:east){
cin>>value;
}
int first=0;
int second=0;
while(first<length&&second<length){
// A smaller current value cannot match the other sorted suffix.
if(west[first]<east[second]){
first++;
}
else if(east[second]<west[first]){
second++;
}
else{
cout<<first+second+2<<'\n';
return 0;
}
}
cout<<0<<'\n';
}