Life In 19x19 http://lifein19x19.com/ |
|
L19 Programming Problem Championship: Round 3 (Graphs) http://lifein19x19.com/viewtopic.php?f=8&t=14222 |
Page 4 of 4 |
Author: | Solomon [ Mon May 15, 2017 12:24 pm ] |
Post subject: | Re: L19 Programming Problem Championship: Round 3 |
Also, kudos to bernds for not only solving Building Dependencies, but also being the fastest! |
Author: | bernds [ Mon May 15, 2017 12:44 pm ] |
Post subject: | Re: L19 Programming Problem Championship: Round 3 |
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. |
Author: | gamesorry [ Mon May 15, 2017 2:35 pm ] |
Post subject: | Re: L19 Programming Problem Championship: Round 3 |
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) 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... Problem C: Didn't realize it could be formulated as a flood-fill problem but solved it with a BFS-style queue 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. 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. 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. 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. |
Author: | ugoertz [ Tue May 16, 2017 2:39 am ] |
Post subject: | Re: L19 Programming Problem Championship: Round 3 |
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 |
Author: | peti29 [ Tue May 16, 2017 7:49 am ] |
Post subject: | Re: L19 Programming Problem Championship: Round 3 |
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.) |
Author: | peti29 [ Thu May 18, 2017 8:51 am ] |
Post subject: | Re: L19 Programming Problem Championship: Round 3 |
My non-recursive C# solution for Building Dependencies if anyone is interested: |
Page 4 of 4 | All times are UTC - 8 hours [ DST ] |
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |