Una cadena binaria es una cadena que contiene solo caracteres extraídos de 01 . Una cadena binaria balanceada es una cadena binaria que contiene exactamente tantos 0 s como 1 s.
Se le da un número entero positivo n y un número arbitrario de máscaras, cada una de las cuales tiene 2n caracteres de longitud y contiene solo caracteres extraídos de 012 . Una cadena binaria y una máscara coinciden si tiene la misma longitud y concuerda con el personaje en cada posición donde la máscara no tiene un 2 . Por ejemplo, la máscara 011022 coincide con las cadenas binarias 011000 , 011001 , 011010 , 011011 .
Dado n y las máscaras como entrada (separadas por nuevas líneas), debe generar el número de cadenas binarias equilibradas distintas que coinciden con una o más de las máscaras.
Ejemplos
Entrada
3
111222
000112
122020
122210
102120
Razonamiento
- La única cadena binaria equilibrada que coincide con 111222 es 111000 .
- La única cadena binaria equilibrada que coincide con 000112 es 000111 .
- Las cadenas binarias balanceadas que coinciden con 122020 son 111000 (ya contadas), 110010 y 101010 .
- Las cadenas binarias balanceadas que coinciden con 122210 son 110010 (ya contadas), 101010 (ya contadas) y 100110 .
- Las cadenas binarias balanceadas que coinciden con 102120 son 101100 y 100110 (ya contadas).
Entonces la salida debería ser
6
Entrada
10
22222222222222222222
Razonamiento
- Hay 20 elegir 10 cadenas binarias balanceadas de longitud 20.
Salida
184756
Ganador
El ganador será el que calcule la entrada de la competencia más rápido, por supuesto, tratándola de la misma manera que lo haría con cualquier otra entrada. (Utilizo un código determinado para tener un ganador claro y evitar casos en los que diferentes entradas darían ganadores diferentes. Si piensas en una mejor manera de encontrar el código más rápido, dímelo).
Aporte de competencia
fuente
Respuestas:
C
Si no está en Linux o tiene problemas para compilar, probablemente debería eliminar el código de sincronización (
clock_gettime
).Casos de ejemplo:
(Los tiempos son para una CPU i7-4770K a 4.1 GHz.) Tenga cuidado,
testcase-hard
usa alrededor de 3-4 GB de memoria.Esto es más o menos una implementación del método blutorange de inclusión-exclusión creado, pero hecho para que maneje las intersecciones de cualquier profundidad.
El código tal como está escrito gasta mucho tiempo en la asignación de memoria, y se volverá aún más rápido una vez que optimice la administración de la memoria.Ahorré alrededor de un 25%
testcase-hard
, pero el rendimiento en el original (testcase-long
) prácticamente no ha cambiado, ya que no hay mucha asignación de memoria allí. Voy a sintonizar un poco más antes de llamarlo: creo que también podría obtener una mejora del 25% al 50%testcase-long
.Mathematica
Una vez que noté que este era un problema de #SAT, me di cuenta de que podía usar el incorporado de Mathematica
SatisfiabilityCount
:Salida:
Eso es 298,208,861,472 máscaras en 1.3 segundos (i7-3517U @ 1.9 GHz), incluido el tiempo dedicado a descargar el caso de prueba de pastebin.
fuente
testcase-hard
puede completarse muy rápidamente si su código busca máscaras que se puedan combinar. Si su código hace esto, elimine todas las demás líneas (por lo que solo/^2*02*$/
quedan los casos). No creo que ese caso pueda optimizarse.rubí, bastante rápido, pero depende de la entrada
Ahora acelere por un factor de 2 ~ 2.5 cambiando de cadenas a enteros.
Uso:
P.ej.
El número de coincidencias para una sola máscara se calcula fácilmente por el coeficiente binomial. Entonces, por ejemplo,
122020
necesita 32
s llenos, 10
y 21
. Por lo tanto, haynCr(3,2)=nCr(3,1)=3!/(2!*1!)=3
diferentes cadenas binarias que coinciden con esta máscara.Una intersección entre n máscaras m_1, m_2, ... m_n es una máscara q, de modo que una cadena binaria s coincide con q solo si coincide con todas las máscaras m_i.
Si tomamos dos máscaras m_1 y m_2, su intersección se calcula fácilmente. Simplemente configure m_1 [i] = m_2 [i] si m_1 [i] == 2. La intersección entre
122020
y111222
es111020
:Las dos máscaras individuales se combinan con 3 + 1 = 4 cadenas, la máscara de intersección se corresponde con una cadena, por lo tanto, hay 3 + 1-1 = 3 cadenas únicas que coinciden con una o ambas máscaras.
Llamaré a N (m_1, m_2, ...) el número de cadenas que coinciden con todos m_i. Aplicando la misma lógica que la anterior, podemos calcular el número de cadenas únicas que coinciden con al menos una máscara, dada por el principio de exclusión de inclusión y ver a continuación también, así:
Hay muchas, muchas, muchas combinaciones de tomar, digamos 30 máscaras de 200.
Por lo tanto, esta solución supone que no existen muchas intersecciones de orden superior de las máscaras de entrada, es decir. La mayoría de las n-tuplas de n> 2 máscaras no tendrán coincidencias comunes.
Use el código aquí, el código de ideone puede estar desactualizado.
Agregué una función
remove_duplicates
que se puede usar para preprocesar la entrada y eliminar máscaras dem_i
modo que todas las cadenas que coincidan también coincidan con otra máscaram_j
., Para la entrada actual, esto realmente lleva más tiempo ya que no hay tales máscaras (o no hay muchas) , por lo que la función aún no se aplica a los datos en el código a continuación.Código:
Esto se llama el principio de exclusión de inclusión, pero antes de que alguien me lo señalara tenía mi propia prueba, así que aquí va. Sin embargo, hacer algo por ti mismo se siente genial.
Consideremos el caso de 2 máscaras, llame entonces
0
y1
, primero. Tomamos todas las cadenas binarias balanceadas y las clasificamos de acuerdo con qué máscara (s) coinciden.c0
es el número de aquellos que solo coinciden con la máscara0
,c1
el número de aquellos que solo coinciden1
,c01
los que coinciden con la máscara0
y1
.Sea
s0
la suma numérica del número de coincidencias para cada máscara (pueden superponerse). Seas1
la suma de la cantidad de coincidencias para cada par (2 combinaciones) de máscaras. Seas_i
la suma del número de coincidencias para cada combinación de máscaras (i + 1). El número de coincidencias de n-máscaras es el número de cadenas binarias que coinciden con todas las máscaras.Si hay n máscaras, la salida deseada es la suma de todas
c
, es decir.c = c0+...+cn+c01+c02+...+c(n-2)(n-1)+c012+...+c(n-3)(n-2)(n-1)+...+c0123...(n-2)(n-1)
. Lo que calcula el programa es la suma alterna de todoss
, es decir.s = s_0-s_1+s_2-+...+-s_(n-1)
. Queremos probar esos==c
.n = 1 es obvio. Considere n = 2. Contando todos los partidos de la máscara
0
dac0+c01
(el número de cadenas que coinciden sólo 0 + coincidente tanto los0
e1
), contando todos los partidos del1
dac1+c02
. Podemos ilustrar esto de la siguiente manera:Por definición,
s0 = c0 + c1 + c12
.s1
es el número total de coincidencias de cada combinación de 2[0,1]
, es decir. todos uniqyec_ij
s. Ten en cuenta esoc01=c10
.Así
s=c
para n = 2.Ahora considere n = 3.
Así
s=c
para n = 3.c__i
representa el de todos losc
s con (i + 1) índices, por ejemplo,c__1 = c01
para n = 2 yc__1 = c01 + c02 + c12
para n == 3.Para n = 4, un patrón comienza a emerger:
Así
s==c
para n = 4.En general, obtenemos coeficientes binomiales como este (↓ es i, → es j):
Para ver esto, considere eso para algunos
i
yj
, hay:Como eso puede sonar confuso, aquí está la definición aplicada a un ejemplo. Para i = 1, j = 2, n = 4, se ve así (cf. arriba):
Entonces, aquí x = 6 (01, 02, 03, 12, 13, 23), y = 2 (dos c con tres índices para cada combinación), z = 4 (c012, c013, c023, c123).
En total, hay
x*y
coeficientesc
con índices (j + 1), y hayz
diferentes, por lo que cada uno ocurrex*y/z
veces, lo que llamamos coeficientek_ij
. Por álgebra simple, obtenemosk_ij = ncr(n,i+1) ncr(n-i-1,j-i) / ncr(n,j+1) = ncr(j+1,i+1)
.Entonces, el índice está dado por
k_ij = nCr(j+1,i+1)
Si recuerda todas las definiciones, todo lo que necesitamos mostrar es que la suma alterna de cada columna da 1.La suma alterna
s0 - s1 + s2 - s3 +- ... +- s(n-1)
se puede expresar como:Así,
s=c
para todos n = 1,2,3, ...fuente
0011 < 2211
,0022 < 0222
. Creo que esto hace que los grupos no sean más grandes2*n
, aunque todavía es demasiado grande en el peor de los casos.unifying two masks
el términounion
tiene sentido para mí y puedo definirlo de esa manera, pero tienes razón, en aras del entendimiento mutuo que he criticado. @ Agawa001 ¿Puedes ser más específico? Además, si tiene alguna buena idea para hacer esto más rápido, siéntase libre de usar cualquier idea de esta respuesta para su programa / respuesta. Por ahora, es lo suficientemente rápido para el caso de prueba grande, y si se hace con subprocesos múltiples, debería tomar <0.1s, que está por debajo de cualquier medición / comparación significativa, por lo que se necesitan casos de prueba más difíciles.C
Buena suerte para obtener el gran aporte para ejecutar esto: probablemente tomará toda la noche superar aprox. 60 ^ 30 permutaciones! ¿Quizás un conjunto de datos de tamaño intermedio podría ser una buena idea?
fuente