Diogo Böhm

Howdy! This time, problems started getting more and more complex, and that’s good, because I like the challenge! The next problem is Get to Work:

You work for a company that has E employees working in town T. There are N towns in the area where the employees live. You want to ensure that everyone will be able to make it to work. Some of the employees are drivers and can drive P passengers. A capacity of P == 1 indicates that the driver can only transport themselves to work. You want to ensure that everyone will be able to make it to work and you would like to minimize the number of cars on the road.

You want to calculate the number of cars on the road, with these requirements:

• Every employee can get to town T.
• The only way an employee may travel between towns is in a car belonging to an employee.
• Employees can only take rides from other employees that live in the same town.
• The minimum number of cars is used.

Find whether it is possible for everyone to make it to work, and if it is, how many cars will end up driving to the office.

Whoa, that’s way more complex than the other problems, but still, not that hard! What we need to do is: check who are drivers and passengers for each town (since they can only help same town buddies), if the total capacity of cars from a town is inferior to the number of passengers, the problem cannot be solved and so, reported as “IMPOSSIBLE”. If we can carry everyone, start filling the cars from the “minivan” (can carry more passengers) to the “mini cooper”. 😀 That way we can make sure there are fewer cars on the road.

Some rough, but commented, and validated (!) python code follows:

for case in range(1,int(raw_input())+1):                  # For all test cases
    town_len, office = map(int, raw_input().split(" "))   # Get amount of towns and office

    carriers = [[] for x in xrange(town_len)]             # Create new lists for every town
    capacities = town_len * [0]                           # Initialize "capacity of transportation"
    payload = town_len * [0]                              # Initialize "cargo" for each town

    for i in range(int(raw_input())):                     # Get and go through employee list
        town, capacity = map(int, raw_input().split(" ")) # Get the current employee info
        if town == office:                                # If employee is from office town
            continue                                      #   No need to commute, ignore

        town -= 1                                         # Adjust "town" to zero-based index
        payload[town] += 1                                # Employee needs to commute, count

        if capacity != 0:                                 # If employee has a car
            capacities[town] += capacity                  # Add to our capacities for the town
            carriers[town].append(capacity)               # Append its car capacity

    resultStr = ""                                        # Create our result string

    for i in range(town_len):                             # For all towns
        if capacities[i] < payload[i]:                    # If we can't carry everyone
            resultStr = "IMPOSSIBLE "                     #   declare it impossible, give up
            break;

        cars = 0                                          # We can carry, start with 0 cars
        carriers[i].sort()                                # Sort and reverse the car list
        carriers[i].reverse()
        for car in carriers[i]:                           # So we can start from the bigger ones
            if (payload[i] <= 0):                         # If we're carrying everybody already
                break                                     #  we're done for this town

            payload[i] -= car                             # Else, fill a car, report as being used
            cars += 1

        resultStr += str(cars)+" "                        # Add this town filled vehicles

    print "Case #%d: %s" % (case, resultStr[:-1])         # Report results, remove last space

As the last problem, the same can be told about this code. There are many ways to improve its performance, but this way it can already solve the large inputs in an instant. Bitbangers apart, it solves the problem and everybody gets happy. Also, I think it is quite clear to understand, even more with the comments. 🙂 Bye!