It is currently Wed Nov 22, 2017 5:32 am

 All times are UTC - 8 hours [ DST ]

 Page 2 of 4 [ 66 posts ] Go to page Previous  1, 2, 3, 4  Next
 Print view Previous topic | Next topic
Author Message
 Post subject: Re: L19 Programming Problem Championship: Round 3 #21 Posted: Sat May 13, 2017 10:12 am
 Gosei

Posts: 1833
Location: Bellevue, WA
Liked others: 89
Was liked: 820
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
bernds wrote:
One thing I do when I'm stumped by "WA" evaluations is write a testcase generator (I did that for the chess problem in this round). Although in this particular case I have no good idea of how the generator would produce the expected answer, other than by running the same algorithm as the real solution which obviously defeats the purpose.
Not sure if it applies to the chess problem (I just started working on the problems this morning...), but one strategy is to write a naive, brute-force algorithm that you know is correct but would lead to TLE and/or MLE and use that to build a test case generator.

Top

 Post subject: Re: L19 Programming Problem Championship: Round 3 #22 Posted: Sat May 13, 2017 12:16 pm
 Lives with ko

Posts: 125
Liked others: 13
Was liked: 11
Rank: KGS 5 kyu
Kirby wrote:
For me, these problems are about 10% getting the right answer, and 90% trying to get it fast enough.

This.
That said, the dominoes was the first problem so far that I got right for the first try.

Top

 Post subject: Re: L19 Programming Problem Championship: Round 3 #23 Posted: Sat May 13, 2017 12:25 pm
 Lives in sente

Posts: 750
Location: Littleton, CO
Liked others: 253
Was liked: 213
Rank: KGS 3k
Universal go server handle: jeromie
quantumf wrote:

Here, for instance, I calculate 11, which is presumably correct?

Are you properly handling the case where there is more than one starting domino? That doesn't show up in the test data, but it's a valid condition and can cause some different conditions.

Top

 Post subject: Re: L19 Programming Problem Championship: Round 3 #24 Posted: Sat May 13, 2017 1:17 pm
 Lives with ko

Posts: 125
Liked others: 13
Was liked: 11
Rank: KGS 5 kyu
Perplexed by Problem A's memory limit hit. There's absolutely no way I allocate 1 GB of memory for an 1000 * 1000 problem.
If however there is a typo and the limit is actually 1 MB then I need to rethink my solution...

Top

 Post subject: Re: L19 Programming Problem Championship: Round 3 #25 Posted: Sat May 13, 2017 1:23 pm
 Dies in gote

Posts: 48
Liked others: 7
Was liked: 7
Rank: 2d
peti29 wrote:
Perplexed by Problem A's memory limit hit. There's absolutely no way I allocate 1 GB of memory for an 1000 * 1000 problem.
If however there is a typo and the limit is actually 1 MB then I need to rethink my solution...
No, it's 1GB. Just guessing, but if you're doing recursion and that has a bug you could end up allocating unbounded stack; I assume they are limiting that as well.

Top

 Post subject: Re: L19 Programming Problem Championship: Round 3 #26 Posted: Sat May 13, 2017 2:32 pm
 Judan

Posts: 7588
Liked others: 1379
Was liked: 1162
KGS: Kirby
Tygem: 커비라고해
In my case for Problem 1, thinking about water having land coast vs. land having water coast was useful.

I kept getting TLE otherwise.

These problems are educational but also make me mad. Maybe it means I'm learning? I dunno.

Love hate relationship.

_________________
What have I learned from this game that I'll be able to use in my own game if the opportunity presents itself?

Top

 Post subject: Re: L19 Programming Problem Championship: Round 3 #27 Posted: Sat May 13, 2017 9:54 pm
 Lives in sente

Posts: 750
Location: Littleton, CO
Liked others: 253
Was liked: 213
Rank: KGS 3k
Universal go server handle: jeromie
I seem to be having an odd problem parsing the file in problem F. My parsing routine works fine for the test file and case 1 (which is probably the same thing), but it's crashing on the second test case. It's almost as if there's a blank line somewhere in the input file, but there's nothing about that mentioned in the problem specification. Anyone else run into a problem like this, or do I just have some silly parsing error somewhere?

Edit:
Or perhaps the test cases are not terminated with a -1 as specified? That could cause the problem.

I can catch the exception and make it give a solution, but when I get a wrong answer I can't tell if there's something wrong with my parsing or my solution algorithm.

Last edited by jeromie on Sat May 13, 2017 10:27 pm, edited 1 time in total.
Top

 Post subject: Re: L19 Programming Problem Championship: Round 3 #28 Posted: Sat May 13, 2017 10:18 pm
 Gosei

Posts: 1833
Location: Bellevue, WA
Liked others: 89
Was liked: 820
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
quantumf wrote:
bernds wrote:
quantumf wrote:
That's a fair point and good hint. Now I keep failing on Test 3, but I can't conceive of a test scenario that makes my code fail. Can anyone advise a fiendish structure that will challenge my solution?
No idea, it could be anything. Are you sure none of your dominos fall more than once?

Every scenario I devise I test by hand to check the result, and the algorithm does it correctly. I've tried branching, multiple branching, nested branching, re-combining, isolated structures. Nothing doesn't work. Most probably I'm still missing some fundamental concept.

Code:
1
13 14 3
1 2
1 3
2 4
2 5
4 6
4 7
4 8
6 10
7 11
8 12
5 12
3 9
12 13
9 12
4
5
3

Here, for instance, I calculate 11, which is presumably correct?

Agree with bernds, edge cases are probably what's biting you. Try something sillier, like below (my output is 0, 2, and 41 respectively):
Code:
3
5 1 0
5 5
5 1 5
1 1
1
1
1
2
2
50 50 50
1 22
1 33
2 2
2 23
3 12
3 18
3 27
3 37
3 43
4 5
5 39
5 43
6 12
6 38
7 50
8 1
8 34
10 2
10 43
10 46
11 5
18 10
18 16
18 43
20 10
20 30
23 16
23 50
25 11
30 10
30 34
31 23
31 40
31 43
32 16
33 5
33 38
35 30
36 5
36 14
38 32
42 13
42 20
42 40
43 2
44 6
45 6
46 8
50 29
50 30
25
49
23
32
22
38
30
31
3
31
39
11
29
47
50
34
29
19
18
8
50
12
27
28
50
8
34
7
32
25
43
17
42
13
23
7
45
45
11
38
18
10
47
21
29
47
5
6
26
14

Top

 Post subject: Re: L19 Programming Problem Championship: Round 3 #29 Posted: Sat May 13, 2017 10:19 pm
 Gosei

Posts: 1833
Location: Bellevue, WA
Liked others: 89
Was liked: 820
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
jeromie wrote:
I seem to be having an odd problem parsing the file in problem 5. My parsing routine works fine for the test file and case 1 (which is probably the same thing), but it's crashing on the second test case. It's almost as if there's a blank line somewhere in the input file, but there's nothing about that mentioned in the problem specification. Anyone else run into a problem like this, or do I just have some silly parsing error somewhere?

Edit:
Or perhaps the test cases are not terminated with a -1 as specified? That could cause the problem.

I can catch the exception and make it give a solution, but when I get a wrong answer I can't tell if there's something wrong with my parsing or my solution algorithm.

You mean problem 6 (XYZZY) right?

Top

 Post subject: Re: L19 Programming Problem Championship: Round 3 #30 Posted: Sat May 13, 2017 10:27 pm
 Lives in sente

Posts: 750
Location: Littleton, CO
Liked others: 253
Was liked: 213
Rank: KGS 3k
Universal go server handle: jeromie
Solomon wrote:
jeromie wrote:
I seem to be having an odd problem parsing the file in problem 5. My parsing routine works fine for the test file and case 1 (which is probably the same thing), but it's crashing on the second test case. It's almost as if there's a blank line somewhere in the input file, but there's nothing about that mentioned in the problem specification. Anyone else run into a problem like this, or do I just have some silly parsing error somewhere?

Edit:
Or perhaps the test cases are not terminated with a -1 as specified? That could cause the problem.

I can catch the exception and make it give a solution, but when I get a wrong answer I can't tell if there's something wrong with my parsing or my solution algorithm.

You mean problem 6 (XYZZY) right?

Yep. Edited above.

Top

 Post subject: Re: L19 Programming Problem Championship: Round 3 #31 Posted: Sun May 14, 2017 12:18 am
 Lives with ko

Posts: 136
Liked others: 182
Was liked: 42
Rank: Chinese 3d
KGS: 3d
DGS: 3d
OGS: 3d
quantumf wrote:
bernds wrote:
quantumf wrote:
That's a fair point and good hint. Now I keep failing on Test 3, but I can't conceive of a test scenario that makes my code fail. Can anyone advise a fiendish structure that will challenge my solution?
No idea, it could be anything. Are you sure none of your dominos fall more than once?

Every scenario I devise I test by hand to check the result, and the algorithm does it correctly. I've tried branching, multiple branching, nested branching, re-combining, isolated structures. Nothing doesn't work. Most probably I'm still missing some fundamental concept.

Code:
1
13 14 3
1 2
1 3
2 4
2 5
4 6
4 7
4 8
6 10
7 11
8 12
5 12
3 9
12 13
9 12
4
5
3

Here, for instance, I calculate 11, which is presumably correct?

Your test case actually helped me detect a bug in my code!

I should use
Code:
edges = [[] for i in range(n+1)]

Code:
edges = [[]] * (n+1)

in initialization

Top

 Post subject: Re: L19 Programming Problem Championship: Round 3 #32 Posted: Sun May 14, 2017 1:28 am
 Dies in gote

Posts: 48
Liked others: 7
Was liked: 7
Rank: 2d
Guess I'll be learning something when Solomon posts how to approach problem B. I have a solution (I think), it's just too slow. Maybe I'm missing something obvious, or maybe I somehow need to treat this as more of geometry problem. Hmm.

Top

 Post subject: Re: L19 Programming Problem Championship: Round 3 #33 Posted: Sun May 14, 2017 1:49 am
 Lives in sente

Posts: 816
Liked others: 180
Was liked: 134
Rank: 2d
GD Posts: 422
Solomon wrote:
Agree with bernds, edge cases are probably what's biting you. Try something sillier, like below (my output is 0, 2, and 41 respectively):

Cool, I get 0,1,34, so something to look at.

Top

 Post subject: Re: L19 Programming Problem Championship: Round 3 #34 Posted: Sun May 14, 2017 1:53 am
 Lives in sente

Posts: 816
Liked others: 180
Was liked: 134
Rank: 2d
GD Posts: 422
E is a really nice problem, and one of the most real world applicable examples I've seen in these problems. Trying to optimize this is a nice challenge - currently getting S/O so need to see if converting my recursive graph traversal to an iterative solution helps. Definitely helped to write a generator here, any hand constructed examples were way too small to push the memory or performance.

Top

 Post subject: Re: L19 Programming Problem Championship: Round 3 #35 Posted: Sun May 14, 2017 2:23 am
 Lives in sente

Posts: 816
Liked others: 180
Was liked: 134
Rank: 2d
GD Posts: 422
quantumf wrote:
Solomon wrote:
Agree with bernds, edge cases are probably what's biting you. Try something sillier, like below (my output is 0, 2, and 41 respectively):

Cool, I get 0,1,34, so something to look at.

Thanks, got it now. Funny how one can have blind spots to such un-intuitive constructions - dominoes knocking themselves over just didn't occur to me.

Top

 Post subject: Re: L19 Programming Problem Championship: Round 3 #36 Posted: Sun May 14, 2017 2:56 am
 Dies in gote

Posts: 62
Liked others: 0
Was liked: 40
jeromie wrote:
I seem to be having an odd problem parsing the file in problem F.

I had a similar problem until I noticed that the description says "The input for each room consists of one or more lines containing:".

Best regards,

Ulrich

_________________
u-go.net

Top

 Post subject: Re: L19 Programming Problem Championship: Round 3 #37 Posted: Sun May 14, 2017 7:00 am
 Lives in sente

Posts: 750
Location: Littleton, CO
Liked others: 253
Was liked: 213
Rank: KGS 3k
Universal go server handle: jeromie
ugoertz wrote:
jeromie wrote:
I seem to be having an odd problem parsing the file in problem F.

I had a similar problem until I noticed that the description says "The input for each room consists of one or more lines containing:".

Best regards,

Ulrich

Thanks. Ugh, that is an awful file format, especially since the example is all on one line.

Edit: And my program works after I fix my parsing error. (Correctly. I bungled it up a couple times to add another few attempts.)

Top

 Post subject: Re: L19 Programming Problem Championship: Round 3 #38 Posted: Sun May 14, 2017 11:57 am
 Dies in gote

Posts: 48
Liked others: 7
Was liked: 7
Rank: 2d
bernds wrote:
Guess I'll be learning something when Solomon posts how to approach problem B. I have a solution (I think), it's just too slow. Maybe I'm missing something obvious, or maybe I somehow need to treat this as more of geometry problem. Hmm.
Ok, I was missing something obvious, and now I've got the efficient algorithm. Produces the same output as my previous one on all my testcases... but now it's WA instead of TLE

Top

 Post subject: Re: L19 Programming Problem Championship: Round 3 #39 Posted: Sun May 14, 2017 12:07 pm
 Gosei

Posts: 1833
Location: Bellevue, WA
Liked others: 89
Was liked: 820
Rank: AGA 5d
KGS: Capsule 4d
Tygem: 치킨까스 5d
I have pretty good ideas on how to solve E (Build Dependencies) and F (XYZZY), and will try to solve them before Mother's Day (US edition) dinner, but D (Chess Tournament) I'm not so sure. Only way I can see it modeled is a mixed graph with directed and undirected edges, but that just sounds like a nightmare and I'm unversed on any algorithms for handling mixed graphs. Whatever I manage to get, I will write how I solved tomorrow before work.

Top

 Post subject: Re: L19 Programming Problem Championship: Round 3 #40 Posted: Sun May 14, 2017 12:12 pm
 Dies in gote

Posts: 48
Liked others: 7
Was liked: 7
Rank: 2d
Solomon wrote:
I have pretty good ideas on how to solve E (Build Dependencies) and F (XYZZY), and will try to solve them before Mother's Day (US edition) dinner, but D (Chess Tournament) I'm not so sure. Only way I can see it modeled is a mixed graph with directed and undirected edges, but that just sounds like a nightmare and I'm unversed on any algorithms for handling mixed graphs. Whatever I manage to get, I will write how I solved tomorrow before work.
Hint: it's simpler than that. Not too hard a problem at all really once you figure out one step.

Top

 Display posts from previous: All posts1 day7 days2 weeks1 month3 months6 months1 year Sort by AuthorPost timeSubject AscendingDescending
 Page 2 of 4 [ 66 posts ] Go to page Previous  1, 2, 3, 4  Next

 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