c - ¿Cómo reducir la complejidad del tiempo al atravesar una cadena?
Estaba resolviendo un problema para encontrar el número de índices, a, b, c, d en una cadena s, de tamaño n formada solo por letras minúsculas, de modo que:
1 <= a < b < c < d <= n
y
s[a] == s[c] y s[b] == s[d]
El código que escribí atraviesa la cadena carácter por carácter de una manera básica:
#include<stdio.h>
int main()
{
int n, count = 0;
char s[2002];
scanf("%d%s", &n, s);
for(int a = 0; a<n-3; a++)
{
for(int b = a + 1; b<n-2; b++)
{
for(int c = b + 1; c<n-1; c++)
{
for(int d = c + 1; d<n; d++)
{
if(s[a] == s[c] && s[b] == s[d] && a>=0 && b>a && c>b && d>c && d<n)
{
count++;
}
}
}
}
}
printf("%d", count);
return 0;
}
a, b, cyd son los índices. El problema es que si la cadena de entrada es grande, el límite de tiempo se excede debido a los 4 bucles anidados. ¿Hay alguna manera de mejorar el código para disminuir la complejidad?
El planteamiento del problema está disponible aquí: https://www.hackerearth.com/practice/algorithms/searching/linear-search/practice-problems/algorithm/holiday-season-ab957deb/
Será difícil resolver este problema en O(n). Sin embargo, O(n^2) es posible.
- AKSingh28/03/2021 a las 11:16
Aunque la descripción del problema lo oscurece (supongo que intencionalmente), se trata de un problema de intervalos superpuestos.
- John Bollinger28/03/2021 a las 13:14
Logré resolver tu problema. La complejidad de mi código es O(n^2).
- AKSingh28/03/2021 a las 14:36
------------------------------------
El problema se puede resolver si mantiene una matriz que almacena la frecuencia acumulada (el total de una frecuencia y todas las frecuencias hasta el momento en una distribución de frecuencia) de cada carácter en la cadena de entrada. Dado que la cadena solo constará de caracteres en minúscula, el tamaño de la matriz será [26][N+1].
Por ejemplo:
index - 1 2 3 4 5
string - a b a b a
cumulativeFrequency array:
0 1 2 3 4 5
a 0 1 1 2 2 3
b 0 0 1 1 2 2
Hice la matriz tomando el índice del primer carácter de la cadena de entrada como 1. Hacerlo nos ayudará a resolver el problema más adelante. Por ahora, simplemente ignore la columna 0 y suponga que la cadena comienza en el índice 1 y no en el 0.
Datos útilesUtilizando una matriz de frecuencia acumulada podemos comprobar fácilmente si un carácter está presente en cualquier índice i:
if cumulativeFrequency[i]-cumulativeFrequency[i-1] > 0
número de veces que un carácter está presente desde el rango i al j (excluyendo i y j):
frequency between i and j = cumulativeFrequency[j-1] - cumulativeFrequency[i]
1: for each character from a-z:
2: Locate index a and c such that charAt[a] == charAt[c]
3: for each pair (a, c):
4: for character from a-z:
5: b = frequency of character between a and c
6: d = frequency of character after c
7: count += b*d
Línea 1-2:
El bucle más externo se ejecutará 26 veces. Necesitamos localizar todos los par(a, c), para hacer eso requerimos una complejidad temporal de O(n^2).
Línea 3-4:
Para cada par, volvemos a ejecutar un bucle 26 veces para comprobar cuántas veces cada carácter está presente entreentre a y c y después de c.
Línea 5-7:
Utilizando una matriz de frecuencia acumulativa, para cada carácter podemos calcular fácilmente cuántas veces aparece entre a y c y después de c en O(1).
Por lo tanto, la complejidad general es O(26*n^2*26) = O(n^2).
CódigoCodifico en Java. No tengo un código en C. He usado bucles simples y una matriz por lo que debería ser fácil de entender.
//Input N and string
//Do not pay attention to the next two lines since they are basically taking
//input using Java input streams
int N = Integer.parseInt(bufferedReader.readLine().trim());
String str = bufferedReader.readLine().trim();
//Construct an array to store cumulative frequency of each character in the string
int[][] cumulativeFrequency = new int[26][N+1];
//Fill the cumulative frequency array
for (int i = 0;i < str.length();i++)
{
//character an index i
char ch = str.charAt(i);
//Fill the cumulative frequency array for each character
for (int j = 0;j < 26;j++)
{
cumulativeFrequency[j][i+1] += cumulativeFrequency[j][i];
if (ch-97 == j) cumulativeFrequency[j][i+1]++;
}
}
int a, b, c, d;
long count = 0;
//Follow the steps of the algorithm here
for (int i = 0;i < 26;i++)
{
for (int j = 1; j <= N - 2; j++)
{
//Check if character at i is present at index j
a = cumulativeFrequency[i][j] - cumulativeFrequency[i][j - 1];
if (a > 0)
{
//Check if character at i is present at index k
for (int k = j + 2; k <= N; k++)
{
c = cumulativeFrequency[i][k] - cumulativeFrequency[i][k - 1];
if (c > 0)
{
//For each character, find b*d
for (int l = 0; l < 26; l++)
{
//For each character calculate b and d
b = cumulativeFrequency[l][k-1] - cumulativeFrequency[l][j];
d = cumulativeFrequency[l][N] - cumulativeFrequency[l][k];
count += b * d;
}
}
}
}
}
}
System.out.println(count);
Espero haberte ayudado. El código que proporcioné no dará error de complejidad temporal y funcionará para todos los casos de prueba. Comenta si no entiendes nada de mi explicación.
2
Este es un gran enfoque. Dado que escribí una respuesta que no proporciona ningún código (porque el OP debería escribir el suyo propio, en mi opinión), no puedo culparlo por proporcionar código Java en una pregunta de C.
- John Bollinger28/03/2021 a las 15:21
@JohnBollinger Gracias por los comentarios. Sólo escribí bucles simples en código Java. Cualquier persona necesitará usar lápiz y papel si realmente quiere saber cómo funciona el código jajaja.
- AKSingh28/03/2021 a las 15:30
------------------------------------
Realizar la verificación de igualdad en las primeras etapas puede ahorrarle algo de tiempo. También la marca a>=0 && b>a && c>b && d>c && d<n parece innecesario ya que ya está verificando esta condición en los bucles. Una versión mejorada puede ser la siguiente:
#include<stdio.h>
int main()
{
int n, count = 0;
char s[2002];
scanf("%d%s", &n, s);
for(int a = 0; a<n-3; a++)
{
for(int b = a + 1; b<n-2; b++)
{
for(int c = b + 1; c<n-1; c++)
{
if(s[a] == s[c]) {
for(int d = c + 1; d<n; d++)
{
if(s[b] == s[d])
{
count++;
}
}
}
}
}
}
printf("%d", count);
return 0;
}
1
Gracias, la modificación resuelve algunos casos de prueba más dentro del límite de tiempo, peroTodavía hay algunos en los que se supera el límite, aunque sólo por una pequeña cantidad. ¿Hay alguna forma de fusionar 2 bucles cualesquiera?
- rohan84328/03/2021 a las 11:13
------------------------------------
Dado que la cadena S está formada únicamente por letras minúsculas, puede mantener una tabla de 26x26 (en realidad 25x25, ignorar cuando i=j) que mantenga la apariencia de todos los posibles casos distintos de dos letras (por ejemplo, ab, ac, bc, etc.) ).
El siguiente código rastrea la integridad de cada respuesta candidata (abab, acac, bbcc, etc.) mediante dos funciones: verificar la posición AC y verificar la posición BD. Una vez que el valor llega a 4, significa que el candidate es una respuesta válida.
#include <stdio.h>
int digitsAC(int a)
{
if(a % 2 == 0)
return a + 1;
return a;
}
int digitsBD(int b)
{
if(b % 2 == 1)
return b + 1;
return b;
}
int main()
{
int n, count = 0;
char s[2002];
int appearance2x2[26][26] = {0};
scanf("%d%s", &n, s);
for(int i = 0; i < n; ++i)
{
int id = s[i] - 'a';
for(int j = 0; j < 26; ++j)
{
appearance2x2[id][j] = digitsAC(appearance2x2[id][j]);
appearance2x2[j][id] = digitsBD(appearance2x2[j][id]);
}
}
//counting the results
for(int i = 0; i < 26; ++i)
{
for(int j = 0; j < 26; ++j)
{
if(i == j)continue;
if(appearance2x2[i][j] >= 4)count += ((appearance2x2[i][j] - 2) / 2);
}
}
printf("%d", count);
return 0;
}
La complejidad del tiempo es O(26N), que es igual a lineal. El código se puede acelerar aún más realizando operaciones de máscara bit a bit, pero dejé las funciones simples para mayor claridad. No lo he probado mucho. ¡Dime si encuentras algún error!
editar: existe un problema al manejar letras que aparecen continuamente como aabbaabb
3
La idea de usar una matriz auxiliar es buena, pero este código no hace lo mismo que el código original (y lo que plantea la pregunta), creo:Usted cuenta las posibles combinaciones de letras, pero el original cuenta las posibles "selecciones" de la cadena, donde "ababababa" debería tener más de dos aciertos.
- M Oehm28 de marzo de 2021 a las 11:58
Vaya, parece que me equivoqué en la pregunta. Pero siento que un ajuste en la parte de conteo debería funcionar. Editaré mi respuesta después de ejecutar algunos casos de prueba.
- Sorevan28/03/2021 a las 12:24
1
El programa no funcionará con la cadena de entrada ababab. El recuento debe ser 6 mientras que el resultado producido es 3.
- AKSingh28/03/2021 a las 12:41
------------------------------------
Aquí hay una solución O(n) (contando el número de caracteres en el juego de caracteres permitido como constante).
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
/* As used in this program, "substring" means a string that can be formed by
characters from another string. The resulting characters are not
necessarily consecutive in the original string. For example, "ab" is a
substring of "xaxxxxbxx".
This program requires the lowercase letters to have consecutive codes, as
in ASCII.
*/
#define Max 2000 // Maximum string length supported.
typedef short T1; // A type that can hold Max.
typedef int T2; // A type that can hold Max**2.
typedef long T3; // A type that can hold Max**3.
typedef long long T4; // A type that can hold Max**4.
#define PRIT4 "lld" // A conversion specification that will print a T4.
#define L ('z'-'a'+1) // Number of characters in the set allowed.
/* A Positions structure records all positions of a character in the string.
N is the number of appearances, and Position[i] is the position (index into
the string) of the i-th appearance, in ascending order.
*/
typedef struct { T1 N, Position[Max]; } Positions;
/* Return the number of substrings "aaaa" that can be formed from "a"
characters in the positions indicated by A.
*/
static T4 Count1(const Positions *A)
{
T4 N = A->N;
return N * (N-1) * (N-2) * (N-3) / (4*3*2*1);
}
/* Return the number of substrings "abab" that can be formed from "a"
characters in the positions indicated by A and "b" characters in the
positions indicated by B. A and B must be different.
*/
static T4 Count2(const Positions *A, const Positions *B)
{
// Exit early for trivial cases.
if (A->N < 2 || B->N < 2)
return 0;
/* Sum[i] will record the number of "ab" substrings that can be formed
with a "b" at the position in B->Position[b] or earlier.
*/
T2 Sum[Max];
T3 RunningSum = 0;
/* Iterate b through the indices of B->Position. While doing this, a is
synchronized to index to a corresponding place in A->Position.
*/
for (T1 a = 0, b = 0; b < B->N; ++b)
{
/* Advance a to index into A->Position where where A->Position[i]
first exceeds B->Position[b], or to the end if there is no such
spot.
*/
while (a < A->N && A->Position[a] < B->Position[b])
++a;
/* The number of substrings "ab" that can be formed using the "b" at
position B->Position[b] is a, the number of "a" preceding it.
Adding this to RunningSum produces the number of substrings "ab"
that can be formed using this "b" or an earlier one.
*/
RunningSum += a;
// Record that.
Sum[b] = RunningSum;
}
RunningSum = 0;
/* Iterate a through the indices of A->Position. While doing this, b is
synchronized to index to a corresponding place in B->Position.
*/
for (T1 a = 0, b = 0; a < A->N; ++a)
{
/* Advance b to index into B->Position where where B->Position[i]
first exceeds A->Position[a], or to the end if there is no such
spot.
*/
while (b < B->N && B->Position[b] < A->Position[a])
++b;
/* The number of substrings "abab" that can be formed using the "a"
at A->Position[a] as the second "a" in the substring is the number
of "ab" substrings that can be formed with a "b" before the this
"a" multiplied by the number of "b" after this "a".
That number of "ab" substrings is in Sum[b-1], if 0 < b. If b is
zero, there are no "b" before this "a", so the number is zero.
The number of "b" after this "a" is B->N - b.
*/
if (0 < b) RunningSum += (T3) Sum[b-1] * (B->N - b);
}
return RunningSum;
}
int main(void)
{
// Get the string length.
size_t length;
if (1 != scanf("%zu", &length))
{
fprintf(stderr, "Error, expected length in standard input.\n");
exit(EXIT_FAILURE);
}
// Skip blanks.
int c;
do
c = getchar();
while (c != EOF && isspace(c));
ungetc(c, stdin);
/* Create an array of Positions, one element for each character in the
allowed set.
*/
Positions P[L] = {{0}};
for (size_t i = 0; i < length; ++i)
{
c = getchar();
if (!islower(c))
{
fprintf(stderr,
"Error, malformed input, expected only lowercase letters in the string.\n");
exit(EXIT_FAILURE);
}
c -= 'a';
P[c].Position[P[c].N++] = i;
}
/* Count the specified substrings. i and j are iterated through the
indices of the allowed characters. For each pair different i and j, we
count the number of specified substrings that can be performed using
the character of index i as "a" and the character of index j as "b" as
described in Count2. For each pair where i and j are identical, we
count the number of specified substrings that can be formed using the
character of index i alone.
*/
T4 Sum = 0;
for (size_t i = 0; i < L; ++i)
for (size_t j = 0; j < L; ++j)
Sum += i == j
? Count1(&P[i])
: Count2(&P[i], &P[j]);
printf("%" PRIT4 "\n", Sum);
}
------------------------------------
En el peor de los casos, toda la cadenacontiene el mismo carácter y, en este caso, todos los índices son tales que 1 <= a < b < c < d <= N satisfará s[a] == s[c] && s[b] == s[d], por lo tanto, el contador sumaría n*(n-1)*(n-2)*(n-3) / 4!, que es O(n^4). En otras palabras, asumiendo que el proceso de conteo es uno por uno (usando counter++), no hay manera de hacer que la complejidad del tiempo en el peor de los casos sea mejor que O(n^4).
Dicho esto, este algoritmo se puede mejorar. Una mejora posible y muy importante es que si s[a] != s[c], no tiene sentido seguir comprobando todos los índices posibles b y d. user3777427 fue en esta dirección y se puede mejorar aún más de esta manera:
for(int a = 0; a < n-3; a++)
{
for(int c = a + 2; c < n-1; c++)
{
if(s[a] == s[c])
{
for(int b = a + 1; b < c; b++)
{
for(int d = c + 1; d < n; d++)
{
if(s[b] == s[d])
{
count++;
}
}
}
}
}
}
Editar:
Después de pensar un poco más, encontré una manera de reducir la complejidad del tiempo de peor pronóstico a O(n^3), usandoun histograma.
Primero, repasamos la matriz de caracteres una vez y completamos el histograma, de modo que el índice 'a' en el histograma contendrá el número de apariciones de 'a', el índice 'b' en el histograma contendrá el número de apariciones de 'b', etc.
Luego, usamos el histograma para eliminar la necesidad del bucle más interno (el bucle d), así:
int histogram1[256] = {0};
for (int i = 0; i < n; ++i)
{
++histogram1[(int) s[i]];
}
int histogram2[256];
for(int a = 0; a < n-3; a++)
{
--histogram1[(int) s[a]];
for (int i = 'a'; i <= 'z'; ++i)
{
histogram2[i] = histogram1[i];
}
--histogram2[(int) s[a+1]];
for (int c = a + 2; c < n-1; c++)
{
--histogram2[(int) s[c]];
for (int b = a + 1; b < c; b++)
{
if (s[a] == s[c])
{
count += histogram2[(int) s[b]];
}
}
}
}
3
Gracias, la mejora resuelve más casos de prueba en el tiempo señalado, pero el problema del límite de tiempo aún persiste, pero la sugerencia de cambiar el flujo de lla lógica es muy útil
- rohan84328/03/2021 a las 11:45
@rohan843 Edité y agregué una solución mejorada.
-Orielno28/03/2021 a las 12:11
@rohan843 Tuve un error en mi solución mejorada anteriormente. Ahora edité e ingresé un código que probé y me aseguré de que funcionara correctamente.
-Orielno28/03/2021 a las 13:08
------------------------------------
Problema
Quizás sea útil para pensar en el problema reconocer que se trata de un ejercicio de contar intervalos superpuestos. Por ejemplo, si consideramos que cada par de los mismos caracteres en la entrada marca los puntos finales de un intervalo medio abierto, entonces la pregunta es contar el número de pares de intervalos que se superponen sin que uno sea un subconjunto del otro.
AlgoritmoUna forma de abordar el problema comenzaría identificando y registrando todos los intervalos. Es sencillo hacer esto de una manera que permita agrupar los intervalos por punto final izquierdo y ordenar por punto final derecho dentro de cada grupo.Esto se desprende fácilmente de un escaneo ingenuo de la entrada con un nido de bucle de dos niveles.
Esta organización de los intervalos es conveniente tanto para reducir el espacio de búsqueda de superposiciones como para contarlas de manera más eficiente. En particular, se puede abordar el conteo así:
Para cada intervalo I, considere los grupos de intervalos para los puntos finales izquierdos estrictamente entre los puntos finales de I. Dentro de cada uno de los grupos considerados, realice una búsqueda binaria de un intervalo que tenga un extremo derecho mayor que el extremo derecho de I, o la posición donde se produciría dicho intervalo. Todos los miembros de ese grupo desde ese punto hasta el final satisfacen el criterio de superposición, así que suma ese número al recuento total. Análisis de complejidadLa lista de intervalos ordenados y los tamaños/límites de los grupos se pueden crear enCosto de O(n2) a través de un nido de bucle de dos niveles. Puede haber hasta n * (n - 1) intervalos en total, que ocurren cuando todos los caracteres de entrada son iguales, por lo que la lista requiere almacenamiento O(n2).
Los intervalos están agrupados en exactamente n - 1 grupos, algunos de los cuales pueden estar vacíos. Para cada intervalo (O(n2)), consideramos hasta n - 2 de ellos y realizamos una búsqueda binaria (O(log n)) en cada uno. Esto produce operaciones generales O(n3 log n).
Esa es una mejora algorítmica sobre el costo O(n4) de su algoritmo original, aunque aún está por verse si la complejidad asintótica mejorada manifiesta un mejor rendimiento para los tamaños de problemas específicos que se están probando.
1
¿Se vinculó a una página web que dice que hay una solución O(n log n), pero muestra un algoritmo O(n^3 log n)? Además, esa página web tiene una solución O(n log n) porque primero necesita ordenar los intervalos. Se nos proporciona una cadena con los intervalos esencialmente marcados (cada carácter comienza y termina un intervalo potencial en la posición donde se encuentra), por lo que no necesitamos una clasificación. Existe una solución O(n) (en complejidad práctica, contar multiplicaciones de tamaño de palabra y pasos individuales).
- Eric Postpischil28/03/2021 a las 18:21