Reconstruct the Painted Fence
National Olympiad — National round (2023 season)
Submission name: painting.cpp
Problem summary
A fence starts with color 0. Each move uses a new positive color on one consecutive interval; at least one board of every used color must remain visible forever. Given a reachable final coloring, find the number of colors, minimum liters of paint (one per painted board), and one optimal sequence of moves.
Source clarification. The PDF’s second sample declares N=10 but prints 12 colors and describes moves for only the first 10; it is inconsistent. The first sample is reproduced here. Output uses uppercase MOVE as required by the prose, although the sample uses Move.
Input
N, then N final colors.
Output
First print the number of used positive colors and minimum paint. Then print each move as MOVE t: color left right, using one-based inclusive board positions.
Constraints
1 ≤ N ≤ 100000; colors are in [0,1000000]. The described process produced the final fence.
Worked example
An independently prepared example for this explanation.
Input
6 3 3 3 3 2 2
Output
2 6 MOVE 1: 3 1 4 MOVE 2: 2 5 6
Solution analysis
- A color is used once, so its move must include both its first and last final occurrences. Its necessary interval is therefore [first[color],last[color]], and that interval length is a lower bound on paint for the color.
- Reachability implies that these intervals are disjoint or nested. Crossing intervals could not preserve both colors at their required endpoints. A zero board cannot lie inside any positive interval, because zero is never painted back.
- Paint each positive color exactly on its necessary interval, in order of first appearance. Outer intervals start earlier and are painted before inner ones, which restore the colors covering their middle. In the sample, intervals [1,4] and [5,6] are disjoint, so two moves consume 4+2=6 liters.
Why it works
Every valid solution pays at least the sum of necessary interval lengths. The nesting property ensures that first-appearance order paints ancestors before descendants; for each board, its final color is the innermost interval containing it. Thus the construction reaches the target and attains the lower bound.
Watch out. Ignore color 0 when counting moves and paint. Positions in the output are one-based. Store the paint total in long long.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n;
cin >> n;
const int colorLimit = 1000001;
vector<int> first(colorLimit, 0), last(colorLimit, 0), order;
for (int position = 1; position <= n; position++) {
int color;
cin >> color;
if (color == 0) {
continue;
}
if (first[color] == 0) {
first[color] = position;
order.push_back(color);
}
last[color] = position;
}
long long paint = 0;
for (int color : order) {
paint += last[color] - first[color] + 1;
}
cout << order.size() << ' ' << paint << '\n';
// First appearances order enclosing intervals before their nested intervals.
for (int move = 0; move < static_cast<int>(order.size()); move++) {
int color = order[move];
cout << "MOVE " << move + 1 << ": " << color << ' ' << first[color] << ' ' << last[color] << '\n';
}
}