Festival Decoration
Feasibility Condition A valid arrangement exists if and only if _i c_i n 2. Necessity. In any valid arrangement of n elements, a single color can occupy at most every other position, i.e., at most n/2 positions. Suffi...
Problem Statement
Rendered from the "Problem Statement" section in the LaTeX write-up.
Given $k$ colors with counts $c_1, c_2, \ldots, c_k$ (totaling $n = c_1 + c_2 + \cdots + c_k$ balls), arrange all $n$ balls in a line such that no two adjacent balls share the same color. Output one valid arrangement, or report that none exists.
Editorial
The solution write-up is rendered from the LaTeX source, with equations kept live through MathJax.
Solution
Feasibility Condition
Theorem.
A valid arrangement exists if and only if \[ \max_i\, c_i \le \left\lceil \frac{n}{2} \right\rceil. \]
Proof.
Necessity. In any valid arrangement of $n$ elements, a single color can occupy at most every other position, i.e., at most $\lceil n/2 \rceil$ positions.
Sufficiency. The greedy algorithm below always produces a valid arrangement when this condition holds, as shown in the correctness argument that follows.
Greedy Algorithm
Maintain a max-heap of $(\text{count}, \text{color})$ pairs:
Extract the color with the highest remaining count.
If it differs from the previously placed color, place it.
Otherwise, extract the second-highest color, place it, and push the first color back.
Repeat until all balls are placed.
Lemma (Correctness).
If $\max_i\, c_i \le \lceil n/2 \rceil$, the greedy algorithm never gets stuck.
Proof.
The algorithm gets stuck only when the heap contains a single color that matches the last placed color. At that point, the remaining count of that color must be at least 1 while the total remaining is also that count. But this means $c_{\max} > \lceil n'/2 \rceil$ for the remaining $n'$ items, which contradicts the invariant maintained by always placing the most frequent available color first.
Complexity Analysis
Time: $O(n \log k)$. Each of the $n$ placement steps involves at most two heap operations, each costing $O(\log k)$.
Space: $O(k)$ for the heap.
Example
Input: 3 colors with counts $[3, 2, 1]$, total $n = 6$.
Since $\max(c_i) = 3 = \lceil 6/2 \rceil$, a valid arrangement exists.
Greedy execution:
Heap: $\{(3,\mathrm{A}),\, (2,\mathrm{B}),\, (1,\mathrm{C})\}$. Place
A. Remaining: $[2,2,1]$.Top is $\mathrm{A}$ again (tied with $\mathrm{B}$); last was $\mathrm{A}$, so take $\mathrm{B}$. Place
B. Remaining: $[2,1,1]$.Place
A. Remaining: $[1,1,1]$.Place
B. Remaining: $[1,0,1]$.Place
A. Remaining: $[0,0,1]$.Place
C. Done.Result:
ABABAC.
Code
C++ solution used for this page.
// IOI 1990 - Problem 3: Festival Decoration
// Arrange colored balls so no two adjacent balls share the same color.
// Greedy with max-heap: always place the most frequent available color.
#include <bits/stdc++.h>
using namespace std;
int main() {
int k;
scanf("%d", &k);
priority_queue<pair<int,int>> pq;
int total = 0;
for (int i = 0; i < k; i++) {
int c;
scanf("%d", &c);
if (c > 0) {
pq.push({c, i});
total += c;
}
}
if (pq.empty()) { printf("\n"); return 0; }
// Check feasibility: max count must be <= ceil(total/2)
if (pq.top().first > (total + 1) / 2) {
printf("IMPOSSIBLE\n");
return 0;
}
string result;
result.reserve(total);
int lastColor = -1;
while (!pq.empty()) {
auto [cnt1, col1] = pq.top();
pq.pop();
if (col1 != lastColor) {
result += (char)('A' + col1);
lastColor = col1;
if (cnt1 > 1) pq.push({cnt1 - 1, col1});
} else {
if (pq.empty()) {
printf("IMPOSSIBLE\n");
return 0;
}
auto [cnt2, col2] = pq.top();
pq.pop();
result += (char)('A' + col2);
lastColor = col2;
pq.push({cnt1, col1});
if (cnt2 > 1) pq.push({cnt2 - 1, col2});
}
}
printf("%s\n", result.c_str());
return 0;
}
Source Files and Assets
Raw files are still available here when you want the original TeX, C++, or statement assets.