Los gráficos se pueden usar para problemas aparentemente inconexos. Diga el problema de las tarjetas que tienen números en ambos lados e intente crear una secuencia continua de números usando un lado. Este problema genera problemas sobre cómo dividir un gráfico en subconjuntos conectados con ciclos y subconjuntos conectados sin ciclos.
Existen algoritmos conocidos para detectar si el gráfico contiene un círculo. Aquí lo modificamos para encontrar todos los Nodes no conectados a los círculos. Agregamos una array booleana cíclica iniciada como falsa, lo que significa que no se sabe que ningún Node esté conectado a un círculo.
Luego recorremos los Nodes aplicando un algoritmo habitual para determinar un círculo omitiendo los Nodes que ya se sabe que están conectados a un círculo. Cada vez que encontramos un nuevo Node conectado a un círculo, propagamos la propiedad a todos los Nodes conectados, omitiendo los ya designados como conectados nuevamente.
La función principal es una modificación del algoritmo DFS del artículo » Detectar ciclos en gráficos no dirigidos «:
Todos los Nodes conectados a un ciclo se designan como tales en un tiempo lineal.
El algoritmo se aplicó al siguiente problema del desafío reciente «Germanio» , que fue resuelto por aproximadamente el 3,5% de los participantes.
Supongamos que tenemos N tarjetas (100000 >= N >= 1) y en ambos lados de las tarjetas hay un número ( N son inútiles y se pueden descartar. En el mismo espíritu, cada automóvil (n, m): n N permite nosotros ponemos n hacia arriba y aseguramos su presencia en la secuencia, mientras que m es inútil de todos
modos.Si tenemos una tarjeta (nn): n < N, asegura que n siempre se puede agregar a una secuencia continua que llegó a n-1
Si tenemos dos cartas idénticas (n, m), ambas n, m siempre se pueden agregar a una secuencia si es necesario, solo para ponerla en el lado opuesto .
Ahora codificamos las tarjetas en un gráfico de la siguiente manera. Se supone que los Nodes del gráfico están numerados de 0 a N-1. Cada Node tiene un conjunto de aristas que conducen a se representa como un vector, iniciado como un conjunto vacío y total de aristas es un vector de vectores de números enteros – aristas (N).
(n, m) : n, m N – descartado.
(n, m): n N – agregar al borde del gráfico (n-1, n-1)
Ahora es fácil entender que cada ciclo en el gráfico puede usarse para todos los Nodes del gráfico. Una muestra: (1, 2) (2, 5), (5, 1) – cada número aparece en dos tarjetas, simplemente pase el ciclo y coloque cualquier número una vez hacia arriba y otra vez hacia abajo:
(1, 2) – 1 arriba, 2 abajo
(2, 5) – 2 arriba, 5 abajo
(5, 1) – 5 arriba, 1 abajo
Si algún número ya está puesto en la parte superior, cada carta subsiguiente que tenga el número debe tener este número hacia abajo, para que se pueda mostrar otro número en la parte superior. En el gráfico, significa que cualquier número conectado por una arista a un número de ciclos se puede mostrar libremente. Lo mismo es cierto para una tarjeta conectada a la tarjeta conectada al ciclo. Por lo tanto, cualquier número/Node que se conecte de alguna manera a cualquier ciclo no puede generar ningún problema. Los pares de cartas idénticas como (1, 2), (1, 2) también producen un pequeño círculo en el gráfico, lo mismo ocurre con las cartas dobles, como 3, 3 es un ciclo de un Node conectado a sí mismo.
Todas las partes del gráfico que no están conectadas a ningún ciclo se pueden dividir en gráficos más pequeños no conectados. Es más o menos obvio que cualquier fragmento de este tipo tiene un número problemático: el más grande del fragmento. Usamos un algoritmo similar pero mucho más fácil para encontrar tales fragmentos y todos los máximos en fragmentos. El menor de ellos es Q: el número más pequeño que no puede ser el final de la cobertura continua de los números menores, el Q anterior.
Además de la array cíclica, agregamos otra array:visitedNonCyclic, lo que significa que este número ya se alcanzó al pasar por un fragmento que no es de ciclo.
El máximo en el fragmento que no es de ciclo se extrae mediante llamadas recurrentes a una función:
Consulte findMax() en el código siguiente. La creación del gráfico se realiza en la solución() del siguiente código.
Después de crear el gráfico, la solución simplemente llama a isCyclic y luego a:
// the main crux of the solution, see full code below graph.isCyclic(); int res = 1 + graph.GetAnswer();
La solución, que se inspiró en el reciente y bastante duro “ Germanium 2018 Codility Challenge ” y trajo la medalla de oro.
Idea principal:
1. Los números son grandes, pero exigimos una secuencia continua desde el 1 hasta el último número,
pero no hay más de 100 000 números. Entonces, el mayor posible es realmente 100 000, tómalo como la primera hipótesis
2. Debido a las mismas consideraciones, el número más grande no puede ser mayor que N (cantidad de números)
3. También podemos pasar números generales y tomar el mayor que es NN. El resultado no puede ser mayor que N o NN
4. Teniendo esto en cuenta, podemos reemplazar todas las cartas como (x, 200 000) en (x, x). Ambos permiten configurar x hacia arriba, por lo que x no es un problema.
5. Tarjetas con ambos números más grandes que N o NN simplemente ignoradas o descartadas
6. Si hay tarjetas con el mismo número en ambos lados, significa que el número siempre está bien, no puede ser el más pequeño problemático, por lo que nunca es la respuesta.
7. Si hay dos cartas idénticas como (x, y) e (y, x) significa que tanto x como y no son problemáticas y no pueden ser la respuesta
8. Ahora introducimos la GRAN idea principal de que traducimos el conjunto de tarjetas en un gráfico. Los vórtices del gráfico están numerados de 0 a M-1, donde M es el último número posible (el menor de N, NN). Cada Node tiene algunos Nodes adyacentes, por lo que el conjunto de todas las aristas es un vector de vectores de números enteros
8. Cada tarjeta como (x, y) con ambos números menores o iguales a M en la arista x-1, y-1, por lo que el el primer Node obtiene un Node adyacente adicional y viceversa
9. Algunos vórtices estarán conectados entre sí debido a cartas como (3, 3). Es un caso de bucle de tamaño 1.
10. Algunos vórtices estarán conectados por dos bordes o más si hay tarjetas idénticas. Es un lazo de tamaño 2.
11. Los lazos de tamaño 1 y 2 tienen números que no pueden ser de ningún problema. Pero ahora nos damos cuenta de que lo mismo ocurre con un ciclo de cualquier longitud. Por ejemplo, las cartas son 2, 3; 3, 4; 4, 10; 10, 2; Todos sus números no tienen problema, solo pon 2, 3, 4, 10 en la parte de arriba. La desventaja tendrá 3, 4, 10, 2.
12. Ahora, si tenemos una tarjeta x, y y sabemos que x ya está garantizada en otro lugar, podemos poner esta tarjeta x abajo, y arriba y asegurarnos de que la y está en la secuencia resultante.
12. Entonces, si alguna tarjeta está conectada a un ciclo por un borde, no puede presentar un problema ya que el ciclo está todo OK, por lo que este número también está OK.
13. Así, si hay un subconjunto interconectado de Nodes de un gráfico que contiene un ciclo, todos los vórtices no pueden presentar ningún problema.
Entonces, podemos aplicar uno de los algoritmos conocidos para encontrar bucles como en el artículo » Detectar ciclo en un gráfico no dirigido » con una adición de propagación
14. También podemos designar todos los Nodes en el gráfico que están conectados a un ciclo, ciclado[ ]. Y podemos propagar la propiedad
Simplemente comience con algunos en un ciclo, configúrelo como un ciclo, luego pase sobre su adyacente omitiendo el ciclo y llamando a la misma función en el adyacente.
15. Usando una combinación del algoritmo conocido para detectar ciclos en un gráfico no dirigido saltando sobre ciclado ya y propagando la propiedad «conectado a un ciclo», encontramos todos los Nodes conectados a ciclos. Todos estos Nodes son seguros, no pueden ser un problema
16. Pero siendo Nodes no conectados a ningún ciclo, su problema se puede simplificar pero cortando en gráficos separados que no tienen aristas o Nodes comunes.
17. Pero, ¿qué hacer con ellos? Puede ser una rama lineal o ramas que se cruzan entre sí. Todos los Nodes son diferentes.
18. Con un último esfuerzo, uno puede entender que cualquier conjunto de este tipo tiene solo un número problemático: el máximo del conjunto. Se puede comprobar, fijándose que los cruces solo mejoran las cosas, pero el máximo se queda quieto.
19. Entonces, cortamos todo lo que no tiene ciclos en entidades separadas conectadas y encontramos el máximo en cada una.
20. ¡Luego encontramos el mínimo de ellos y esta es la respuesta final!
Ejemplos:
Entrada: A = [1, 2, 4, 3] B = [1, 3, 2, 3]
Salida: 5.
Porque las tarjetas tal como están proporcionan 1, 2, 3, 4 pero no 5.Entrada: A = [4, 2, 1, 6, 5] B = [3, 2, 1, 7, 7],
Salida: 4.
Porque puede mostrar 3 o 4 en la primera carta pero no tanto 3 como 4 Entonces, pon 3, mientras que el 1 y el 2 están junto a las siguientes cartas.Entrada: A = [2, 3], B = [2, 3]
Salida: 1. Porque falta 1.
Complejidad:
- la complejidad temporal esperada en el peor de los casos es O(N);
- la complejidad espacial esperada en el caso más desfavorable es O(N);
La implementación final
C++
#include <algorithm>
#include <vector>
using namespace std;
class Graph {
private:
int V; // No. of vertices
vector<vector<int> > edges; // edges grouped by nodes
bool isCyclicUtil(int v, vector<bool>& visited, int parent);
vector<bool> cyclic;
vector<int> maxInNonCyclicFragments;
int findMax(int v);
vector<bool> visitedNonCyclic;
void setPropagateCycle(int v);
public:
Graph(int V); // Constructor
void addEdge(int v, int w); // to add an edge to graph
// returns true if there is a cycle and
// also designates all connected to a cycle
bool isCyclic();
int getSize() const { return V; }
int GetAnswer();
};
Graph::Graph(int V)
{
this->V = V;
edges = vector<vector<int> >(V, vector<int>());
visitedNonCyclic = cyclic = vector<bool>(V, false);
}
void Graph::addEdge(int v, int w)
{
edges[v].push_back(w);
edges[w].push_back(v);
}
void Graph::setPropagateCycle(int v)
{
if (cyclic[v])
return;
cyclic[v] = true;
for (auto i = edges[v].begin(); i != edges[v].end(); ++i) {
setPropagateCycle(*i);
}
}
bool Graph::isCyclicUtil(int v, vector<bool>& visited, int parent)
{
if (cyclic[v])
return true;
// Mark the current node as visited
visited[v] = true;
// Recur for all the vertices edgesacent to this vertex
vector<int>::iterator i;
for (i = edges[v].begin(); i != edges[v].end(); ++i) {
// If an edgesacent is not visited, then
// recur for that edgesacent
if (!visited[*i]) {
if (isCyclicUtil(*i, visited, v)) {
setPropagateCycle(v);
return true;
}
}
// If an edgesacent is visited and not parent
// of current vertex, then there is a cycle.
else if (*i != parent) {
setPropagateCycle(v);
return true;
}
if (cyclic[*i]) {
setPropagateCycle(v);
return true;
}
}
return false;
}
bool Graph::isCyclic()
{
// Mark all the vortices as not visited
// and not part of recursion stack
vector<bool> visited(V, false);
// Call the recursive helper function
// to detect cycle in different DFS trees
bool res = false;
for (int u = 0; u < V; u++)
// Don't recur for u if it is already visited{
if (!visited[u] && !cyclic[u]) {
if (isCyclicUtil(u, visited, -1)) {
res = true;
// there was return true originally
visited = vector<bool>(V, false);
}
}
return res;
}
int Graph::findMax(int v)
{
if (cyclic[v])
return -1;
if (visitedNonCyclic.at(v))
return -1;
int res = v;
visitedNonCyclic.at(v) = true;
for (auto& u2 : edges.at(v)) {
res = max(res, findMax(u2));
}
return res;
}
int Graph::GetAnswer()
{
// cannot be less than, after extract must add 1
int res = V;
for (int u = 0; u < V; u++) {
maxInNonCyclicFragments.push_back(findMax(u));
}
for (auto& u : maxInNonCyclicFragments) {
if (u >= 0)
res = min(res, u);
}
return res;
}
int solution(vector<int>& A, vector<int>& B)
{
const int N = (int)A.size();
const int MAX_AMOUNT = 100001;
vector<bool> present(MAX_AMOUNT, false);
for (auto& au : A) {
if (au <= N) {
present.at(au) = true;
}
}
for (auto& au : B) {
if (au <= N) {
present.at(au) = true;
}
}
int MAX_POSSIBLE = N;
for (int i = 1; i <= N; i++) {
if (false == present.at(i)) {
MAX_POSSIBLE = i - 1;
break;
}
}
Graph graph(MAX_POSSIBLE);
for (int i = 0; i < N; i++) {
if (A.at(i) > MAX_POSSIBLE && B.at(i) > MAX_POSSIBLE) {
continue;
}
int mi = min(A.at(i), B.at(i));
int ma = max(A.at(i), B.at(i));
if (A.at(i) > MAX_POSSIBLE || B.at(i) > MAX_POSSIBLE) {
graph.addEdge(mi - 1, mi - 1);
}
else {
graph.addEdge(mi - 1, ma - 1);
}
}
graph.isCyclic();
int res = 1 + graph.GetAnswer();
return res;
}
// Test and driver
#include <iostream>
void test(vector<int>& A, vector<int>& B, int expected,
bool printAll = false)
{
int res = solution(A, B);
if (expected != res || printAll) {
for (size_t i = 0; i < A.size(); i++) {
cout << A.at(i) << " ";
}
cout << endl;
for (size_t i = 0; i < B.size(); i++) {
cout << B.at(i) << " ";
}
cout << endl;
if (expected != res)
cout << "Error! Expected: " << expected << " ";
else
cout << "Expected: " << expected << " ";
}
cout << " Result: " << res << endl;
}
int main()
{
vector<int> VA;
vector<int> VB;
int A4[] = { 1, 1, 1, 1, 1 };
int B4[] = { 2, 3, 4, 5, 6 };
VA = vector<int>(A4, A4 + 1);
VB = vector<int>(B4, B4 + 1);
test(VA, VB, 2, true);
int A0[] = { 1, 1 };
int B0[] = { 2, 2 };
VA = vector<int>(A0, A0 + 2);
VB = vector<int>(B0, B0 + 2);
test(VA, VB, 3);
int A[] = { 1, 2, 4, 3 };
int B[] = { 1, 3, 2, 3 };
VA = vector<int>(A, A + 4);
VB = vector<int>(B, B + 4);
test(VA, VB, 5);
int A2[] = { 4, 2, 1, 6, 5 };
int B2[] = { 3, 2, 1, 7, 7 };
VA = vector<int>(A2, A2 + 5);
VB = vector<int>(B2, B2 + 5);
test(VA, VB, 4);
int A3[] = { 2, 3 };
int B3[] = { 2, 3 };
VA = vector<int>(A3, A3 + 2);
VB = vector<int>(B3, B3 + 2);
test(VA, VB, 1);
return 0;
}
1 2 Expected: 2 Result: 2 Result: 3 Result: 5 Result: 4 Result: 1
Publicación traducida automáticamente
Artículo escrito por LeviKitrossky y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA