L19 Programming Problem Championship: Round 3 (Graphs)

[Solomon]

Also, kudos to bernds for not only solving Building Dependencies, but also being the fastest!

[bernds]

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.

[gamesorry]

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: Select all

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: Select all

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: Select all

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: Select all

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: Select all

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

changed = input()

affected = set()

q = deque()
q.append(d[changed])
affected.add(d[changed])

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: Select all

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.

[ugoertz]

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 ...

Best, Ulrich

[peti29]

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.)

[peti29]

My non-recursive C# solution for Building Dependencies if anyone is interested:

Code: Select all

using System;
using System.Collections.Generic;

namespace BuildDependency
{
    public class Program
    {
        public Dictionary<string, List<string>> ReverseRules = new Dictionary<string, List<string>>();

        public static void Main()
        {
            new Program();
        }

        public Program()
        {
            int n = int.Parse(Console.ReadLine());

            for (int i = 0; i < n; i++)
            {
                string[] par = Console.ReadLine().Split(':');
                string file = par[0];
                string[] dep = par[1].Split(' ');

                if (dep.Length > 0)
                {
                    foreach (string item in dep)
                    {
                        if (item == "")
                            continue;

                        if (!ReverseRules.ContainsKey(item))
                        {
                            ReverseRules.Add(item, new List<string>());
                        }
                        ReverseRules[item].Add(file);
                    }
                }
            }

            List<string> rebuild = new List<string>();
            string changedFile = Console.ReadLine();
            Traverse(changedFile, rebuild);

            rebuild.Reverse();
            foreach (string item in rebuild)
            {
                Console.WriteLine(item);
            }
        }

        private void Traverse(string node, List<string> rebuild)
        {
            HashSet<string> hash = new HashSet<string>();
            Stack<string> stack = new Stack<string>();
            stack.Push(node);

            while (stack.Count > 0)
            {
                string item = stack.Pop();

                if (item[0] == '%')
                {
                    rebuild.Add(item.Substring(1));
                    continue;
                }

                if (!hash.Add(item))
                {
                    continue;
                }
                else
                {
                    stack.Push('%' + item);
                }

                if (ReverseRules.ContainsKey(item))
                {
                    foreach(string dep in ReverseRules[item])
                    {
                        if (!hash.Contains(dep))
                        {
                            stack.Push(dep);
                        }
                    }
                }
            }
        }
    }
}