It is currently Sat Aug 19, 2017 6:13 am

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 66 posts ]  Go to page Previous  1, 2, 3, 4
Author Message
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #61 Posted: Mon May 15, 2017 12:24 pm 
Gosei
User avatar

Posts: 1828
Location: Bellevue, WA
Liked others: 89
Was liked: 817
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
Also, kudos to bernds for not only solving Building Dependencies, but also being the fastest!

Image


This post by Solomon was liked by 2 people: bernds, gamesorry
Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #62 Posted: Mon May 15, 2017 12:44 pm 
Dies in gote

Posts: 45
Liked others: 5
Was liked: 7
Rank: 2d
Solomon wrote:
Also, kudos to bernds for not only solving Building Dependencies, but also being the fastest!

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


This post by bernds was liked by: Solomon
Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #63 Posted: Mon May 15, 2017 2:35 pm 
Lives with ko

Posts: 130
Liked others: 163
Was liked: 41
Rank: Chinese 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

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


This post by gamesorry was liked by: Solomon
Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #64 Posted: Tue May 16, 2017 2:39 am 
Dies in gote
User avatar

Posts: 58
Liked others: 0
Was liked: 38
bernds wrote:
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

_________________
u-go.net

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #65 Posted: Tue May 16, 2017 7:49 am 
Lives with ko

Posts: 125
Liked others: 13
Was liked: 11
Rank: KGS 5 kyu
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.)

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #66 Posted: Thu May 18, 2017 8:51 am 
Lives with ko

Posts: 125
Liked others: 13
Was liked: 11
Rank: KGS 5 kyu
My non-recursive C# solution for Building Dependencies if anyone is interested:
Code:
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);
                        }
                    }
                }
            }
        }
    }
}

Top
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 66 posts ]  Go to page Previous  1, 2, 3, 4

All times are UTC - 8 hours [ DST ]


Who is online

Users browsing this forum: No registered users and 3 guests


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

Search for:
Jump to:  
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group