It is currently Sun Nov 19, 2017 6:48 pm

 All times are UTC - 8 hours [ DST ]

 Page 4 of 4 [ 66 posts ] Go to page Previous  1, 2, 3, 4
 Print view Previous topic | Next topic
Author Message
 Post subject: Re: L19 Programming Problem Championship: Round 3 #61 Posted: Mon May 15, 2017 12:24 pm
 Gosei

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

 This post by Solomon was liked by 2 people: bernds, gamesorry
Top

 Post subject: Re: L19 Programming Problem Championship: Round 3 #62 Posted: Mon May 15, 2017 12:44 pm
 Dies in gote

Posts: 48
Liked others: 7
Was liked: 7
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.

 This post by bernds was liked by: Solomon
Top

 Post subject: Re: L19 Programming Problem Championship: Round 3 #63 Posted: Mon May 15, 2017 2:35 pm
 Lives with ko

Posts: 136
Liked others: 182
Was liked: 42
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()

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:
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()
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):
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])

while (len(q) > 0):
cur = q.popleft()
for i in range(len(next[cur])):
if (not next[cur][i] in affected):
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:
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

 Post subject: Re: L19 Programming Problem Championship: Round 3 #64 Posted: Tue May 16, 2017 2:39 am
 Dies in gote

Posts: 62
Liked others: 0
Was liked: 40
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

 Post subject: Re: L19 Programming Problem Championship: Round 3 #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

 Post subject: Re: L19 Programming Problem Championship: Round 3 #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()
{

for (int i = 0; i < n; i++)
{
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))
{
}
}
}
}

List<string> rebuild = new List<string>();
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] == '%')
{
continue;
}

{
continue;
}
else
{
stack.Push('%' + item);
}

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

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 4 of 4 [ 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 1 guest

 You cannot post new topics in this forumYou cannot reply to topics in this forumYou cannot edit your posts in this forumYou cannot delete your posts in this forumYou cannot post attachments in this forum

Search for:
 Jump to:  Select a forum ------------------ Life In 19x19.com General Topics    Introductions and Guidelines    Off Topic    Announcements    General Go Chat    Beginners    Amateurs    Professionals       Lee Sedol vs Gu Li    Go Rules    Forum/Site Suggestions and Bugs    Creative writing    Tournaments       Ride share to tournaments Improve Your Game    Game Analysis    Study Group    Teachers/Club Leaders       Teacher advertisements    Study Journals L19²GO (Malkovich)    1-on-1 Malkovich games    Big Brother Malkovich games    Rengo Games    Other versions of turn-based games Go Gear    Go Books    Go Book Reviews    Computer Go    Gobans and other equipment    Trading Post    New Products/Upgrades/Sales Go Club Forums    Go Club Discussions       Honinbo Go League    American Go Association Forum       Go Congress 2011 volunteers       AGA volunteers ( non-congress)    Australian Go Association    European Go Federation Forum    Singapore Weiqi Association    KGS    ASR League    IGS    OGS    Tygem    WBaduk    Turn Based Servers    Insei League Events    Kaya.gs       King of the Hill