Problème C : Candles
Dans ce problème, nous avons $N$ bougies disposées sur une ligne et nous devons en allumer $K$ en partant de l'origine (position 0). Le chemin optimal pour allumer $K$ bougies consécutives sera toujours un segment $[L, R]$ contenant l'origine.
Pour chaque segment possible de $K$ bougies, la distence parcourue est la longueur totale du segment plus la distance la plus courte entre l'origine et l'une des deux extrémités du segment. Formellement, pour un segment $[x_i, x_{i+K-1}]$, le coût est :
min(abs(x[i]), abs(x[i+K-1])) + (x[i+K-1] - x[i])
Il suffit de parcourir tous les indices $i$ de $0$ à $N-K$ et de retenir la valeur minimale. La complexité est $O(N)$.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main() {
int n, k;
cin >> n >> k;
vector<long long> pos(n);
for (int i = 0; i < n; ++i) cin >> pos[i];
long long min_dist = 1e18;
for (int i = 0; i <= n - k; ++i) {
long long left = pos[i];
long long right = pos[i + k - 1];
long long current = min(abs(left) + abs(right - left), abs(right) + abs(right - left));
min_dist = min(min_dist, current);
}
cout << min_dist << endl;
return 0;
}
Problème D : Median of Medians
L'objectif est de trouver la médiane de l'ensemble des médianes de tous les sous-tableaux posisbles. Une approche par recherche binaire sur la valeur de la réponse $X$ est efficace. Pour une valeur $X$ donnée, nous voulons savoir si la médiane finale est supérieure ou égale à $X$.
Transformons le tableau original : si $a_i \geq X$, remplaçons-le par $1$, sinon par $-1$. Un sous-tableau a une médiane $\geq X$ si la somme de ses éléments est strictement positive (ou $\geq 0$ selon la convention de la médiane).
Soit $P_i$ la somme préfixe du tableau transformé. Nous cherchons le nombre de paires $(i, j)$ telles que $P_j - P_i \geq 0$ avec $j > i$. Ce décompte peut être effectué en $O(N \log N)$ à l'aide d'un arbre de Fenwick (Binary Indexed Tree). La complexité totale est $O(N \log N \log (\max A))$.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int OFFSET = 100005;
int bit[200010];
void update(int idx, int val, int limit) {
for (; idx <= limit; idx += idx & -idx) bit[idx] += val;
}
int query(int idx) {
int s = 0;
for (; idx > 0; idx -= idx & -idx) s += bit[idx];
return s;
}
bool check(int x, int n, const vector<int>& a) {
for (int i = 0; i < 200010; ++i) bit[i] = 0;
long long count = 0;
int current_sum = 0;
update(OFFSET, 1, 200005);
for (int i = 0; i < n; ++i) {
current_sum += (a[i] >= x ? 1 : -1);
count += query(current_sum + OFFSET);
update(current_sum + OFFSET, 1, 200005);
}
long long total_subarrays = 1LL * n * (n + 1) / 2;
return count >= (total_subarrays + 1) / 2;
}
int main() {
int n;
cin >> n;
vector<int> a(n), b(n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
b[i] = a[i];
}
sort(b.begin(), b.end());
int low = 0, high = n - 1, ans = b[n - 1];
while (low <= high) {
int mid = low + (high - low) / 2;
if (check(b[mid], n, a)) {
ans = b[mid];
low = mid + 1;
} else {
high = mid - 1;
}
}
cout << ans << endl;
return 0;
}
Problème E : Ribbons on Tree
On nous demande de coupler tous les nœuds d'un arbre (N est pair) de sorte que chaque arête de l'arbre soit couevrte par au moins un chemin reliant une paire de nœuds. Par le principe d'inclusion-exclusion, nous pouvons compter le nombre de façons de coupler les nœuds tel qu'un sous-ensemble spécifique d'arêtes ne soit jamais traversé.
Si un ensemble d'arêtes $S$ n'est pas traversé, l'arbre se divise en plusieurs composantes connexes. Pour chaque composante de taille $n$, le nombre de façons de coupler ses nœuds est $g(n)$, où $g(n) = (n-1)!!$ si $n$ est pair, et $0$ sinon.
Nous utilisons la programmation dynamique sur l'arbre. Soit $dp[u][s]$ le nombre de façons de former des couplages dans le sous-arbre de $u$, où $u$ appartient à une composante connexe de taille $s$. Lors de la transition pour une arête $(u, v)$ :
- Soit on garde l'arête : les composantes de $u$ et $v$ fusionnent.
- Soit on supprime l'arête : la composante de $v$ est finalisée (multipliée par $-g(size(v))$ pour l'inclusion-exclusion) et $u$ commence une nouvelle branche.
#include <iostream>
#include <vector>
using namespace std;
long long MOD = 1e9 + 7;
int n;
vector<int> adj[5005];
long long dp[5005][5005];
int sz[5005];
long long g[5005];
void dfs(int u, int p) {
sz[u] = 1;
dp[u][1] = 1;
for (int v : adj[u]) {
if (v == p) continue;
dfs(v, u);
static long long next_dp[5005];
for (int i = 0; i <= sz[u] + sz[v]; ++i) next_dp[i] = 0;
long long ways_to_cut = 0;
for (int j = 1; j <= sz[v]; ++j) {
ways_to_cut = (ways_to_cut + dp[v][j] * g[j]) % MOD;
}
for (int i = 1; i <= sz[u]; ++i) {
// Option 1: Ne pas couper l'arête (u, v)
for (int j = 1; j <= sz[v]; ++j) {
next_dp[i + j] = (next_dp[i + j] + dp[u][i] * dp[v][j]) % MOD;
}
// Option 2: Couper l'arête (u, v) - Inclusion-Exclusion
next_dp[i] = (next_dp[i] - (dp[u][i] * ways_to_cut % MOD) + MOD) % MOD;
}
sz[u] += sz[v];
for (int i = 1; i <= sz[u]; ++i) dp[u][i] = next_dp[i];
}
}
int main() {
cin >> n;
for (int i = 0; i < n - 1; ++i) {
int u, v; cin >> u >> v;
adj[u].push_back(v); adj[v].push_back(u);
}
g[0] = 1;
for (int i = 2; i <= n; i += 2) g[i] = g[i - 2] * (i - 1) % MOD;
dfs(1, 0);
long long res = 0;
for (int i = 1; i <= n; ++i) {
res = (res + dp[1][i] * g[i]) % MOD;
}
cout << res << endl;
return 0;
}
Problème F : Robots and Exits
Chaque robot situé entre deux sorties $E_i$ et $E_{i+1}$ finira par sortir par l'une ou l'autre. Soit $x$ la position du robot, $d_L = x - E_i$ la distance à la sortie gauche et $d_R = E_{i+1} - x$ la distance à la sortie droite.
Un robot sort par la gauche si le mouvement global vers la gauche atteint $d_L$ avant que le mouvement global vers la droite n'atteigne $d_R$. Chaque robot peut être représenté par un point $(d_L, d_R)$ dans un plan 2D. Le problème revient à compter le nombre de séquences de décisions (Gauche/Droite) uniques.
En triant les points par $d_L$ et en éliminant les points redondants, nous pouvons utiliser un arbre de Fenwick pour calculer le nombre de sous-suites croissantes de coordonnées $d_R$. La complexité est $O((N+M) \log (N+M))$.
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int MOD = 1e9 + 7;
struct Point {
int l, r;
bool operator<(const Point& other) const {
if (l != other.l) return l < other.l;
return r < other.r;
}
bool operator==(const Point& other) const {
return l == other.l && r == other.r;
}
};
int main() {
int n, m;
cin >> n >> m;
vector<int> x(n), y(m);
for (int i = 0; i < n; ++i) cin >> x[i];
for (int i = 0; i < m; ++i) cin >> y[i];
vector<Point> pts;
for (int i = 0; i < n; ++i) {
auto it = lower_bound(y.begin(), y.end(), x[i]);
if (it == y.begin() || it == y.end()) continue;
pts.push_back({x[i] - *(it - 1), *it - x[i]});
}
if (pts.empty()) {
cout << 1 << endl;
return 0;
}
sort(pts.begin(), pts.end());
pts.erase(unique(pts.begin(), pts.end()), pts.end());
vector<int> coords_r;
for (auto& p : pts) coords_r.push_back(p.r);
sort(coords_r.begin(), coords_r.end());
coords_r.erase(unique(coords_r.begin(), coords_r.end()), coords_r.end());
int sz = coords_r.size();
vector<long long> bit(sz + 1, 0), last_val(sz + 1, 0);
long long total_ways = 1;
auto update = [&](int idx, long long val) {
for (; idx <= sz; idx += idx & -idx) bit[idx] = (bit[idx] + val) % MOD;
};
auto query = [&](int idx) {
long long res = 0;
for (; idx > 0; idx -= idx & -idx) res = (res + bit[idx]) % MOD;
return res;
};
for (int i = 0, j = 0; i < pts.size(); i = j) {
while (j < pts.size() && pts[i].l == pts[j].l) j++;
for (int k = i; k < j; ++k) {
int r_idx = lower_bound(coords_r.begin(), coords_r.end(), pts[k].r) - coords_r.begin() + 1;
long long current_ways = (query(r_idx - 1) + 1) % MOD;
long long increment = (current_ways - last_val[r_idx] + MOD) % MOD;
last_val[r_idx] = current_ways;
update(r_idx, increment);
total_ways = (total_ways + increment) % MOD;
}
}
cout << total_ways << endl;
return 0;
}