A. Cerradura de Combinación

Se presenta una cerradura de combinación de cuatro dígitos, donde cada dial contiene los números del 0 al 9. El siguiente dígito después de \(i\) es \((i+1) \pmod{10}\), y el dígito anterior es \((i-1) \pmod{10}\). En cada operación, puedes seleccionar un segmento contiguo de dígitos y rotarlo un paso hacia arriba o hacia abajo. Dado un estado inicial de la cerradura, el objetivo es ancontrar el número mínimo de operaciones para alcanzar un estado objetivo.

Estrategia

Una cerradura de \(abcd \rightarrow efgh\) puede ser vista como una transformación del estado inicial \(0000\) al estado objetivo \( (abcd - efgh) \pmod{10}\). Por lo tanto, podemos precalcular las distancias más cortas desde \(0000\) a todos los demás estados utilizando una búsqueda en anchura (BFS).

Código

#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <map>
#include <algorithm>

struct State {
   std::vector<int> digits;
   int distance;
};

std::queue<State> q;
std::map<std::vector<int>, int> min_distances;

void initialize_bfs() {
   min_distances[{0, 0, 0, 0}] = 0;
   q.push({{0, 0, 0, 0}, 0});
}

void run_bfs() {
   while (!q.empty()) {
       State current_state = q.front();
       q.pop();

       int current_dist = current_state.distance;
       std::vector<int> current_digits = current_state.digits;

       for (int i = 0; i < 4; ++i) {
           for (int j = i; j < 4; ++j) {
               for (int rotation : {-1, 1}) { // -1 for down, 1 for up
                   std::vector<int> next_digits = current_digits;
                   for (int k = i; k <= j; ++k) {
                       next_digits[k] = (next_digits[k] + rotation + 10) % 10;
                   }

                   if (min_distances.find(next_digits) == min_distances.end()) {
                       min_distances[next_digits] = current_dist + 1;
                       q.push({next_digits, current_dist + 1});
                   }
               }
           }
       }
   }
}

void solve() {
   std::string initial_str, target_str;
   std::cin >> initial_str >> target_str;

   std::vector<int> diff_digits(4);
   for (int i = 0; i < 4; ++i) {
       diff_digits[i] = (initial_str[i] - target_str[i] + 10) % 10;
   }

   std::cout << min_distances[diff_digits] << "\n";
}

int main() {
   std::ios::sync_with_stdio(false);
   std::cin.tie(nullptr);
   std::cout.tie(nullptr);

   initialize_bfs();
   run_bfs();

   int num_test_cases;
   std::cin >> num_test_cases;
   while (num_test_cases--) {
       solve();
   }

   return 0;
}
 

B. Colores Vibrantes

Definimos el valor de diversidad entre dos cadenas \(S\) y \(T\) de longitud \(N\) como \(f(S,T) = \sum_{i=0}^{N-1} [S_i \ne T_i]\).

Se busca calcular \(\sum_{i=0}^{N-1} \sum_{j=0}^{N-1} f(S \text{LSH} i, S \text{LSH} j)\), donde \(S \text{LSH} x\) representa el resultado de rotar \(S\) \(x\) posiciones a la izquierda.

Estrategia

Considreemos el problema complementario: contar las coincidencias en lugar de las diferencias. Cada par de caracteres idénticos en la misma posición antre dos rotaciones contribuye \(N\) al resultado total. Si \(cnt_c\) es la frecuencia del carácter \(c\), la contribución total de las coincidencias es \(\sum_{c} cnt_c^2 \cdot N\). El resultado final se obtiene restando esta suma del número total de comparaciones posibles, que es \(N^3\).

Código

#include <iostream>
#include <vector>
#include <string>
#include <numeric>

int main() {
   std::ios::sync_with_stdio(false);
   std::cin.tie(nullptr);
   std::cout.tie(nullptr);

   int n;
   std::cin >> n;
   std::string s;
   std::cin >> s;

   std::vector<int> char_counts(26, 0);
   for (char c : s) {
       char_counts[c - 'a']++;
   }

   long long total_possible_pairs = (long long)n * n * n;
   long long matching_contribution = 0;

   for (int count : char_counts) {
       matching_contribution += (long long)count * count * n;
   }

   std::cout << total_possible_pairs - matching_contribution << std::endl;

   return 0;
}
 </numeric></string>

C. Árbol Blanco y Negro

Se da un árbol donde cada nodo está inicialmente coloreado de negro o blanco. Se puede realizar la siguiente operación cualquier número de veces: seleccionar un nodo **hoja** y revertir el color de todos los nodos en la ruta desde esa hoja hasta la raíz. El objetivo es maximizar el número de nodos negros al final.