A Third Garden Bed
National Olympiad — National round (2014 season)
Submission name: garden.cpp
Problem summary
Two garden beds contain bushes of distinct heights within each bed. Move one bush of every height appearing in both beds to a third bed. Print these common heights in increasing order. The third bed is nonempty.
Input
k n, followed by k decimal heights and then n decimal heights.
Output
Common heights in increasing order, separated by spaces without a trailing space.
Constraints
2 < k, n < 100; heights do not exceed 3000 cm; decimal precision is not specified.
Worked example
An independently prepared example for this explanation.
Input
4 5 5 4.3 9 2.5 9 4.3 1 6.4 7
Output
4.3 9
Solution analysis
- We need the intersection of two collections of heights. Sort both lists so that each common height can be located by a pair of forward-moving indices.
- If the current heights are equal, output that height and advance both indices. If one is smaller, advance only that index: that smaller value cannot equal any later value of the other sorted list.
- The example lists become [2.5, 4.3, 5, 9] and [1, 4.3, 6.4, 7, 9]. The two equal encounters are 4.3 and 9, already in the required increasing order.
Why it works
At each step, every discarded smaller value is too small to match any unprocessed value on the other side. Every equality is therefore a common height and no common height is skipped. Sorted traversal outputs exactly the intersection in increasing order.
Watch out. Do not concatenate the lists: only common heights belong in the result. Decimal inputs are compared as parsed long double values; identical numeric decimal values parse equally.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
#include <algorithm>
#include <iomanip>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int k, n;
cin >> k >> n;
vector<long double> a(k), b(n);
for (auto &height : a) {
cin >> height;
}
for (auto &height : b) {
cin >> height;
}
sort(a.begin(), a.end());
sort(b.begin(), b.end());
int i = 0;
int j = 0;
bool first = true;
cout << setprecision(18);
// The smaller current height cannot match a later value on the other side.
while (i < k && j < n) {
if (a[i] == b[j]) {
if (!first) {
cout << ' ';
}
cout << a[i];
first = false;
++i;
++j;
} else if (a[i] < b[j]) {
++i;
} else {
++j;
}
}
cout << '\n';
return 0;
}