• Martin Thoma
  • Home
  • Categories
  • Tags
  • Archives
  • Support me

Google Code Jam 2012 – Round 1C 2012

Contents

  • Google Code Jam 2012 – Round 1C 2012
    • Diamond Inheritance
    • See also

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

  • Wikipedia: Google Code Jam
  • Google Code Jam Statistics

Published

Mai 6, 2012
by Martin Thoma

Category

Code

Tags

  • competition 5
  • Google 9
  • Google Code Jam 8
  • Programming 52
  • Python 141

Contact

  • Martin Thoma - A blog about Code, the Web and Cyberculture
  • E-mail subscription
  • RSS-Feed
  • Privacy/Datenschutzerklärung
  • Impressum
  • Powered by Pelican. Theme: Elegant by Talha Mansoor