Unable to find solution for a practice problem in codechef

Question

Here is the problem from code chef :

A set of N dignitaries have arrived in close succession at Delhi and are awaiting transportation to Roorkee to participate in the inaugural ceremony of Cognizance. Being big sponsors of Cognizance, it has been deemed unsuitable by the organizing team to arrange for more than one dignitary to travel in a single vehicle. In addition, each dignitary has specified his preferred modes of transport to the organizing team well in advance. Consequently, the organizing team has drawn up a list specifying the set of acceptable transport mechanisms for each dignitary. Given such a list of preferences and the list of N available vehicles at Delhi, you need to specify if an allocation of vehicles can be so made that everyone’s preferences are satisfied. Each dignitary takes up atmost 1 transportation unit. Input Format: Line 1: N - The number of dignitaries. 1 <= N <= 100 Line 2-N+1: The names of the dignitaries – 1 per line. Line N+2 to 2*N+1: The names of the vehicles, 1 per line Line N+2 onwards: K – The size of the preference list for each dignitary, followed by K space separated names of acceptable transport means. K <= N Note: None of the names will have a length > 100.

Output Format:

Line 1: Yes/No.

Sample Input:

4

Divye

Rohit

Akshat

Parth

Scorpio

BMW

Ford

Chevrolet

1 BMW

1 Ford

2 Scorpio Chevrolet

1 Ford

Sample Output:

No

Link to the problem : http://www.codechef.com/problems/INSOMB6/

Here is the code i wrote :

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

It gives correct output for sample input. But it fails somewhere. It will be great if you guys can point out a situation where this code fails!

Answer 1

One first error (I doubt it's blocking you):

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

It's never correct to use is / is not to test immutables (such as numbers): use = or != instead. The code you've written may accidentally work as an implementation-based artifact in versions of Python that "cache" small integers, but it's still wrong;-). Similarly for the len(cars) is 0 later.

Using a variable named error to indicate the lack of error is peculiar and confusing (though technically not wrong code;-).

The algorithmic bug is: all you're checking is that each car is liked by exactly 1 dignitary. This is very different from "there exists a 1-1 assignment of cars to dignitaries satisfying the preferences". For example, if all dignitaries liked all cars, you'd say "No" (because you remove all cars on the first leg of the loop, then get a ValueError the second time and thus set error to False) while most obviously the answer must be "Yes"! So, rethink the algorithm from scratch. Consider using sets or dicts, they may make your life easier (they won't change the algorithm but may make it easier to see/conceptualize).

Answer 2

Consider the test case:

2
A
B
1
2
2 1 2
1 1

The answer is yes because person A can use car 2, and person B will use car 1.

I believe your solution will put person A in car 1, then be unable to place person 2.

If you want a hint, this problem reduces to whether there exists a perfect matching of a bipartite graph.