Martin Thoma

Google Code Jam 2012 – Round 1C 2012

· by

Contents

4230 tried the first problem, but only 3189 people are listed in the scoreboard.

  • Problem 1 (Diamond Inheritance):
    • Small Set: 3077/4230 users (73%)
    • Large Set: 2387/3044 users (78%)
  • Problem 2 (Out of Gas):
    • Small Set: 471/766 users (61%)
    • Large Set: 73/253 users (29%)
  • Problem 3 (Box Factory):
    • Small Set: 1071/1810 users (59%)
    • Large Set: 308/788 users (39%)

Diamond Inheritance

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import psyco

psyco.full()

testcases = input()


def line2intlist(line):
    list = line.split(" ")
    numbers = [int(x) for x in list]
    return numbers


def getAnswer(classDict, N):
    for startPoint in range(1, N):
        reachable = [startPoint]
        justAppended = [startPoint]
        while len(justAppended) > 0:
            newJustAppended = []
            for node in justAppended:
                for new in classDict[node]:
                    if new in reachable:
                        return "Yes"
                    else:
                        newJustAppended.append(new)
                        reachable.append(new)
            justAppended = newJustAppended
    return "No"


for i in range(0, testcases):
    N = input()
    classDict = {}
    for classNr in range(1, N + 1):
        liste = line2intlist(raw_input())
        classDict[classNr] = liste[1:]
    print("Case #%i: %s" % (i + 1, getAnswer(classDict, N)))

See also