Une chaîne binaire est une chaîne qui ne contient que des caractères tirés de 01 . Une chaîne binaire équilibrée est une chaîne binaire qui contient exactement autant de 0 s que 1 s.

On vous donne un entier positif n et un nombre arbitraire de masques, chacun de 2n caractères et ne contenant que des caractères tirés de 012 . Une chaîne binaire et un masque correspondent s'ils ont la même longueur et s'accordent sur le caractère dans chaque position où le masque n'a pas de 2 . Par exemple, le masque 011022 correspond aux chaînes binaires 011000 , 011001 , 011010 , 011011 .

Étant donné n et les masques en entrée (séparés par des retours à la ligne), vous devez sortir le nombre de chaînes binaires équilibrées distinctes qui correspondent à un ou plusieurs des masques.

Exemples

Contribution

3
111222
000112
122020
122210
102120

Raisonnement

• La seule chaîne binaire équilibrée correspondant à 111222 est 111000 .
• La seule chaîne binaire équilibrée correspondant à 000112 est 000111 .
• Les chaînes binaires équilibrées correspondant à 122020 sont 111000 (déjà comptées), 110010 et 101010 .
• Les chaînes binaires équilibrées correspondant à 122210 sont 110010 (déjà comptées), 101010 (déjà comptées) et 100110 .
• Les chaînes binaires équilibrées correspondant à 102120 sont 101100 et 100110 (déjà comptées).

La sortie doit donc être

6

Contribution

10
22222222222222222222

Raisonnement

• Il y a 20 choisissez 10 chaînes binaires équilibrées de longueur 20.

Production

184756

Gagnant

Le vainqueur sera celui qui calculera le plus rapidement les entrées de la compétition, en les traitant bien sûr de la même manière que n'importe quelle autre entrée. (J'utilise un code déterminé afin d'avoir un gagnant clair et d'éviter les cas où différentes entrées donneraient différents gagnants. Si vous pensez à une meilleure façon de trouver le code le plus rapide, dites-le-moi).

Participation à la compétition

http://pastebin.com/2Dg7gbfV

C

Si vous n'êtes pas sous Linux, ou si vous rencontrez des problèmes de compilation, vous devriez probablement supprimer le code de synchronisation ( clock_gettime).

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

long int binomial(int n, int m) {
  if(m > n/2) {
    m = n - m;
  }
  int i;
  long int result = 1;
  for(i = 0; i < m; i++) {
    result *= n - i;
    result /= i + 1;
  }
  return result;
}

typedef struct isct {
  char *mask;
  int p_len;
  int *p;
} isct;

long int mask_intersect(char *mask1, char *mask2, char *mask_dest, int n) {

  int zero_count = 0;
  int any_count = 0;
  int i;
  for(i = 0; i < n; i++) {
    if(mask1[i] == '2') {
      mask_dest[i] = mask2[i];
    } else if (mask2[i] == '2') {
      mask_dest[i] = mask1[i];
    } else if (mask1[i] == mask2[i]) {
      mask_dest[i] = mask1[i];
    } else {
      return 0;
    }
    if(mask_dest[i] == '2') {
      any_count++;
    } else if (mask_dest[i] == '0') {
      zero_count++;
    }
  }
  if(zero_count > n/2 || any_count + zero_count < n/2) {
    return 0;
  }
  return binomial(any_count, n/2 - zero_count);
}

int main() {

  struct timespec start, end;
  clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);

  int n;
  scanf("%d", &n);
  int nn = 2 * n;

  int m = 0;
  int m_max = 1024;

  char **masks = malloc(m_max * sizeof(char *));

  while(1) {
    masks[m] = malloc(nn + 1);
    if (scanf("%s", masks[m]) == EOF) {
      break;
    }
    m++;
    if (m == m_max) {
      m_max *= 2;
      masks = realloc(masks, m_max * sizeof(char *));
    }
  }

  int i = 1;
  int i_max = 1024 * 128;

  isct *iscts = malloc(i_max * sizeof(isct));

  iscts[0].mask = malloc(nn);
  iscts[0].p = malloc(m * sizeof(int));

  int j;
  for(j = 0; j < nn; j++) {
    iscts[0].mask[j] = '2';
  }
  for(j = 0; j < m; j++) {
    iscts[0].p[j] = j;
  }
  iscts[0].p_len = m;

  int i_start = 0;
  int i_end = 1;
  int sign = 1;

  long int total = 0;

  int mask_bin_len = 1024 * 1024;
  char* mask_bin = malloc(mask_bin_len);
  int mask_bin_count = 0;

  int p_bin_len = 1024 * 128;
  int* p_bin = malloc(p_bin_len * sizeof(int));
  int p_bin_count = 0;


  while (i_end > i_start) {
    for (j = i_start; j < i_end; j++) {
      if (i + iscts[j].p_len > i_max) {
        i_max *= 2;
        iscts = realloc(iscts, i_max * sizeof(isct));
      }
      isct *isct_orig = iscts + j;
      int x;
      int x_len = 0;
      int i0 = i;
      for (x = 0; x < isct_orig->p_len; x++) {
        if(mask_bin_count + nn > mask_bin_len) {
          mask_bin_len *= 2;
          mask_bin = malloc(mask_bin_len);
          mask_bin_count = 0;
        }
        iscts[i].mask = mask_bin + mask_bin_count;
        mask_bin_count += nn;
        long int count =
            mask_intersect(isct_orig->mask, masks[isct_orig->p[x]], iscts[i].mask, nn);
        if (count > 0) {
          isct_orig->p[x_len] = isct_orig->p[x];
          i++;
          x_len++;
          total += sign * count;
        }
      }
      for (x = 0; x < x_len; x++) {
        int p_len = x_len - x - 1;
        iscts[i0 + x].p_len = p_len;
        if(p_bin_count + p_len > p_bin_len) {
          p_bin_len *= 2;
          p_bin = malloc(p_bin_len * sizeof(int));
          p_bin_count = 0;
        }
        iscts[i0 + x].p = p_bin + p_bin_count;
        p_bin_count += p_len;
        int y;
        for (y = 0; y < p_len; y++) {
          iscts[i0 + x].p[y] = isct_orig->p[x + y + 1];
        }
      }
    }

    sign *= -1;
    i_start = i_end;
    i_end = i;

  }

  printf("%lld\n", total);

  clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);

  int seconds = end.tv_sec - start.tv_sec;
  long nanoseconds = end.tv_nsec - start.tv_nsec;
  if(nanoseconds < 0) {
    nanoseconds += 1000000000;
    seconds--;
  }

  printf("%d.%09lds\n", seconds, nanoseconds);
  return 0;
}

Exemples de cas:

robert@unity:~/c/se-mask$ gcc -O3 se-mask.c -lrt -o se-mask
robert@unity:~/c/se-mask$ head testcase-long
30
210211202222222211222112102111220022202222210122222212220210
010222222120210221012002220212102220002222221122222220022212
111022212212022222222220111120022120122121022212211202022010
022121221020201212200211120100202222212222122222102220020212
112200102110212002122122011102201021222222120200211222002220
121102222220221210220212202012110201021201200010222200221002
022220200201222002020110122212211202112011102220212120221111
012220222200211200020022121202212222022012201201210222200212
210211221022122020011220202222010222011101220121102101200122
robert@unity:~/c/se-mask$ ./se-mask < testcase-long
298208861472
0.001615834s
robert@unity:~/c/se-mask$ head testcase-hard
8
0222222222222222
1222222222222222
2022222222222222
2122222222222222
2202222222222222
2212222222222222
2220222222222222
2221222222222222
2222022222222222
robert@unity:~/c/se-mask$ ./se-mask < testcase-hard
12870
3.041261458s
robert@unity:~/c/se-mask$ 

(Les temps sont pour un processeur i7-4770K à 4,1 GHz.) Attention, testcase-hardutilise environ 3-4 Go de mémoire.

C'est à peu près une implémentation de la méthode d'inclusion-exclusion proposée par blutorange, mais faite de manière à gérer les intersections de n'importe quelle profondeur. Le code tel qu'il est écrit consacre beaucoup de temps à l'allocation de mémoire et sera encore plus rapide une fois que j'optimiserai la gestion de la mémoire.

J'ai réduit d'environ 25% testcase-hard, mais les performances sur l'original ( testcase-long) sont à peu près inchangées, car il n'y a pas beaucoup d'allocation de mémoire. Je vais régler un peu plus avant de l'appeler: je pense que je pourrais peut-être aussi obtenir une amélioration de 25% à 50% testcase-long.

Mathematica

Une fois que j'ai remarqué qu'il s'agissait d'un problème #SAT, j'ai réalisé que je pouvais utiliser la fonction intégrée de Mathematica SatisfiabilityCount:

AbsoluteTiming[
 (* download test case *)
 input = Map[FromDigits, 
   Characters[
    Rest[StringSplit[
      Import["http://pastebin.com/raw.php?i=2Dg7gbfV", 
       "Text"]]]], {2}]; n = Length[First[input]];
 (* create boolean function *)
 bool = BooleanCountingFunction[{n/2}, n] @@ Array[x, n] && 
   Or @@ Table[
     And @@ MapIndexed[# == 2 || Xor[# == 1, x[First[#2]]] &, i], {i, 
      input}];
 (* count instances *)
 SatisfiabilityCount[bool, Array[x, n]]
]

Production:

{1.296944, 298208861472}

Cela représente 298 208 861 472 masques en 1,3 seconde (i7-3517U @ 1,9 GHz), y compris le temps passé à télécharger le cas de test à partir de pastebin.

rubis, assez rapide, mais cela dépend de l'entrée

Accélérez maintenant d'un facteur 2 ~ 2,5 en passant des chaînes aux entiers.

Usage:

cat <input> | ruby this.script.rb

Par exemple.

mad_gaksha@madlab ~/tmp $ ruby c50138.rb < c50138.inp2
number of matches: 298208861472
took 0.05726237 s

Le nombre de correspondances pour un seul masque est facilement calculé par le coefficient binomial. Ainsi, par exemple, il 122020faut 3 2s remplis, 1 0et 2 1. Il existe donc nCr(3,2)=nCr(3,1)=3!/(2!*1!)=3différentes chaînes binaires correspondant à ce masque.

Une intersection entre n masques m_1, m_2, ... m_n est un masque q, de sorte qu'une chaîne binaire s ne correspond à q que si elle correspond à tous les masques m_i.

Si nous prenons deux masques m_1 et m_2, son intersection est facilement calculée. Définissez simplement m_1 [i] = m_2 [i] si m_1 [i] == 2. L'intersection entre 122020et 111222est 111020:

122020 (matched by 3 strings, 111000 110010 101010)
111222 (matched by 1 string, 111000)
111020 (matched by 1 string, 111000)

Les deux masques individuels sont appariés par 3 + 1 = 4 chaînes, le masque d'intersection est apparié par une chaîne, il y a donc 3 + 1-1 = 3 chaînes uniques correspondant à l'un ou aux deux masques.

J'appellerai N (m_1, m_2, ...) le nombre de chaînes correspondant à tous les m_i. En appliquant la même logique que ci-dessus, nous pouvons calculer le nombre de chaînes uniques correspondant à au moins un masque, donné par le principe d'exclusion d'inclusion et voir également ci-dessous, comme ceci:

N(m_1) + N(m_2) + ... + N(m_n) - N(m_1,m_2) - ... - N(m_n-1,m_n) + N(m_1,m_2,m_3) + N(m_1,m_2,m_4) + ... N(m_n-2,m_n-1,m_n) - N(m_1,m_2,m_3,m_4) -+ ...

Il existe de très nombreuses combinaisons de prises, disons 30 masques sur 200.

Donc, cette solution fait l'hypothèse qu'il n'y a pas beaucoup d'intersections d'ordre élevé des masques d'entrée, c'est-à-dire. la plupart des n-tuples de n> 2 masques n'auront aucune correspondance commune.

Utilisez le code ici, le code à ideone peut être obsolète.

• Cas de test 1 : nombre de correspondances: 6
• Cas de test 2 : nombre de correspondances: 184756
• Cas de test 3 : nombre de correspondances: 298208861472
• Cas de test 4 : nombre de correspondances: 5

J'ai ajouté une fonction remove_duplicatesqui peut être utilisée pour prétraiter l'entrée et supprimer les masques de m_isorte que toutes les chaînes qui y correspondent correspondent également à un autre masque m_j., Pour l'entrée actuelle, cela prend en fait plus de temps car il n'y a pas de tels masques (ou pas beaucoup) , la fonction n'est donc pas encore appliquée aux données dans le code ci-dessous.

Code:

# factorial table
FAC = [1]
def gen_fac(n)
  n.times do |i|
    FAC << FAC[i]*(i+1)
  end
end

# generates a mask such that it is matched by each string that matches m and n
def diff_mask(m,n)
  (0..m.size-1).map do |i|
    c1 = m[i]
    c2 = n[i]
    c1^c2==1 ? break : c1&c2
  end
end

# counts the number of possible balanced strings matching the mask
def count_mask(m)
  n = m.size/2
  c0 = n-m.count(0)
  c1 = n-m.count(1)
  if c0<0 || c1<0
    0
  else
    FAC[c0+c1]/(FAC[c0]*FAC[c1])
  end
end

# removes masks contained in another
def remove_duplicates(m)
  m.each do |x|
    s = x.join
    m.delete_if do |y|
      r = /\A#{s.gsub(?3,?.)}\Z/
      (!x.equal?(y) && y =~ r) ? true : false
    end
  end
end

#intersection masks of cn masks from m.size masks
def mask_diff_combinations(m,n=1,s=m.size,diff1=[3]*m[0].size,j=-1,&b)
  (j+1..s-1).each do |i|
    diff2 = diff_mask(diff1,m[i])
    if diff2
      mask_diff_combinations(m,n+1,s,diff2,i,&b) if n<s
      yield diff2,n
    end
  end
end

# counts the number of balanced strings matched by at least one mask
def count_n_masks(m)
  sum = 0
  mask_diff_combinations(m) do |mask,i|
    sum += i%2==1 ? count_mask(mask) : -count_mask(mask)
  end
  sum
end

time = Time.now

# parse input
d = STDIN.each_line.map do |line|
  line.chomp.strip.gsub('2','3')
end
d.delete_if(&:empty?)
d.shift
d.map!{|x|x.chars.map(&:to_i)}

# generate factorial table
gen_fac([d.size,d[0].size].max+1)

# count masks
puts "number of matches: #{count_n_masks(d)}"
puts "took #{Time.now-time} s"

C'est ce qu'on appelle le principe d'exclusion de l'inclusion, mais avant que quelqu'un ne me le montre, j'avais ma propre preuve, alors voilà. Cependant, faire quelque chose vous fait du bien.

Considérons le cas de 2 masques, appelons ensuite 0et 1, d'abord. Nous prenons chaque chaîne binaire équilibrée et la classons en fonction du ou des masques auxquels elle correspond. c0est le nombre de ceux qui correspondent uniquement au masque 0, c1le nombre de ceux qui correspondent uniquement 1, c01ceux qui correspondent au masque 0et 1.

Soit s0la somme numérique du nombre de correspondances pour chaque masque (elles peuvent se chevaucher). Soit s1la somme du nombre de correspondances pour chaque paire (2 combinaisons) de masques. Soit s_ila somme du nombre de correspondances pour chaque (i + 1) combinaison de masques. Le nombre de correspondances de n-masques est le nombre de chaînes binaires correspondant à tous les masques.

S'il y a n masques, la sortie souhaitée est la somme de tous c, c'est-à-dire. c = c0+...+cn+c01+c02+...+c(n-2)(n-1)+c012+...+c(n-3)(n-2)(n-1)+...+c0123...(n-2)(n-1). Ce que le programme calcule est la somme alternée de tous s, c'est-à-dire. s = s_0-s_1+s_2-+...+-s_(n-1). Nous voulons le prouver s==c.

n = 1 est évident. Considérons n = 2. Compter toutes les correspondances de mask 0donne c0+c01(le nombre de chaînes ne correspondant qu'à 0 + celles correspondant à la fois à 0et 1), compter toutes les correspondances de 1donne c1+c02. Nous pouvons illustrer cela comme suit:

0: c0 c01
1: c1 c10

Par définition, s0 = c0 + c1 + c12. s1est le nombre total de correspondances de chaque combinaison de 2 [0,1], c'est-à-dire. tous uniqye c_ijs. Gardez cela à l'esprit c01=c10.

s0 = c0 + c1 + 2 c01
s1 = c01
s = s0 - s1 = c0 + c1 + c01 = c

Ainsi s=cpour n = 2.

Considérons maintenant n = 3.

0  : c0 + c01 + c02 + c012
1  : c1 + c01 + c12 + c012
2  : c2 + c12 + c02 + c012
01 : c01 + c012
02 : c02 + c012
12 : c12 + c012
012: c012

s0 = c0 + c1 + c2 + 2 (c01+c02+c03) + 3 c012
s1 = c01 + c02 + c12 + 3 c012
s2 = c012

s0 = c__0 + 2 c__1 + 3 c__2
s1 =          c__1 + 3 c__2
s2 =                   c__2

s = s0 - s1 + s2 = ... = c0 + c1 + c2 + c01 + c02 + c03 + c012 = c__0 + c__1 + c__2 = c

Ainsi s=cpour n = 3. c__ireprésente le de tous les cs avec (i + 1) indices, par exemple c__1 = c01pour n = 2 et c__1 = c01 + c02 + c12pour n == 3.

Pour n = 4, un modèle commence à émerger:

0:   c0 + c01 + c02 + c03 + c012 + c013 + c023 + c0123
1:   c1 + c01 + c12 + c13 + c102 + c103 + c123 + c0123
2:   c2 + c02 + c12 + c23 + c201 + c203 + c213 + c0123
3:   c3 + c03 + c13 + c23 + c301 + c302 + c312 + c0123

01:  c01 + c012 + c013 + c0123
02:  c02 + c012 + c023 + c0123
03:  c03 + c013 + c023 + c0123
12:  c11 + c012 + c123 + c0123
13:  c13 + c013 + c123 + c0123
23:  c23 + c023 + c123 + c0123

012:  c012 + c0123
013:  c013 + c0123
023:  c023 + c0123
123:  c123 + c0123

0123: c0123

s0 = c__0 + 2 c__1 + 3 c__2 + 4 c__3
s1 =          c__1 + 3 c__2 + 6 c__3
s2 =                   c__2 + 4 c__3
s3 =                            c__3

s = s0 - s1 + s2 - s3 = c__0 + c__1 + c__2 + c__3 = c

Ainsi s==cpour n = 4.

En général, nous obtenons des coefficients binomiaux comme celui-ci (↓ est i, → est j):

   0  1  2  3  4  5  6  .  .  .

0  1  2  3  4  5  6  7  .  .  .
1     1  3  6  10 15 21 .  .  .
2        1  4  10 20 35 .  .  .
3           1  5  15 35 .  .  .
4              1  6  21 .  .  .
5                 1  7  .  .  .
6                    1  .  .  . 
.                       .
.                          .
.                             .

Pour voir cela, considérez cela pour certains iet j, il y a:

• x = ncr (n, i + 1): combinaisons C pour l'intersection de (i + 1) masque sur n
• y = ncr (ni-1, ji): pour chaque combinaison C ci-dessus, il existe y différentes combinaisons pour l'intersection de (j + 2) masques parmi ceux contenant C
• z = ncr (n, j + 1): différentes combinaisons pour l'intersection de (j + 1) masques sur n

Comme cela peut sembler déroutant, voici la définition appliquée à un exemple. Pour i = 1, j = 2, n = 4, cela ressemble à ceci (cf. ci-dessus):

01:  c01 + c012 + c013 + c0123
02:  c02 + c012 + c023 + c0123
03:  c03 + c013 + c023 + c0123
12:  c11 + c012 + c123 + c0123
13:  c13 + c013 + c123 + c0123
23:  c23 + c023 + c123 + c0123

Donc ici x = 6 (01, 02, 03, 12, 13, 23), y = 2 (deux c avec trois indices pour chaque combinaison), z = 4 (c012, c013, c023, c123).

Au total, il y a des x*ycoefficients cavec des indices (j + 1), et il y en a zdifférents, donc chacun se produit x*y/zfois, que nous appelons le coefficient k_ij. Par simple algèbre, on obtient k_ij = ncr(n,i+1) ncr(n-i-1,j-i) / ncr(n,j+1) = ncr(j+1,i+1).

Donc, l'indice est donné par k_ij = nCr(j+1,i+1)Si vous vous souvenez de toutes les définitions, tout ce que nous devons montrer est que la somme alternée de chaque colonne donne 1.

La somme alternée s0 - s1 + s2 - s3 +- ... +- s(n-1)peut ainsi s'exprimer comme:

s_j = c__j * ∑［(-1)^(i+j) k_ij］ for i=0..n-1
     = c__j * ∑［(-1)^(i+j) nCr(j+1,i+1)］ for i=0..n-1
     = c__j * ∑［(-1)^(i+j) nCr(j+1,i)］｛i=0..n｝ - (-1)^0 nCr(j+1,0)
     = (-1)^j c__j

s   = ∑［(-1)^j  s_j］ for j = 0..n-1
    = ∑［(-1)^j (-1)^j c__j)］ for j=0..n-1
    = ∑［c__j］ for j=0..n-1
    = c

Ainsi s=cpour tout n = 1,2,3, ...

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <gsl/gsl_combination.h>

int main (int argc, char *argv[]) {

    printf ("reading\n");
    char buffer[100];
    gets(buffer);
    char n = atoi(buffer);

    char *masks[1000];
    masks[0] = malloc(2 * n * sizeof(char));
    char c,nrows,j,biggestzerorun,biggestonerun,currentzerorun,currentonerun = 0;

    while ((c = getchar()) && c != EOF) {
        if (c == '\n') {
            nrows++;
            if (currentonerun > biggestonerun) {
                biggestonerun = currentonerun;
            }
            if (currentzerorun > biggestzerorun) {
                biggestzerorun = currentzerorun;
            }
            j=currentonerun=currentzerorun=0;
            masks[nrows] = malloc(2 * n * sizeof(char));
        } else if (c == '0') {
            masks[nrows][j++] = 1;
            currentzerorun++;
            if (currentonerun > biggestonerun) {
                biggestonerun = currentonerun;
            }
            currentonerun=0;
        } else if (c == '1') {
            masks[nrows][j++] = 2;
            currentonerun++;
            if (currentzerorun > biggestzerorun) {
                biggestzerorun = currentzerorun;
            }
            currentonerun=0;
        } else if (c == '2') {
            masks[nrows][j++] = 3;
            currentonerun++;
            currentzerorun++;
        }
    }
    if (currentonerun > biggestonerun) {
        biggestonerun = currentonerun;
    }
    if (currentzerorun > biggestzerorun) {
        biggestzerorun = currentzerorun;
    }

    printf("preparing combinations\n");

    int nmatches=0;

    gsl_combination *combination = gsl_combination_calloc(2*n, n);

    printf("entering loop:\n");

    do {
        char vector[2*n];
        char currentindex, previousindex;
        currentonerun = 0;
        memset(vector, 1, 2*n);


        // gsl_combination_fprintf (stdout, combination, "%u ");
        // printf(": ");

        for (char k=0; k<n; k++) {
            previousindex = currentindex;
            currentindex = gsl_combination_get(combination, k);
            if (k>0) {
                if (currentindex - previousindex == 1) {
                    currentonerun++;
                    if (currentonerun > biggestonerun) {
                        goto NEXT;
                    }
                } else {
                    currentonerun=0;
                    if (currentindex - previousindex > biggestzerorun) {
                        goto NEXT;
                    }
                }
            }
            vector[currentindex] = 2;
        }

        for (char k=0; k<=nrows; k++) {
            char ismatch = 1;
            for (char l=0; l<2*n; l++) {
                if (!(vector[l] & masks[k][l])) {
                    ismatch = 0;
                    break;
                }
            }
            if (ismatch) {
                nmatches++;
                break;
            }
        }

        NEXT: 1;

    } while (
        gsl_combination_next(combination) == GSL_SUCCESS
    );

    printf ("RESULT: %i\n", nmatches);

    gsl_combination_free(combination);
    for (; nrows>=0; nrows--) {
        free(masks[nrows]);
    }
}

Bonne chance pour obtenir la grande contribution à exécuter sur cela - il faudra probablement toute la nuit pour passer à travers environ. 60 ^ 30 permutations! Peut-être qu'un ensemble de données de taille intermédiaire pourrait être une bonne idée?