PEG Online Judge Coding

Question

Я решаю проблему на PEG Online Judge, которая является местом, где вы можете решить множество проблем для практики и развлечений.

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

Это проблема капореджима: http://wcipeg.com/problem/capos

Вы можете использовать несколько языков, чтобы решить эту проблему. Я решил использовать Python (хотя я также закодировал его на C++). Существует 12 наборов данных, которые использует судья при тестировании кода. Мой код проходит 11/12. Я понятия не имею, почему я не могу пройти последний тест и надеюсь, что кто-то может мне помочь.

Я думаю, что это определенная проблема с разбиением на разделы, и я решаю ее с помощью метода поиска по ширине. Набор данных проблем невелик, поэтому он не выходит из-под контроля.

Вот мое решение:

import sys 
import copy 

class SearchState(): 
    def __init__(self, label, crews): 
     self.label = label 
     self.crews = crews 

    def __repr__(self): 
     return "State: %s: %s" % (self.label, str(self.crews)) 


def crewsSoldierCanBeIn(s, crews, grudges): 
    ''' 
     For a given soldier and a list of crews and grudges, 
     return the crews the soldier an go in 
    ''' 

    noGrudgeCrews = [] 
    for i, crew in enumerate(crews): 
     conflict = False 
     for c in crew: 
      if [s, c] in grudges or [c, s] in grudges: 
       conflict = True 
       break 
     if not conflict: 
      noGrudgeCrews.append(i) 

    return noGrudgeCrews  


def solve(numSoldiers, grudges): 
    ''' 
     Put each soldier in a crew, output min no. of crews and who is in them 
    ''' 

    crews = [[1]] 
    numStates = 0 
    states = [SearchState(numStates, crews)] 

    for s in range(2, numSoldiers+1): 
     newStates = [] 
     for state in states: 
      possibleCrews = crewsSoldierCanBeIn(s, state.crews, grudges) 
      if len(possibleCrews) > 0: 
       for crew in possibleCrews: 
        numStates += 1 
        newCrews = copy.deepcopy(state.crews) 
        newCrews[crew].append(s) 
        newStates.append(SearchState(numStates, newCrews)) 
      else: 
       numStates += 1 
       newCrews = copy.deepcopy(state.crews) 
       newCrews.append([s]) 
       newStates.append(SearchState(numStates, newCrews)) 

     states = copy.deepcopy(newStates) 


    minNumCrews = 1000000 
    minState = -1 
    for i, state in enumerate(states): 
     if len(state.crews) < minNumCrews: 
      minNumCrews = len(state.crews) 
      minState = i 


    print(len(states[minState].crews)) 
    for crew in states[minState].crews: 
     for s in crew: 
      print("%d " % (s), end = "") 
     print() 

def readInData(f): 

    numSoldiers, numGrudges = map(int, f.readline().strip().split()) 
    grudges = [] 
    for _ in range(numGrudges): 
     grudges.append(list(map(int, f.readline().strip().split()))) 

    return numSoldiers, grudges 


def main(): 

    # Read in the data 
    f = sys.stdin 

    numSoldiers, grudges = readInData(f) 

    solve(numSoldiers, grudges) 

if __name__ == '__main__': 
    main() 

Answer 1

Итак, я наконец-то решил эту проблему.

В принципе, мне нужно было использовать подход DFS, он не может быть действительно решен (с учетом памяти и временных ограничений онлайн-судьи) через BFS.

Преимущество DFS двоякое: 1) Я могу быстро найти решение (не лучшее решение) и использовать его для обрезки дерева, чтобы избавиться от кучи частичных решений, которые никогда не будут хорошими, и 2) Очень мало памяти.

Так что DFS быстрее и использует меньше памяти для этой проблемы.