fork download
copy 
  1. from random import sample
  2.  
  3. def reader(inFile):
  4.     N = inFile.getInt()
  5.     prerequisites = inFile.getInts()
  6.     letters = inFile.readline()
  7.     M = inFile.getInt()
  8.     coolWords = inFile.getWords()
  9.     return (N,prerequisites,letters,coolWords)
  10.  
  11. def solver((N,prerequisites,letters,words)):
  12.     # For any course, find out which courses directly depend on it. 
  13.     # Also get a list of basic courses.
  14.     directDependencies = {i:[] for i in xrange(1,N+1)}
  15.     basics = []
  16.     for i in xrange(1,N+1):
  17.         if prerequisites[i-1] == 0:
  18.             basics.append(i)
  19.         else:
  20.             directDependencies[prerequisites[i-1]].append(i)
  21.  
  22.     # Get the number of courses which directly or indirectly depend on each course.
  23.     numDependents = {}
  24.     def getNumDependents(i):
  25.         tot = 1
  26.         for j in directDependencies[i]:
  27.             tot += getNumDependents(j)
  28.         numDependents[i] = tot
  29.         return tot    
  30.     for i in basics:
  31.         getNumDependents(i)
  32.  
  33.     # Sample from uniform random distribution of orderings
  34.     def placeDependentsAndReturnRemaining(sampleSoFar, i, available):
  35.         # The nodes that are used by i and its (direct or indirect) dependencies are 
  36.         # equally likely to be any set of the same size, given that there are no
  37.         # interdependencies with other nodes still to place
  38.         dependencyLocations = sample(available, numDependents[i])
  39.         # i must be the first of these to be placed
  40.         w = min(dependencyLocations)
  41.         others = [z for z in dependencyLocations if z != w]
  42.         sampleSoFar[w] = letters[i-1]
  43.         for j in directDependencies[i]:
  44.             others = placeDependentsAndReturnRemaining(sampleSoFar, j, others)
  45.         dependencyLocations = set(dependencyLocations)
  46.         return [k for k in available if k not in dependencyLocations]
  47.     def randomSample():
  48.         sampleSoFar = ["" for i in xrange(N)]
  49.         remaining = range(N)
  50.         for j in basics:
  51.             remaining = placeDependentsAndReturnRemaining(sampleSoFar, j, remaining)
  52.         return "".join(sampleSoFar)
  53.  
  54.     # If you a coin flip with probability p N times, the number of heads has
  55.     # mean Np and standard deviation sqrt(Np(1-p))
  56.  
  57.     # Thus, the estimated probability will be p with standard deviation sqrt(p(1-p)/N)
  58.  
  59.     # If we sample 10000 times, the standard deviation is at most 0.005, so being 0.03 wrong
  60.     # is 6 standard deviations out, and we would rarely expect to see such an error in our 
  61.     # 500 (5 words x 100 test cases) tests.
  62.  
  63.     counts = [0 for i in words]
  64.     sampleSize = 10000
  65.     for i in xrange(sampleSize):
  66.         w = randomSample()
  67.         for p in xrange(len(words)):
  68.             if words[p] in w:
  69.                 counts[p] += 1
  70.  
  71.     return " ".join(str(float(count)/sampleSize) for count in counts)
  72.  
  73. if __name__ == "__main__":
  74.     from GCJ import GCJ
  75.     GCJ(reader, solver, "/Users/luke/gcj/2016/3/", "b").run()
  76.  
Runtime error #stdin #stdout #stderr 0.02s 11448KB
comments (?)
stdin
copy 
2
2
0 1
CJ
4
CJ C D JC
3
0 1 0
BAA
3
AA AAB ABA
stdout
copy 
Standard output is empty
stderr
copy 
Traceback (most recent call last):
  File "prog.py", line 74, in <module>
ImportError: No module named GCJ
https://ideone.com/CjB58d
language:
Python (cpython 2.7.16)
created:
9 years ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!