Решение задачи программирования: Аппарат от Kattis

Question

Я пытаюсь решить описанную проблему с аппаратом here. И у меня есть решение, но это занимает больше 2 секунд, что ограничение времени. Я пытался оптимизировать свой код для скорости, но не могу получить его с 2-секундным лимитом.

import sys 
import math 

for line in sys.stdin: 

    line = line.strip("\n").split(" ") 
    numSwitches = int(line[0]) 
    numPics = int(line[1]) 

    wiring = {} 
    inValid = False 
    for i in range(numPics): 
     if (inValid): 
      break 
     x = sys.stdin.readline().strip("\n") 
     f_x = sys.stdin.readline().strip("\n") 

     x_ones = 0 
     f_x_ones = 0 

     digit = 0 
     for i in range(numSwitches): 
      if f_x[i]=='1': 
       digit += 2**(numSwitches-i-1) 
       f_x_ones += 1 

     for switch in range(numSwitches): 
      if (x[switch]=='1'): 
       x_ones += 1 
       if not (switch in wiring.keys()): 
        wiring[switch] = digit 
       else: 
        wiring[switch] &= digit 

     if x_ones != f_x_ones: 
      inValid = True 
      break 

    if not inValid: 
     for i in wiring.values(): 
      if i==0: 
       inValid = True 
       break 

    for possibilities in set(wiring.values()): 
     frequency = wiring.values().count(possibilities) 
     if frequency>1: 
      oneBits = 0 
      while (possibilities>0): 
       oneBits += (possibilities%2==1) 
       possibilities /= 2 
      if oneBits < frequency: 
       inValid = True 
       break 

    if not inValid: 
     print math.factorial(numSwitches-numPics)%1000003 
    else: 
     print 0 

Я ищу предложения о том, как я должен был обратиться к проблеме или внести свой вклад в то, как я могу оптимизировать свой текущий код.

Примечание: Рассмотрим следующий тестовый случай:

3 2 
110 
011 
011 
011 

Мой код находит, что является недействительным следующим образом. Во-первых, после первой фотографии (110, 011). проводка словарь получает присвоены следующие ключи и значения:

wiring[0] = 011 
wiring[1] = 011 

Это означает, что первый и второй переключатель может загораться либо второй или третий свет. После встречи с второй фотографией (011, 011). проводка обновляется следующим образом:

wiring[1] = 011 & 011 = 011 
wiring[2] = 011 

Теперь заметим, что состояние проводки указывает на то, что все три переключателя может загораться либо второй и третий свет. Это непоследовательность, поскольку 3 переключателя должны загорать три огня, здесь у нас есть три переключателя, освещающие 2 огня.

Answer 1

Я думаю, что это может быть решением, но я не уверен, что я могу объяснить более завтра

import numpy as np 
from operator import mul 

def apparatus(n, m, x, y): 
    if not m: 
     return np.math.factorial(n) % 1000003 
    result = 1 
    tmp = np.matrix([False] * x.shape[1]) 

    for i in xrange(x.shape[1]): 
     if tmp[0, i]: 
      continue 
     tmp0 = np.prod(x[:, i] == x, 0) 
     tmp1 = np.prod(x[:, i] == y, 0) 
     if np.sum(tmp1) != np.sum(tmp0): 
      return 0 
     result *= np.math.factorial(np.sum(tmp1)) 
     result %= 1000003 
     tmp += tmp1 

    return result 

x = np.matrix([[True, True, False]]) 
y = np.matrix([[False, True, True]]) 
print apparatus(3, 1, x, y) 

x = np.matrix([[True, False, False, False], [False, False, False, False]]) 
y = np.matrix([[True, False, False, False], [False, False, True, False]]) 
print apparatus(4, 2, x, y) 

print apparatus(1000, 0, [], [])