Posts: 259 Liked others: 46 Was liked: 116
Rank: 2d
Solomon wrote:
Also, kudos to bernds for not only solving Building Dependencies, but also being the fastest!
Thanks I was surprised by this one because I felt I wasn't doing anything really special to be honest. Incremental Double Free Strings too, by the way https://open.kattis.com/problems/idf/statistics Still puzzled how to get near the top in Power Strings.
Posts: 149 Liked others: 276 Was liked: 49
Rank: 3d
KGS: 3d
DGS: 3d
OGS: 3d
Problem A: Flood-fill twice, similar to Solomon's solution. The first time I used recursive version and got RTE, so I changed it to non-recursive version (bernds also suggested it) using a BFS-style queue and got AC. (Should've defined a queue of pairs instead of two queues to make it shorter)
Code:
from collections import deque
tmp = input().split()
m = int(tmp[0]) n = int(tmp[1])
a = []
for i in range(m): a.append(list(input()))
qx = deque() qy = deque()
for j in range(n): if a[0][j] == '0': a[0][j] = '2' qx.append(0) qy.append(j) if a[m-1][j] == '0': a[m-1][j] = '2' qx.append(m-1) qy.append(j)
for i in range(m): if a[i][0] == '0': a[i][0] = '2' qx.append(i) qy.append(0) if a[i][n-1] == '0': a[i][n-1] = '2' qx.append(i) qy.append(n-1)
while (len(qx) > 0): x = qx.popleft() y = qy.popleft() if (x > 0 and a[x-1][y] == '0'): a[x-1][y] = '2' qx.append(x-1) qy.append(y) if (x < m-1 and a[x+1][y] == '0'): a[x+1][y] = '2' qx.append(x+1) qy.append(y) if (y > 0 and a[x][y-1] == '0'): a[x][y-1] = '2' qx.append(x) qy.append(y-1) if (y < n-1 and a[x][y+1] == '0'): a[x][y+1] = '2' qx.append(x) qy.append(y+1)
ans = 0
for i in range(m): for j in range(n): if a[i][j] == '1': if (i == 0 or a[i-1][j] == '2'): ans += 1 if (j == 0 or a[i][j-1] == '2'): ans += 1 if (i == m-1 or a[i+1][j] == '2'): ans += 1 if (j == n-1 or a[i][j+1] == '2'): ans += 1
print(ans)
Problem B:
Minimum Spanning Tree. I used Prim's algorithm with a priority queue, and then cut the edges with the minimum costs until there are exactly s clusters remaining. Got 2 WAs because I forgot to comment out the debugging information...
Code:
from collections import deque import queue as Q from math import sqrt
class Edge(object): #class Edge: def __init__(self, a, b, length): self.a = a self.b = b self.length = length def __lt__(self, other): return self.length < other.length
c = int(input())
for cc in range(c): tmp = input().split() s = int(tmp[0]) p = int(tmp[1])
x = [] y = [] for i in range(p): tmp = input().split() x.append(int(tmp[0])) y.append(int(tmp[1]))
q = Q.PriorityQueue()
for i in range(1, p): q.put(Edge(0, i, (x[0]-x[i])*(x[0]-x[i])+(y[0]-y[i])*(y[0]-y[i])))
v = set() v.add(0)
q_ans = Q.PriorityQueue() q_ans.put(0)
for i in range(1, p): while (not q.empty()): e = q.get() if not e.b in v: v.add(e.b) ans = e.length q_ans.put(e.length) #print("%d %d %f" % (e.a, e.b, e.length)) for j in range(p): if not j in v: q.put(Edge(e.b, j, (x[e.b]-x[j])*(x[e.b]-x[j])+(y[e.b]-y[j])*(y[e.b]-y[j]))) break u = p - s + 1 while (not q_ans.empty() and u > 0): u -= 1 ans = q_ans.get()
print("%.2f" % sqrt(ans))
Problem C: Didn't realize it could be formulated as a flood-fill problem but solved it with a BFS-style queue
Code:
from collections import deque
c = int(input())
for cc in range(c): tmp = input().split() n = int(tmp[0]) m = int(tmp[1]) l = int(tmp[2])
edges = [[] for i in range(n+1)] #print(edges) down = [False] * (n+1)
for j in range(m): tmp = input().split() edges[int(tmp[0])].append(int(tmp[1])) #print("%d: " % int(tmp[0])) #print(edges[int(tmp[0])])
ans = 0 q = deque() for k in range(l): x = int(input()) if (not down[x]): q.append(x) down[x] = True ans += 1
while (len(q) > 0): x = q.popleft() for k in range(len(edges[x])): if (not down[edges[x][k]]): q.append(edges[x][k]) down[edges[x][k]] = True ans += 1
print(ans)
Problem D: Two passes. First pass is to cluster the nodes with '=' and map them to new nodes, and second pass is the traditional topological sort to find out if there're remaining nodes with parents.
Code:
from collections import deque #import queue as Q #from math import sqrt
tmp = input().split() n = int(tmp[0]) m = int(tmp[1])
edge = [[] for i in range(n)] equal = [[] for i in range(n)] p = [0 for i in range(n)]
for i in range(m): tmp = input().split() a = int(tmp[0]) b = int(tmp[2]) if (tmp[1] == "="): equal[a].append(b) equal[b].append(a) elif (tmp[1] == "<"): edge[a].append(b) p[b] += 1 else: edge[b].append(a) p[a] += 1
k = 0 name = [0 for i in range(n)] idlists = [] pp = [] visited = set() for i in range(n): if (not i in visited): q = deque() visited.add(i) q.append(i) idlist = [i] psum = p[i] while (len(q) > 0): cur = q.popleft() name[cur] = k for j in range(len(equal[cur])): if (not equal[cur][j] in visited): visited.add(equal[cur][j]) q.append(equal[cur][j]) idlist.append(equal[cur][j]) psum += p[equal[cur][j]] idlists.append(idlist) pp.append(psum) k += 1 #print(idlists) #print(name) #print(pp)
#toposort q = deque()
for i in range(k): if (pp[i] == 0): q.append(i)
count = 0
while (len(q) > 0): cur = q.popleft() count += len(idlists[cur]) #print("equal[%d] = " % cur, end="") #print(equal[cur]) #print(v) #print(not (equal[2][1] in v)) for i in range(len(idlists[cur])): x = idlists[cur][i] for j in range(len(edge[x])): pp[name[edge[x][j]]] -= 1 if (pp[name[edge[x][j]]] == 0): q.append(name[edge[x][j]])
if (count == n): print("consistent") else: print("inconsistent")
Problem E: First map the names to ids, followed by two passes. First pass is to traverse through the graph to find out all affected nodes, and second pass is topological sorting on all nodes but printing out affected nodes only.
Code:
from collections import deque #import queue as Q #from math import sqrt
n = int(input())
d = {} name = [] k = 0 next = [] p = []
for i in range(n): tmp = input().split() s = tmp[0][:-1] if not s in d: d[s] = k k += 1 name.append(s) next.append([]) p.append(0)
for j in range(1, len(tmp)): if not tmp[j] in d: d[tmp[j]] = k k += 1 name.append(tmp[j]) next.append([]) p.append(0) next[d[tmp[j]]].append(d[s]) p[d[s]] += 1
while (len(q) > 0): cur = q.popleft() for i in range(len(next[cur])): if (not next[cur][i] in affected): affected.add(next[cur][i]) q.append(next[cur][i])
#print(name) #print(next) #print("s:%d" % len(affected)) #toposort for i in range(n): if (p[i] == 0): q.append(i)
m = 0
while (len(q) > 0): cur = q.popleft() if (cur in affected): print(name[cur]) m += 1 if (m == len(affected)): break for i in range(len(next[cur])): p[next[cur][i]] -= 1 if (p[next[cur][i]] == 0): q.append(next[cur][i])
Problem F Longest-path problem with positive weight (and possibly positive cycles). Bellman-Ford came into mind immediately, but there's an extra constraint that we can't go below or equal to 0 energy in the middle unless there're positive cycles before them. Also, positive cycles don't mean winnable - we need to make sure they're reachable to the destination. Therefore first pass is to figure out all reachable nodes from the destination room, and then do a variation of Bellman-Ford algorithm on reachable nodes with positive-distance-only updates to find the longest path.
Code:
from collections import deque
#try: while (True): try: n = int(input()) except ValueError: print("Please enter an integer") exit() if (n == -1): exit() edge = [[] for i in range(n)] redge = [[] for i in range(n)] weight = [[] for i in range(n)] for i in range(n): tmp = input().split() w = int(tmp[0]) #if (int(tmp[1]) > len(tmp) - 2): # exit() #for j in range(int(tmp[1])): for j in range(len(tmp)-2): edge[i].append(int(tmp[j+2])-1) weight[i].append(w) redge[int(tmp[j+2])-1].append(i) while (int(tmp[1]) > len(edge[i])): ttt = input().split() for k in range(len(ttt)): edge[i].append(int(ttt[k])-1) weight[i].append(w) redge[int(ttt[k])-1].append(i)
#print(weight) #print(redge) q = deque() q.append(n-1) visible = [False for i in range(n)] visible[n-1] = True while (len(q) > 0): cur = q.popleft() for i in range(len(redge[cur])): if (not visible[redge[cur][i]]): q.append(redge[cur][i]) visible[redge[cur][i]] = True #print(visible) if (not visible[0]): print("hopeless") continue
d = [-1000000 for i in range(n)] d[0] = 100
q = deque() q.append(0)
visited = [0 for i in range(n)] inqueue = [False for i in range(n)] inqueue[0] = True
positive_cycle = False
while (len(q) > 0): cur = q.popleft() inqueue[cur] = False visited[cur] += 1 if (visited[cur] > n): positive_cycle = True break for i in range(len(edge[cur])): if (visible[edge[cur][i]]): if (d[cur] + weight[cur][i] > 0 and d[cur] + weight[cur][i] > d[edge[cur][i]]): d[edge[cur][i]] = d[cur] + weight[cur][i] if (not inqueue[edge[cur][i]]): q.append(edge[cur][i]) inqueue[edge[cur][i]] = True
if (positive_cycle): print("winnable") elif (d[n-1] > 0): print("winnable") else: print("hopeless")
I think the key structure/component I used for all problems is the compact edge-representation (adjacency list) + queue-based BFS graph traversal, combined with existing graph theory knowledge like floodfill, minimum spanning tree, topological sort and shortest path.
Still puzzled how to get near the top in Power Strings.
I would guess that checking for prime divisors of the string length, and continuing with the initial piece of the string in the case of a hit, should be pretty fast. To save time, one should compute the list of primes only as far as required. In Python this can be done nicely using generator functions, and gives a running time of 0.32 seconds. Rewriting in C or so should yield a speed up by a factor of 10 at least.
Even faster would be hardcoding the list of relevant primes ...
Ah, and of course thx for arranging this round, Solomon!
What I did was I ported Solomon's Build Dependency solution to C# so that I better understand what's going on. I noticed two differences compared to what I tried: 1, I didn't map strings to indices and vice versa (I'm not sure if that's actually necessary in C# - gonna try) and 2, I used a BFS instead of a DFS Now the ported solution got accepted, so I'll only want to modify my non-recursive solution to DFS and see if it's fast enough.
What I also noticed is that it seems way too cumbersome to code in C++ once you are used to C# (I mean, e.g. you need to split a string? myString.Split(' '); there you go.)
Users browsing this forum: No registered users and 1 guest
You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot post attachments in this forum