Двоичная строка является строкой , которая содержит только символы , взятые из 01 . Сбалансирован двоичная строка является двоичной строкой , которая содержит ровно столько 0 сек , как 1 с.

Вам дается положительное целое число n и произвольное количество масок, каждая из которых имеет длину 2n символов и содержит только символы, взятые из 012 . Двоичная строка и маска совпадают, если они имеют одинаковую длину и согласуются с символом в каждой позиции, где маска не имеет 2 . Например , маска 011022 спичек бинарные струн 011000 , 011001 , 011010 , 011011 .

Учитывая n и маски в качестве входных данных (разделенных символами новой строки), вы должны вывести количество различных сбалансированных двоичных строк, которые соответствуют одной или нескольким маскам.

Примеры

вход

3
111222
000112
122020
122210
102120

аргументация

• Единственная сбалансированная двоичная строка, совпадающая с 111222, это 111000 .
• Единственная сбалансированная двоичная строка, совпадающая с 000112, это 000111 .
• Сбалансированные двоичные строки , соответствующие 122020 являются 111000 (уже подсчитан), 110010 и 101010 .
• Сбалансированные двоичные строки, соответствующие 122210 : 110010 (уже посчитано), 101010 (уже посчитано) и 100110 .
• Сбалансированные двоичные строки, соответствующие 102120, равны 101100 и 100110 (уже учтены).

Таким образом, вывод должен быть

6

вход

10
22222222222222222222

аргументация

• Есть 20 выбрать 10 сбалансированных двоичных строк длиной 20.

Вывод

184756

победитель

Победителем будет тот, кто посчитает входные данные соревнования быстрее всего, конечно же, обработав их так же, как и любой другой вход. (Я использую определенный код, чтобы иметь явного победителя и избегать случаев, когда разные входные данные давали бы разных победителей. Если вы думаете о лучшем способе найти самый быстрый код, скажите мне об этом).

Конкурсный вклад

http://pastebin.com/2Dg7gbfV

С

Если вы не работаете в Linux или у вас другие проблемы с компиляцией, вам, вероятно, следует удалить код синхронизации ( 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;
}

Примеры случаев:

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$ 

(Время для процессора i7-4770K с частотой 4,1 ГГц.) Будьте осторожны, testcase-hardиспользуйте около 3-4 ГБ памяти.

Это в значительной степени реализация метода включения-исключения, разработанного blutorange, но сделанного так, что он будет обрабатывать пересечения любой глубины. Написанный код тратит много времени на выделение памяти и станет еще быстрее, когда я оптимизирую управление памятью.

Я сэкономил около 25% testcase-hard, но производительность оригинала ( testcase-long) практически не изменилась, так как там не происходит большого выделения памяти. Я собираюсь настроиться немного больше, прежде чем позвонить: думаю, я тоже смогу добиться улучшения на 25-50% testcase-long.

Mathematica

Как только я заметил, что это проблема #SAT, я понял, что могу использовать встроенное в 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]]
]

Вывод:

{1.296944, 298208861472}

Это 298 208 861 472 маски за 1,3 секунды (i7-3517U @ 1,9 ГГц), включая время, потраченное на загрузку тестового примера из pastebin.

Рубин, довольно быстро, но это зависит от ввода

Теперь ускорение в 2 ~ 2,5 раза происходит за счет перехода от строк к целым числам.

Применение:

cat <input> | ruby this.script.rb

Например.

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

Количество совпадений для одной маски легко рассчитывается по биномиальному коэффициенту. Так, например, 122020необходимо 3 2с заполнены, 1 0и 2 1. Таким образом, есть nCr(3,2)=nCr(3,1)=3!/(2!*1!)=3разные двоичные строки, соответствующие этой маске.

Пересечение между n масками m_1, m_2, ... m_n является маской q, так что двоичная строка s соответствует q только тогда, когда она соответствует всем маскам m_i.

Если взять две маски m_1 и m_2, их пересечение легко вычисляется. Просто установите m_1 [i] = m_2 [i], если m_1 [i] == 2. Пересечение между 122020и 111222является 111020:

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

Две отдельные маски соответствуют 3 + 1 = 4 строкам, маска пересечения соответствует одной строке, таким образом, есть 3 + 1-1 = 3 уникальных строки, соответствующих одной или обеим маскам.

Я назову N (m_1, m_2, ...) количество строк, соответствующих всем m_i. Применяя ту же логику, что и выше, мы можем вычислить количество уникальных строк, сопоставленных хотя бы с одной маской, заданной принципом исключения включения, и также см. Ниже, например, так:

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) -+ ...

Есть много, много, много комбинаций взятия, скажем, 30 масок из 200.

Таким образом, это решение предполагает, что существует не так много пересечений высших порядков входных масок, т.е. большинство n-кортежей с n> 2 масками не будут иметь общих совпадений.

Используйте код здесь, код в ideone может быть устаревшим.

• Тестовый пример 1 : количество совпадений: 6
• Контрольный пример 2 : количество совпадений: 184756
• Контрольный пример 3 : количество совпадений: 298208861472
• Контрольный пример 4 : количество совпадений: 5

Я добавил функцию, remove_duplicatesкоторую можно использовать для предварительной обработки ввода и удаления масок m_i, чтобы все соответствующие ему строки также соответствовали другой маске m_j. Для текущего ввода это на самом деле занимает больше времени, поскольку таких масок нет (или их не много). , так что функция не применяется к данным еще в коде ниже.

Код:

# 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"

Это называется принципом исключения включения, но до того, как кто-то указал мне на это, у меня было собственное доказательство, так что вот так. Делать что-то самостоятельно - это здорово.

Давайте рассмотрим случай 2 масок, звоните потом 0и 1, во-первых. Мы берем каждую сбалансированную двоичную строку и классифицируем ее в зависимости от того, к какой маске она подходит. c0Число тех , которые соответствуют лишь маскируют 0, c1Nunber из тех , которые соответствуют только 1, c01те , что маски матч 0и 1.

Позвольте s0быть число сумма количества совпадений для каждой маски (они могут перекрываться). Позвольте s1быть сумма количества совпадений для каждой пары (2-комбинация) масок. Позвольте s_iбыть сумма количества совпадений для каждой (я + 1) комбинации масок. Количество совпадений n-масок - это количество двоичных строк, соответствующих всем маскам.

Если существует n масок, желаемый результат является суммой всех c, т.е. c = c0+...+cn+c01+c02+...+c(n-2)(n-1)+c012+...+c(n-3)(n-2)(n-1)+...+c0123...(n-2)(n-1), То, что программа вычисляет, является чередующейся суммой всех s, т.е. s = s_0-s_1+s_2-+...+-s_(n-1), Мы хотим доказать это s==c.

п = 1 очевидно. Рассмотрим n = 2. Подсчет всех совпадений по маске 0дает c0+c01(количество строк, совпадающих только с 0 + совпадающих с обоими 0и 1), подсчитывая все совпадения по 1маскам c1+c02. Мы можем проиллюстрировать это следующим образом:

0: c0 c01
1: c1 c10

По определению s0 = c0 + c1 + c12. s1сумма совпадений каждой 2-комбинации [0,1], т.е. все uniqye c_ijс. Имейте это в виду c01=c10.

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

Таким образом, s=cдля n = 2.

Теперь рассмотрим 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

Таким образом, s=cдля n = 3. c__iпредставляет все cs с (i + 1) индексами, например, c__1 = c01для n = 2 и c__1 = c01 + c02 + c12для n == 3.

Для n = 4 шаблон начинает появляться:

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

Таким образом, s==cдля n = 4.

В общем, мы получаем биномиальные коэффициенты, подобные этому (↓ это i, → это 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  .  .  . 
.                       .
.                          .
.                             .

Чтобы увидеть это, рассмотрим, что для некоторых iи jесть:

• x = ncr (n, i + 1): комбинации C для пересечения маски (i + 1) из n
• y = ncr (ni-1, ji): для каждой комбинации C выше есть y различных комбинаций для пересечения масок (j + 2) из ​​тех, которые содержат C
• z = ncr (n, j + 1): различные комбинации для пересечения масок (j + 1) из n

Как это может показаться запутанным, вот определение, примененное к примеру. Для i = 1, j = 2, n = 4 это выглядит так (см. Выше):

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

Так что здесь x = 6 (01, 02, 03, 12, 13, 23), y = 2 (два c с тремя индексами для каждой комбинации), z = 4 (c012, c013, c023, c123).

В общем, есть x*yкоэффициенты cс (j + 1) индексами, и есть zразные, поэтому каждый x*y/zраз встречается , что мы называем коэффициентом k_ij. По простой алгебре получаем k_ij = ncr(n,i+1) ncr(n-i-1,j-i) / ncr(n,j+1) = ncr(j+1,i+1).

Таким образом, индекс дается выражением: k_ij = nCr(j+1,i+1)Если вы помните все определения, все, что нам нужно показать, это то, что переменная сумма каждого столбца дает 1.

Таким образом, переменная сумма s0 - s1 + s2 - s3 +- ... +- s(n-1)может быть выражена как:

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

Таким образом, s=cдля всех n = 1,2,3, ...

С

#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]);
    }
}

Удачи в получении большого вклада для этого - вероятно, потребуется около ночи, чтобы пройти ок. 60 ^ 30 перестановок! Может быть, набор данных промежуточного размера может быть хорошей идеей?