Невозможно найти решение для практической проблемы в codechef

Question

Вот проблема от кода шеф-повара:

Группа из N высокопоставленных лиц прибыла в Дели в порядке очереди и ожидает доставки в Рурки для участия в церемонии открытия Cognizance. Будучи крупными спонсорами Cognizance, команда организаторов посчитала неприемлемой организацию более чем одного сановника для поездки на одном транспортном средстве. Кроме того, каждый сановник заблаговременно определил предпочитаемые виды транспорта для команды организаторов. Следовательно, команда организаторов составила список с указанием набора приемлемых транспортных механизмов для каждого сановника. Учитывая такой список предпочтений и список из N доступных автомобилей в Дели, вам необходимо указать, можно ли выделить автомобили таким образом, чтобы все предпочтения были удовлетворены. Каждый сановник занимает максимум 1 транспортную единицу. Формат ввода: Строка 1: N - количество сановников. 1 <= N <= 100 Строка 2-N + 1: имена сановников - 1 на строку. Строка N + 2 до 2 * N + 1: названия транспортных средств, 1 на строку Строка N + 2 и далее: K - размер списка предпочтений для каждого сановника, за которым следует K разделенных пробелами названий допустимых транспортных средств. K <= N Примечание: ни одно из имен не будет иметь длину> 100.

Формат вывода:

Строка 1: Да / Нет.

Пример ввода:

4

Divye

Рохит

Akshat

Parth

Скорпион

BMW

Форд

Chevrolet

1 BMW

1 Ford

2 Скорпион Шевроле

1 Ford

Пример вывода:

нет

Нет

Ссылка на проблему: http://www.codechef.com/problems/INSOMB6/

Вот код, который я написал:

#!/usr/bin/python

ceo = []
cars = []
error = True
n = int(raw_input())
for i in range(n):
 ceo.append(raw_input().lower())
for i in range(n):
 cars.append(raw_input().lower())

for i in range(n):
 test = raw_input().lower().split()
 if int(test[0]) is not len(test[1:]):
  error = False
  continue
 if test[0] != '0':
  for i in test[1:]:

   try :
    cars.remove(i)
   except ValueError :
    error = False

if error and  len(cars) is 0 :
 print "Yes"
else : 
 print "No"

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

Answer 1

Одна первая ошибка (я сомневаюсь, что она блокирует вас):

if int(test[0]) is not len(test[1:]):

Никогда не правильно использовать is / is not для проверки неизменяемых (например, чисел): используйте вместо этого = или !=. Код, который вы написали, может случайно работать как основанный на реализации артефакт в версиях Python, которые «кэшируют» маленькие целые числа, но это все равно неправильно ;-). Аналогично для len(cars) is 0 позже.

Использование переменной с именем error для указания на отсутствие ошибки является своеобразным и запутанным (хотя технически это не неправильный код; -).

Алгоритмическая ошибка: все, что вы проверяете, так это то, что каждая машина нравится только одному сановнику. Это очень отличается от «присваивания высокопоставленных лиц 1-1 автомобилей, удовлетворяющих предпочтениям». Например, если всем сановникам понравились все машины, вы бы сказали «Нет» (поскольку вы удаляете все машины на первом участке цикла, затем получаете ValueError во второй раз и, таким образом, устанавливаете error в False), пока Очевидно, ответ должен быть «Да»! Итак, переосмыслите алгоритм с нуля. Подумайте об использовании наборов или диктовок, они могут облегчить вашу жизнь (они не изменят алгоритм, но могут упростить понимание / концептуализацию).

Answer 2

Рассмотрим контрольный пример:

2
A
B
1
2
2 1 2
1 1

Ответ - да, потому что человек A может использовать автомобиль 2, а человек B - автомобиль 1.

Я полагаю, ваше решение посадит человека А в машину 1, а затем не сможет посадить человека 2.

Если вы хотите подсказку, эта проблема сводится к тому, существует ли идеальное соответствие двудольного графа.