Ce document présente les solutions pour les problèmes A, B et C du Round Éducatif Codeforces 174 (Classé pour la Division 2).
A - Y avait-il un Tableau ?
Analyse du Problème
L'énoncé suggère qu'une solution est impossible s'il existe une sous-séquence spécifique dans un tableau dérivé. Le motif interdit semble être une combinaison de 1 et 0.
Logique de Solution
Si la taille du tableau est de 4 ou moins, il est toujours possible de former le tableau d'origine. Pour des tableaux plus grands, nous devons vérifier la présence de la sous-séquence 1, 0, 1 dans un tableau intermédiaire b, qui est construit en prenant des différences entre des éléments adjacents du tableau original. Si cette sous-séquence est trouvée, il n'y a pas de solution ; sinon, une solution existe.
Implémentation
#include <iostream>
#include <vector>
#include <numeric>
void solve() {
int n;
std::cin >> n;
if (n <= 4) {
std::cout << "YES\n";
return;
}
std::vector<int> diffs(n - 2);
for (int i = 0; i < n - 2; ++i) {
std::cin >> diffs[i];
}
for (int i = 0; i <= n - 5; ++i) { // n-2 elements in diffs, so indices 0 to n-3. Need to check triplets.
if (diffs[i] == 1 && diffs[i + 1] == 0 && diffs[i + 2] == 1) {
std::cout << "NO\n";
return;
}
}
std::cout << "YES\n";
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}
B - Ensemble d'Étrangers
Analyse du Problème
On nous donne une grille n x m avec des couleurs assignées à chaque cellule. L'opération autorisée est de choisir deux cellules de la même couleur qui ne sont pas adjacentes et de les recolorer avec une nouvelle couleur. Le but est de trouver le nombre minimum d'opérations pour que toutes les cellules aient la même couleur.
Logique de Solution
Pour chaque couleur existante, nous devons déterminer si des cellules de cette couleur sont adjacentes. Si aucune cellule d'une couleur donnée n'est adjacente à une autre cellule de la même couleur, il faut 1 opération pour la changer. Si elles sont adjacentes, il en faut 2. L'objectif est de minimiser les opérations, donc nous devrions idéalement choisir une couleur qui a des paires adjacentes. Le nombre total d'opérations est la somme des opérations requises pour chaque couleur, moins une opération pour la couleur finale choisie. Si aucune couleur n'a de cellules adjacentes, cela compte comme une opération de moins.
Implémentation
#include <iostream>
#include <vector>
#include <set>
#include <unordered_map>
int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};
void solve() {
int n, m;
std::cin >> n >> m;
std::vector<std::vector<int>> grid(n, std::vector<int>>(m));
std::set<int> distinct_colors;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
std::cin >> grid[i][j];
distinct_colors.insert(grid[i][j]);
}
}
if (distinct_colors.size() == 1) {
std::cout << 0 << "\n";
return;
}
std::unordered_map<int, bool> has_adjacent;
for (int color : distinct_colors) {
has_adjacent[color] = false;
}
for (int r = 0; r < n; ++r) {
for (int c = 0; c < m; ++c) {
int current_color = grid[r][c];
if (has_adjacent[current_color]) continue;
for (int i = 0; i < 4; ++i) {
int nr = r + dx[i];
int nc = c + dy[i];
if (nr >= 0 && nr < n && nc >= 0 && nc < m) {
if (grid[nr][nc] == current_color) {
has_adjacent[current_color] = true;
break;
}
}
}
}
}
int operations = 0;
bool any_adjacent = false;
for (int color : distinct_colors) {
if (has_adjacent[color]) {
operations += 2;
any_adjacent = true;
} else {
operations += 1;
}
}
// We subtract 1 for the final color chosen.
// If there were any adjacent pairs, we effectively get one of those for free.
if (any_adjacent) {
std::cout << operations - 1 -1 << "\n"; // -1 for final color, -1 because one adjacent pair requires only 1 op effectively
} else {
std::cout << operations - 1 << "\n"; // -1 for final color
}
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}
C - Séquence Magnifique
Analyse du Problème
Une séquence est considérée comme magnifique si elle ne contient que les éléments 1, 2 et 3, et suit un motif spécifique. La structuer d'une telle séquence semble être une série de 1, suivie d'une série de 2, puis une série de 3. La tâche est de compter le nombre de sous-séquences magnifiques possibles.
Logique de Solution
Une séquence magnifique valide doit avoir la forme 1...1 2...2 3...3. L'énoncé implique que nous devons trouver des paires de 1 et 3 dans la séquence originale, et compter le nombre de 2 situés entre eux. Pour une paire de 1 et 3 avec m occurrences de 2 entre eux, la contribution à la somme totale est la somme des combinaisons de 2, c'est-à-dire Σ C(m, i) pour i de 1 à m. Ceci est égal à 2^m - 1. Pour éviter les dépassements de temps, nous pouvons précalculer les puissances de 2 et leurs inverses modulaires, et utiliser des structures de données pour un accès efficace aux comptes de 2.
Implémentation
#include <iostream>
#include <vector>
#include <algorithm>
const int MOD = 998244353;
const int MAXN = 200005;
long long pow2[MAXN];
long long inv_pow2[MAXN];
long long power(long long base, long long exp) {
long long res = 1;
base %= MOD;
while (exp > 0) {
if (exp % 2 == 1) res = (res * base) % MOD;
base = (base * base) % MOD;
exp /= 2;
}
return res;
}
long long modInverse(long long n) {
return power(n, MOD - 2);
}
void precompute_powers() {
pow2[0] = 1;
inv_pow2[0] = 1;
long long inv_2 = modInverse(2);
for (int i = 1; i < MAXN; ++i) {
pow2[i] = (pow2[i - 1] * 2) % MOD;
inv_pow2[i] = (inv_pow2[i - 1] * inv_2) % MOD;
}
}
void solve() {
int n;
std::cin >> n;
std::vector<int> a(n);
std::vector<int> count_twos_prefix(n + 1, 0);
std::vector<int> ones_indices;
std::vector<int> threes_indices;
for (int i = 0; i < n; ++i) {
std::cin >> a[i];
count_twos_prefix[i + 1] = count_twos_prefix[i] + (a[i] == 2);
if (a[i] == 1) {
ones_indices.push_back(i);
} else if (a[i] == 3) {
threes_indices.push_back(i);
}
}
if (ones_indices.empty() || threes_indices.empty()) {
std::cout << 0 << "\n";
return;
}
long long total_sum = 0;
int ones_ptr = 0;
// Precompute sums of inverse powers of 2 for segments ending at each '1'
std::vector<long long> prefix_inv_pow2_sum(ones_indices.size() + 1, 0);
for(size_t i = 0; i < ones_indices.size(); ++i) {
int num_twos_before_one = count_twos_prefix[ones_indices[i]];
prefix_inv_pow2_sum[i+1] = (prefix_inv_pow2_sum[i] + inv_pow2[num_twos_before_one]) % MOD;
}
for (int three_idx : threes_indices) {
// Find the number of '1's that appear before this '3'
auto it = std::upper_bound(ones_indices.begin(), ones_indices.end(), three_idx);
int num_ones_before = std::distance(ones_indices.begin(), it);
if (num_ones_before == 0) {
continue;
}
// Sum of 2^k for k = twos between 1 and 3.
// This is related to the number of ways to choose 2s.
// The contribution for a specific 3 and all 1s before it.
// We need sum of (2^m - 1) for each 1-3 pair.
// The formula derived is (sum of inv_pow2[twos_before_1] * 2^twos_between_1_and_3) - num_ones
int num_twos_before_three = count_twos_prefix[three_idx];
// Sum of inv_pow2[twos_before_one] for ones before this three
long long sum_inv_pow2_segment = prefix_inv_pow2_sum[num_ones_before];
// Calculate the contribution: (Sum_{i=1}^{num_ones_before} inv_pow2[twos_before_1_i]) * 2^{twos_before_three} - num_ones_before
long long term1 = (sum_inv_pow2_segment * pow2[num_twos_before_three]) % MOD;
long long term2 = (term1 - num_ones_before + MOD) % MOD;
total_sum = (total_sum + term2) % MOD;
}
std::cout << total_sum << "\n";
}
int main() {
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
precompute_powers();
int t;
std::cin >> t;
while (t--) {
solve();
}
return 0;
}