IOI 2014 - Holiday
There are n cities on a line, each with a number of attractions a_i. You start at city S (0-indexed) and have D days. Each day you either move to an adjacent city or visit the current city (collecting its attractions,...
IOI2014TeXC++
Source of truth
Source-first archive entry
This page is built from the copied files in competitive_programming/ioi/2014/holiday. Edit
competitive_programming/ioi/2014/holiday/solution.tex to update the written solution and
competitive_programming/ioi/2014/holiday/solution.cpp to update the implementation.
The website does not replace those files with hand-maintained HTML. It reads the copied source tree during the build and exposes the exact files below.
Problem statement
Problem Statement
Rendered from the "Problem Summary" section inside solution.tex because this entry has no separate statement file.
There are $n$ cities on a line, each with a number of attractions $a_i$. You start at city $S$ (0-indexed) and have $D$ days. Each day you either move to an adjacent city or visit the current city (collecting its attractions, at most once per city). Maximise the total attractions collected.
Editorial
Editorial
Rendered from the copied solution.tex file. The original TeX source remains
available below.
Solution
Structure of Optimal Solutions
Lemma.
An optimal strategy visits a contiguous range $[l, r]$ containing $S$. Within that range, it collects the cities with the largest attraction values.
The travel cost to visit range $[l, r]$ ($l \le S \le r$) is:
Left first: $2(S - l) + (r - S)$.
Right first: $(S - l) + 2(r - S)$.
The remaining $D - \text{cost}$ days are used to visit cities, so we collect the top $\min(D - \text{cost},\, r - l + 1)$ attraction values in $[l, r]$.
Divide and Conquer with Segment Tree
Fix the direction (left-first or right-first). For a fixed left endpoint $l$, let $r^*(l)$ be the optimal right endpoint.
Lemma (Monotonicity).
$r^*(l)$ is non-decreasing as $l$ increases, enabling divide-and-conquer optimisation.
We use D&C on $l$: for the midpoint $l_{\text{mid}}$, sweep $r$ to find $r^*(l_{\text{mid}})$, then recurse on the two halves. A segment tree on coordinate-compressed attraction values supports:
$\texttt{add}(v)$: insert value $v$.
$\texttt{rem}(v)$: remove value $v$.
$\texttt{topk}(k)$: sum of the $k$ largest inserted values.
We maintain the segment tree incrementally as we expand or shrink the window $[l, r]$.
C++ Implementation
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct SegTree {
int n;
vector<int> cnt;
vector<ll> sum;
void init(int _n) {
n = _n;
cnt.assign(4 * n, 0);
sum.assign(4 * n, 0);
}
void update(int node, int l, int r, int pos, int val, ll w) {
if (l == r) { cnt[node] += val; sum[node] += w; return; }
int mid = (l + r) / 2;
if (pos <= mid) update(2*node, l, mid, pos, val, w);
else update(2*node+1, mid+1, r, pos, val, w);
cnt[node] = cnt[2*node] + cnt[2*node+1];
sum[node] = sum[2*node] + sum[2*node+1];
}
ll query(int node, int l, int r, int k) {
if (k <= 0) return 0;
if (k >= cnt[node]) return sum[node];
if (l == r) return (ll)k * (sum[node] / cnt[node]);
int mid = (l + r) / 2;
if (cnt[2*node+1] >= k)
return query(2*node+1, mid+1, r, k);
return sum[2*node+1] + query(2*node, l, mid, k - cnt[2*node+1]);
}
void add(int pos, ll w) { update(1, 0, n-1, pos, 1, w); }
void rem(int pos, ll w) { update(1, 0, n-1, pos, -1, -w); }
ll topk(int k) { return query(1, 0, n-1, k); }
};
int N, S, D;
vector<int> a;
vector<int> sorted_vals;
SegTree seg;
ll best_ans;
int compress(int v) {
return lower_bound(sorted_vals.begin(), sorted_vals.end(), v)
- sorted_vals.begin();
}
int cur_l, cur_r;
void addCity(int i) { seg.add(compress(a[i]), a[i]); }
void remCity(int i) { seg.rem(compress(a[i]), a[i]); }
void expand_to(int l, int r) {
while (cur_r < r) { cur_r++; addCity(cur_r); }
while (cur_l > l) { cur_l--; addCity(cur_l); }
while (cur_r > r) { remCity(cur_r); cur_r--; }
while (cur_l < l) { remCity(cur_l); cur_l++; }
}
void solve(int lo_l, int hi_l, int lo_r, int hi_r, bool leftFirst) {
if (lo_l > hi_l) return;
int mid_l = (lo_l + hi_l) / 2;
int best_r = lo_r;
ll best_val = -1;
for (int r = max(lo_r, S); r <= min(hi_r, N - 1); r++) {
int l = mid_l;
int cost = leftFirst ? 2 * (S - l) + (r - S)
: (S - l) + 2 * (r - S);
int visit = D - cost;
if (visit <= 0) continue;
visit = min(visit, r - l + 1);
expand_to(l, r);
ll val = seg.topk(visit);
if (val > best_val) { best_val = val; best_r = r; }
}
best_ans = max(best_ans, best_val);
solve(lo_l, mid_l - 1, lo_r, best_r, leftFirst);
solve(mid_l + 1, hi_l, best_r, hi_r, leftFirst);
}
long long findMaxAttraction(int n, int start, int d, int attraction[]) {
N = n; S = start; D = d;
a.assign(attraction, attraction + n);
sorted_vals = a;
sort(sorted_vals.begin(), sorted_vals.end());
sorted_vals.erase(unique(sorted_vals.begin(), sorted_vals.end()),
sorted_vals.end());
best_ans = 0;
seg.init(sorted_vals.size());
cur_l = S; cur_r = S - 1;
solve(0, S, S, N - 1, true);
seg.init(sorted_vals.size());
cur_l = S; cur_r = S - 1;
solve(0, S, S, N - 1, false);
return best_ans;
}Complexity Analysis
Time: $O(n \log^2 n)$. The D&C has $O(\log n)$ levels; at each level, the total sweep across all subproblems is $O(n)$, with each step requiring an $O(\log n)$ segment-tree operation.
Space: $O(n)$.
Source code
Code
Exact copied C++ implementation from solution.cpp.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// Segment tree on values (by coordinate-compressed index)
// Supports: insert, erase, query top-k sum
struct SegTree {
int n;
vector<int> cnt;
vector<ll> sum;
void init(int _n) {
n = _n;
cnt.assign(4 * n, 0);
sum.assign(4 * n, 0);
}
void update(int node, int l, int r, int pos, int val, ll w) {
if (l == r) {
cnt[node] += val;
sum[node] += w;
return;
}
int mid = (l + r) / 2;
if (pos <= mid) update(2*node, l, mid, pos, val, w);
else update(2*node+1, mid+1, r, pos, val, w);
cnt[node] = cnt[2*node] + cnt[2*node+1];
sum[node] = sum[2*node] + sum[2*node+1];
}
// Sum of top-k elements
ll query(int node, int l, int r, int k) {
if (k <= 0) return 0;
if (k >= cnt[node]) return sum[node];
if (l == r) return (ll)k * (sum[node] / cnt[node]);
int mid = (l + r) / 2;
if (cnt[2*node+1] >= k)
return query(2*node+1, mid+1, r, k);
else
return sum[2*node+1] + query(2*node, l, mid, k - cnt[2*node+1]);
}
void add(int pos, ll w) { update(1, 0, n-1, pos, 1, w); }
void rem(int pos, ll w) { update(1, 0, n-1, pos, -1, -w); }
ll topk(int k) { return query(1, 0, n-1, k); }
};
int N, S, D;
vector<int> a;
vector<int> sorted_vals;
SegTree seg;
ll best_ans;
int compress(int v) {
return lower_bound(sorted_vals.begin(), sorted_vals.end(), v) - sorted_vals.begin();
}
int cur_l, cur_r; // current window in seg tree
void addCity(int i) { seg.add(compress(a[i]), a[i]); }
void remCity(int i) { seg.rem(compress(a[i]), a[i]); }
void expand_to(int l, int r) {
while (cur_r < r) { cur_r++; addCity(cur_r); }
while (cur_l > l) { cur_l--; addCity(cur_l); }
while (cur_r > r) { remCity(cur_r); cur_r--; }
while (cur_l < l) { remCity(cur_l); cur_l++; }
}
// left-first: cost = 2*(S-l) + (r-S), visit = D - cost
// right-first: cost = (S-l) + 2*(r-S), visit = D - cost
void solve(int lo_l, int hi_l, int lo_r, int hi_r, bool leftFirst) {
if (lo_l > hi_l) return;
int mid_l = (lo_l + hi_l) / 2;
int best_r = lo_r;
ll best_val = -1;
int rmin = max(lo_r, S);
int rmax = min(hi_r, N - 1);
for (int r = rmin; r <= rmax; r++) {
int l = mid_l;
int cost;
if (leftFirst) cost = 2 * (S - l) + (r - S);
else cost = (S - l) + 2 * (r - S);
int visit = D - cost;
if (visit <= 0) continue;
visit = min(visit, r - l + 1);
expand_to(l, r);
ll val = seg.topk(visit);
if (val > best_val) {
best_val = val;
best_r = r;
}
}
best_ans = max(best_ans, best_val);
solve(lo_l, mid_l - 1, lo_r, best_r, leftFirst);
solve(mid_l + 1, hi_l, best_r, hi_r, leftFirst);
}
long long findMaxAttraction(int n, int start, int d, int attraction[]) {
N = n; S = start; D = d;
a.assign(attraction, attraction + n);
sorted_vals = a;
sort(sorted_vals.begin(), sorted_vals.end());
sorted_vals.erase(unique(sorted_vals.begin(), sorted_vals.end()), sorted_vals.end());
best_ans = 0;
// Left-first: l in [0, S], r in [S, N-1]
seg.init(sorted_vals.size());
cur_l = S; cur_r = S - 1;
solve(0, S, S, N - 1, true);
// Right-first: l in [0, S], r in [S, N-1]
seg.init(sorted_vals.size());
cur_l = S; cur_r = S - 1;
solve(0, S, S, N - 1, false);
return best_ans;
}
int main() {
int n, s, d;
scanf("%d %d %d", &n, &s, &d);
int attr[n];
for (int i = 0; i < n; i++) scanf("%d", &attr[i]);
printf("%lld\n", findMaxAttraction(n, s, d, attr));
return 0;
}
Source files
Source Files
Exact copied source-of-truth files. Edit solution.tex for the write-up and solution.cpp for the implementation.
\documentclass[11pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{hyperref}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\lstset{
language=C++,
basicstyle=\ttfamily\small,
keywordstyle=\color{blue}\bfseries,
commentstyle=\color{gray},
stringstyle=\color{red},
numbers=left,
numberstyle=\tiny\color{gray},
breaklines=true,
frame=single,
tabsize=4,
showstringspaces=false
}
\title{IOI 2014 -- Holiday}
\author{}
\date{}
\begin{document}
\maketitle
\section{Problem Summary}
There are $n$ cities on a line, each with a number of attractions $a_i$. You start at city $S$ (0-indexed) and have $D$ days. Each day you either move to an adjacent city or visit the current city (collecting its attractions, at most once per city). Maximise the total attractions collected.
\section{Solution}
\subsection{Structure of Optimal Solutions}
\begin{lemma}
An optimal strategy visits a contiguous range $[l, r]$ containing $S$. Within that range, it collects the cities with the largest attraction values.
\end{lemma}
The travel cost to visit range $[l, r]$ ($l \le S \le r$) is:
\begin{itemize}
\item \textbf{Left first}: $2(S - l) + (r - S)$.
\item \textbf{Right first}: $(S - l) + 2(r - S)$.
\end{itemize}
The remaining $D - \text{cost}$ days are used to visit cities, so we collect the top $\min(D - \text{cost},\, r - l + 1)$ attraction values in $[l, r]$.
\subsection{Divide and Conquer with Segment Tree}
Fix the direction (left-first or right-first). For a fixed left endpoint $l$, let $r^*(l)$ be the optimal right endpoint.
\begin{lemma}[Monotonicity]
$r^*(l)$ is non-decreasing as $l$ increases, enabling divide-and-conquer optimisation.
\end{lemma}
We use D\&C on $l$: for the midpoint $l_{\text{mid}}$, sweep $r$ to find $r^*(l_{\text{mid}})$, then recurse on the two halves. A segment tree on coordinate-compressed attraction values supports:
\begin{itemize}
\item $\texttt{add}(v)$: insert value $v$.
\item $\texttt{rem}(v)$: remove value $v$.
\item $\texttt{topk}(k)$: sum of the $k$ largest inserted values.
\end{itemize}
We maintain the segment tree incrementally as we expand or shrink the window $[l, r]$.
\section{C++ Implementation}
\begin{lstlisting}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct SegTree {
int n;
vector<int> cnt;
vector<ll> sum;
void init(int _n) {
n = _n;
cnt.assign(4 * n, 0);
sum.assign(4 * n, 0);
}
void update(int node, int l, int r, int pos, int val, ll w) {
if (l == r) { cnt[node] += val; sum[node] += w; return; }
int mid = (l + r) / 2;
if (pos <= mid) update(2*node, l, mid, pos, val, w);
else update(2*node+1, mid+1, r, pos, val, w);
cnt[node] = cnt[2*node] + cnt[2*node+1];
sum[node] = sum[2*node] + sum[2*node+1];
}
ll query(int node, int l, int r, int k) {
if (k <= 0) return 0;
if (k >= cnt[node]) return sum[node];
if (l == r) return (ll)k * (sum[node] / cnt[node]);
int mid = (l + r) / 2;
if (cnt[2*node+1] >= k)
return query(2*node+1, mid+1, r, k);
return sum[2*node+1] + query(2*node, l, mid, k - cnt[2*node+1]);
}
void add(int pos, ll w) { update(1, 0, n-1, pos, 1, w); }
void rem(int pos, ll w) { update(1, 0, n-1, pos, -1, -w); }
ll topk(int k) { return query(1, 0, n-1, k); }
};
int N, S, D;
vector<int> a;
vector<int> sorted_vals;
SegTree seg;
ll best_ans;
int compress(int v) {
return lower_bound(sorted_vals.begin(), sorted_vals.end(), v)
- sorted_vals.begin();
}
int cur_l, cur_r;
void addCity(int i) { seg.add(compress(a[i]), a[i]); }
void remCity(int i) { seg.rem(compress(a[i]), a[i]); }
void expand_to(int l, int r) {
while (cur_r < r) { cur_r++; addCity(cur_r); }
while (cur_l > l) { cur_l--; addCity(cur_l); }
while (cur_r > r) { remCity(cur_r); cur_r--; }
while (cur_l < l) { remCity(cur_l); cur_l++; }
}
void solve(int lo_l, int hi_l, int lo_r, int hi_r, bool leftFirst) {
if (lo_l > hi_l) return;
int mid_l = (lo_l + hi_l) / 2;
int best_r = lo_r;
ll best_val = -1;
for (int r = max(lo_r, S); r <= min(hi_r, N - 1); r++) {
int l = mid_l;
int cost = leftFirst ? 2 * (S - l) + (r - S)
: (S - l) + 2 * (r - S);
int visit = D - cost;
if (visit <= 0) continue;
visit = min(visit, r - l + 1);
expand_to(l, r);
ll val = seg.topk(visit);
if (val > best_val) { best_val = val; best_r = r; }
}
best_ans = max(best_ans, best_val);
solve(lo_l, mid_l - 1, lo_r, best_r, leftFirst);
solve(mid_l + 1, hi_l, best_r, hi_r, leftFirst);
}
long long findMaxAttraction(int n, int start, int d, int attraction[]) {
N = n; S = start; D = d;
a.assign(attraction, attraction + n);
sorted_vals = a;
sort(sorted_vals.begin(), sorted_vals.end());
sorted_vals.erase(unique(sorted_vals.begin(), sorted_vals.end()),
sorted_vals.end());
best_ans = 0;
seg.init(sorted_vals.size());
cur_l = S; cur_r = S - 1;
solve(0, S, S, N - 1, true);
seg.init(sorted_vals.size());
cur_l = S; cur_r = S - 1;
solve(0, S, S, N - 1, false);
return best_ans;
}
\end{lstlisting}
\section{Complexity Analysis}
\begin{itemize}
\item \textbf{Time}: $O(n \log^2 n)$. The D\&C has $O(\log n)$ levels; at each level, the total sweep across all subproblems is $O(n)$, with each step requiring an $O(\log n)$ segment-tree operation.
\item \textbf{Space}: $O(n)$.
\end{itemize}
\end{document}
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
// Segment tree on values (by coordinate-compressed index)
// Supports: insert, erase, query top-k sum
struct SegTree {
int n;
vector<int> cnt;
vector<ll> sum;
void init(int _n) {
n = _n;
cnt.assign(4 * n, 0);
sum.assign(4 * n, 0);
}
void update(int node, int l, int r, int pos, int val, ll w) {
if (l == r) {
cnt[node] += val;
sum[node] += w;
return;
}
int mid = (l + r) / 2;
if (pos <= mid) update(2*node, l, mid, pos, val, w);
else update(2*node+1, mid+1, r, pos, val, w);
cnt[node] = cnt[2*node] + cnt[2*node+1];
sum[node] = sum[2*node] + sum[2*node+1];
}
// Sum of top-k elements
ll query(int node, int l, int r, int k) {
if (k <= 0) return 0;
if (k >= cnt[node]) return sum[node];
if (l == r) return (ll)k * (sum[node] / cnt[node]);
int mid = (l + r) / 2;
if (cnt[2*node+1] >= k)
return query(2*node+1, mid+1, r, k);
else
return sum[2*node+1] + query(2*node, l, mid, k - cnt[2*node+1]);
}
void add(int pos, ll w) { update(1, 0, n-1, pos, 1, w); }
void rem(int pos, ll w) { update(1, 0, n-1, pos, -1, -w); }
ll topk(int k) { return query(1, 0, n-1, k); }
};
int N, S, D;
vector<int> a;
vector<int> sorted_vals;
SegTree seg;
ll best_ans;
int compress(int v) {
return lower_bound(sorted_vals.begin(), sorted_vals.end(), v) - sorted_vals.begin();
}
int cur_l, cur_r; // current window in seg tree
void addCity(int i) { seg.add(compress(a[i]), a[i]); }
void remCity(int i) { seg.rem(compress(a[i]), a[i]); }
void expand_to(int l, int r) {
while (cur_r < r) { cur_r++; addCity(cur_r); }
while (cur_l > l) { cur_l--; addCity(cur_l); }
while (cur_r > r) { remCity(cur_r); cur_r--; }
while (cur_l < l) { remCity(cur_l); cur_l++; }
}
// left-first: cost = 2*(S-l) + (r-S), visit = D - cost
// right-first: cost = (S-l) + 2*(r-S), visit = D - cost
void solve(int lo_l, int hi_l, int lo_r, int hi_r, bool leftFirst) {
if (lo_l > hi_l) return;
int mid_l = (lo_l + hi_l) / 2;
int best_r = lo_r;
ll best_val = -1;
int rmin = max(lo_r, S);
int rmax = min(hi_r, N - 1);
for (int r = rmin; r <= rmax; r++) {
int l = mid_l;
int cost;
if (leftFirst) cost = 2 * (S - l) + (r - S);
else cost = (S - l) + 2 * (r - S);
int visit = D - cost;
if (visit <= 0) continue;
visit = min(visit, r - l + 1);
expand_to(l, r);
ll val = seg.topk(visit);
if (val > best_val) {
best_val = val;
best_r = r;
}
}
best_ans = max(best_ans, best_val);
solve(lo_l, mid_l - 1, lo_r, best_r, leftFirst);
solve(mid_l + 1, hi_l, best_r, hi_r, leftFirst);
}
long long findMaxAttraction(int n, int start, int d, int attraction[]) {
N = n; S = start; D = d;
a.assign(attraction, attraction + n);
sorted_vals = a;
sort(sorted_vals.begin(), sorted_vals.end());
sorted_vals.erase(unique(sorted_vals.begin(), sorted_vals.end()), sorted_vals.end());
best_ans = 0;
// Left-first: l in [0, S], r in [S, N-1]
seg.init(sorted_vals.size());
cur_l = S; cur_r = S - 1;
solve(0, S, S, N - 1, true);
// Right-first: l in [0, S], r in [S, N-1]
seg.init(sorted_vals.size());
cur_l = S; cur_r = S - 1;
solve(0, S, S, N - 1, false);
return best_ans;
}
int main() {
int n, s, d;
scanf("%d %d %d", &n, &s, &d);
int attr[n];
for (int i = 0; i < n; i++) scanf("%d", &attr[i]);
printf("%lld\n", findMaxAttraction(n, s, d, attr));
return 0;
}