It is currently Fri Mar 29, 2024 5:37 am

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 28 posts ]  Go to page Previous  1, 2
Author Message
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 4
Post #21 Posted: Sat May 20, 2017 6:33 pm 
Lives with ko

Posts: 259
Liked others: 46
Was liked: 116
Rank: 2d
Solomon wrote:
I also tried cases where the starting node and the ending node are the same, such as:
Image
Code:
5 1
2 4
0
winning paths 0
total paths 4

Some of my submission errors were from me not being sure if total paths should be 4 or 1; tried both scenarios and nothing came out of it unfortunately :(. Any help appreciated!
I think this case should be 4. As for why you're getting WA, you're almost certainly running into the same issue I was. Hint: these graphs get big. Like, really big.


This post by bernds was liked by: Solomon
Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 4
Post #22 Posted: Sat May 20, 2017 6:37 pm 
Gosei
User avatar

Posts: 1848
Location: Bellevue, WA
Liked others: 90
Was liked: 837
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
bernds wrote:
Solomon wrote:
I also tried cases where the starting node and the ending node are the same, such as:
Image
Code:
5 1
2 4
0
winning paths 0
total paths 4

Some of my submission errors were from me not being sure if total paths should be 4 or 1; tried both scenarios and nothing came out of it unfortunately :(. Any help appreciated!
I think this case should be 4. As for why you're getting WA, you're almost certainly running into the same issue I was. Hint: these graphs get big. Like, really big.
Thanks for the hint bernds, it was just the nudge I needed!

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 4
Post #23 Posted: Sun May 21, 2017 7:36 pm 
Gosei
User avatar

Posts: 1848
Location: Bellevue, WA
Liked others: 90
Was liked: 837
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
Haven't made much progress today due to spending most of my day packing for a Hawaii vacation starting tomorrow :(. I'll be mostly in the air tomorrow, so I won't be able to post an update until next week (and Round 5 will be in two weeks). Sorry for the inconvenience, and thanks for participating!

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 4
Post #24 Posted: Mon May 22, 2017 1:24 am 
Dies in gote
User avatar

Posts: 63
Liked others: 0
Was liked: 40
Thanks, Solomon, for setting up the contest!

Some thoughts about the problems:

Problem A: Viewing the people as vertices of a graph, with an edge connecting those whose paths cross, the problem is to find the maximal length of a clique. My first tries did that without taking the special form of the graph into account, and thus were too slow. After Solomon's post with a pointer to some paper on this problem for circle graphs I thought about it some more and realized that in the situation at hand, we have what's called a permutation graph, and that once the corresponding permutation has been found, finding cliques just amounts to finding maximal decreasing sequences in the sequence of values. It turns that both these things are easily accomplished (less than 20 lines of Python code, not counting comments and blank lines), so in the end I was quite happy with the solution.

Problem B: Was relatively easy for me (profiting, it seems, from the fact, that Python works with arbitrary large integers out of the box).

Problem E: My solution is quite straightforward - apply some easy heuristics first, and then do backtracking. Fortunately it is fast enough for the given test cases. I tested it on some 14x14 problem I found on the net, and had to interrupt it after a couple of minutes ...


Best, Ulrich

_________________
u-go.net


This post by ugoertz was liked by: Solomon
Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 4
Post #25 Posted: Mon May 22, 2017 4:10 am 
Lives with ko

Posts: 259
Liked others: 46
Was liked: 116
Rank: 2d
I didn't have quite as much time this weekend; I didn't really try C or D. I have pretty much the same thoughts about A and B as Ulrich.
ugoertz wrote:
Problem E: My solution is quite straightforward - apply some easy heuristics first, and then do backtracking. Fortunately it is fast enough for the given test cases. I tested it on some 14x14 problem I found on the net, and had to interrupt it after a couple of minutes ...
I was trying to teach it the kind of deductions that humans would make. I may have been in the wrong mindset since I worked on a similar puzzle game once where the goal was to create human-solvable puzzles of varying diffculties. After the fact I'm guessing they probably want to find any solution if it exists. I guess I could have added a brute-force step, but the program I had was becoming unwieldy anyway and I kind of gave up on it.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 4
Post #26 Posted: Mon May 22, 2017 7:38 am 
Lives with ko

Posts: 125
Liked others: 13
Was liked: 12
Rank: KGS 5 kyu
Thanks, Solomon, for arranging this round!

I regret not having much time this week. That overflow tricked me for quite some time in problem B. Then I wrote up a program to solve A - when I realized that I solved something completely different than what the problem was about :scratch:. Then I couldn't think up an efficient enough solution to find maximal full graphs...
If I had some more time I would have attempted D which seemed straightforward enough even if somewhat complex.
And I really liked problem E. Unfortunately I didn't have much time to think about it - and that "must not contain circles" criteria seemed hard to take into account.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 4
Post #27 Posted: Mon May 22, 2017 8:28 am 
Lives with ko

Posts: 259
Liked others: 46
Was liked: 116
Rank: 2d
peti29 wrote:
That "must not contain circles" criteria seemed hard to take into account.


So, you have a number of subgraphs, none of which contain cycles. What you do is: iterate over all the nodes you have. If you've already seen the one you're looking at, skip it, otherwise traverse the subgraph from that node, and mark all the nodes you encounter with the same ID value (think of it as a color maybe), and record for each node you visit that you've already seen it.
Then, later when you're considering whether you can connect two nodes, just check if they have different colors. If not, you'd be making a cycle. Otherwise, just change all nodes of the newly connected graph to have the same color.

Top
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 4
Post #28 Posted: Mon May 22, 2017 1:29 pm 
Lives in sente
User avatar

Posts: 842
Liked others: 180
Was liked: 151
Rank: 3d
GD Posts: 422
KGS: komi
Solomon wrote:
Haven't made much progress today due to spending most of my day packing for a Hawaii vacation starting tomorrow :(. I'll be mostly in the air tomorrow, so I won't be able to post an update until next week (and Round 5 will be in two weeks). Sorry for the inconvenience, and thanks for participating!


Also traveling for a few weeks, hope to be back for R5

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

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