USACO Revegetate - Version 2

USACO 2019 February Contest, Silver¶

Problem 3. The Great Revegetation¶

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

In [1]:

# Data Set 11
#
# 4 4
# D 1 2
# S 2 3
# D 3 4
# D 1 4

In [2]:

fin = open ('11.in', 'r')
fout = open ('revegetate.out', 'w')
N,M  = map(int, fin.readline().split())
print("N M",N,M)

N M 4 4

In [3]:

# cut-and-paste Union-Find code
PARENT = [i for i in range(N+1)]

def find_with_path_compression(x):
    if x!=PARENT[x]:
        PARENT[x]=find_with_path_compression(PARENT[x])
    return PARENT[x]

def union(x,y):
    a = find_with_path_compression(x)
    b = find_with_path_compression(y)
    PARENT[a]=b
    return

In [4]:

samedict = dict()  # lookup pastures that must be same as key pasture
diffdict = dict()  # lookup pastures that must be different from key pasture

for i in range(M):  
    i,j,k = fin.readline().split()
    p1=int(j)
    p2=int(k)
    union(p1,p2)   # assemble the connected components
    
    # Load up the Same/Different dictionaries
    if i == 'S':
        if p1 in diffdict:
            if p2 in diffdict[p1]:
                nosolution = True
                break
        if p2 in diffdict:
            if p1 in diffdict[p2]:
                nosolution = True
                break
        if p1 in samedict:
            samedict[p1].add(p2)
        else:
            samedict[p1]=set([p2])
        if p2 in samedict:
            samedict[p2].add(p1)
        else:
            samedict[p2]=set([p1])
            
    if i == 'D':
        if p1 in samedict:
            if p2 in samedict[p1]:
                nosolution = True
                break
        if p2 in samedict:
            if p1 in samedict[p2]:
                nosolution = True
                break         
        if p1 in diffdict:
            diffdict[p1].add(p2)
        else:
            diffdict[p1]=set([p2])
        if p2 in diffdict:
            diffdict[p2].add(p1)
        else:
            diffdict[p2]=set([p1])
            
print(samedict)           
print(diffdict)

{2: {3}, 3: {2}}
{1: {2, 4}, 2: {1}, 3: {4}, 4: {1, 3}}

In [5]:

# Count the connected components
countset = set()
for i in range(1,N+1):
    countset.add(find_with_path_compression(i))

print("connected components",len(countset))

connected components 1

In [6]:

nosolution = False
seedtype = [0]*(N+1)  # assign each pasture to seedtype 1 or 2. check there is a valid solution
for x in countset:    # loop through connected components
    BFS = [x]
    seedtype[x]=1     # assign the parent node of the connected component to seed type 1
    # now do a BFS from the parent node, assign seed types and look for conflicts
    while len(BFS)>0 and nosolution==False:
        p = BFS.pop()
        if p in samedict:
            Slist = samedict[p]
            for q in Slist:
                if seedtype[q]!=seedtype[p] and seedtype[q]!=0:
                    nosolution=True
                    break
                elif seedtype[q]==0:
                    seedtype[q]=seedtype[p]
                    BFS.append(q)
        if p in diffdict:
            Dlist = diffdict[p]
            for q in Dlist:
                if seedtype[q]==seedtype[p]:
                    nosolution=True
                    break
                elif seedtype[q]==0:
                    seedtype[q]=seedtype[p]%2+1
                    BFS.append(q)
                    
print("nosolution?",nosolution)

nosolution? True

In [7]:

# Data Set 11 has NO SOLUTION
if nosolution:
    ans = '0'    
else:    
    ans = '1'
    for i in range(len(countset)):
        ans += '0'
print("ans",ans)
fout.write(str(ans)+"\n")
fout.close()

ans 0