Wormholes

USACO 2013 December Contest, Bronze¶

Problem 3. Wormholes¶

http://usaco.org/index.php?page=viewproblem2&cpid=360

In [1]:

fin = open ('wormhole.in','r')

N = int(fin.readline())
X = [-1]*N
Y = [-1]*N
pair_lookup = [-1]*N
neighbor_lookup = [-1]*N
count=0

for i in range(N):
    a,b = map(int,fin.readline().split())
    X[i]=a
    Y[i]=b
    
for i in range(N):
    print(X[i],Y[i])

0 0
1 0
1 1
0 1

In [2]:

for i in range(N):
    for j in range(N):
        if Y[j]==Y[i] and X[j]>X[i]: 
            if neighbor_lookup[i] == -1 or X[j]-X[i] < X[neighbor_lookup[i]]-X[i]:
                    neighbor_lookup[i] = j
    
print(neighbor_lookup)

[1, -1, -1, 2]

In [3]:

def cycle_exists():
    for i in range(N):
        next_wormhole=i
        for j in range(N):
            print(X[next_wormhole],Y[next_wormhole],"-> ",end="")
            if next_wormhole>-1:
                next_wormhole=neighbor_lookup[pair_lookup[next_wormhole]]
            else:
                print("cycle broken")
                break
                
        if next_wormhole > -1:
            return True
        
    return False

In [4]:

def gen_all_pairs(lst):
    
    global count
    
    if len(lst) == 2:
        pair_lookup[lst[0]]=lst[1]
        pair_lookup[lst[1]]=lst[0]
        print("\n",pair_lookup)
        if cycle_exists():
            count+=1
        return
    
    for i in range(1,len(lst)):
        pair_lookup[lst[0]]=lst[i]
        pair_lookup[lst[i]]=lst[0]
        
        remaining_elements = lst[1:i]+lst[i+1:]
        gen_all_pairs(remaining_elements)               
    return

testlist=list(range(N))
gen_all_pairs(testlist)
print(pair_lookup, "\n\ncycle_count=",count)

 [1, 0, 3, 2]
0 0 -> 0 1 -> cycle broken
1 0 -> 1 0 -> 1 0 -> 1 0 -> 
 [2, 3, 0, 1]
0 0 -> 0 1 -> cycle broken
1 0 -> 1 1 -> 1 0 -> 1 1 -> 
 [3, 2, 1, 0]
0 0 -> 1 1 -> 0 1 -> cycle broken
1 0 -> 0 1 -> cycle broken
1 1 -> 0 1 -> cycle broken
0 1 -> 1 0 -> 0 1 -> cycle broken
[3, 2, 1, 0] 

cycle_count= 2

In [5]:

fout = open('wormhole.out','w')
fout.write(str(count)+'\n')      
fout.close()