It is currently Wed Aug 23, 2017 8:34 am

All times are UTC - 8 hours [ DST ]




Post new topic Reply to topic  [ 66 posts ]  Go to page Previous  1, 2, 3, 4  Next
Author Message
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #21 Posted: Sat May 13, 2017 10:12 am 
Gosei
User avatar

Posts: 1828
Location: Bellevue, WA
Liked others: 89
Was liked: 817
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
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #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
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #23 Posted: Sat May 13, 2017 12:25 pm 
Lives in gote

Posts: 648
Location: Littleton, CO
Liked others: 230
Was liked: 188
Rank: KGS 4k
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
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #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
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #25 Posted: Sat May 13, 2017 1:23 pm 
Dies in gote

Posts: 46
Liked others: 5
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
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #26 Posted: Sat May 13, 2017 2:32 pm 
Judan

Posts: 7470
Liked others: 1359
Was liked: 1150
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.

_________________
Discipline is remembering what you want. -David Campbell

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

Posts: 648
Location: Littleton, CO
Liked others: 230
Was liked: 188
Rank: KGS 4k
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
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #28 Posted: Sat May 13, 2017 10:18 pm 
Gosei
User avatar

Posts: 1828
Location: Bellevue, WA
Liked others: 89
Was liked: 817
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
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #29 Posted: Sat May 13, 2017 10:19 pm 
Gosei
User avatar

Posts: 1828
Location: Bellevue, WA
Liked others: 89
Was liked: 817
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
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #30 Posted: Sat May 13, 2017 10:27 pm 
Lives in gote

Posts: 648
Location: Littleton, CO
Liked others: 230
Was liked: 188
Rank: KGS 4k
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
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #31 Posted: Sun May 14, 2017 12:18 am 
Lives with ko

Posts: 131
Liked others: 163
Was liked: 41
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)]

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

in initialization

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

Posts: 46
Liked others: 5
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
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #33 Posted: Sun May 14, 2017 1:49 am 
Lives in sente
User avatar

Posts: 813
Liked others: 180
Was liked: 134
Rank: 2d
GD Posts: 422
KGS: quantumf/komi/balvenie/loads more
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
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #34 Posted: Sun May 14, 2017 1:53 am 
Lives in sente
User avatar

Posts: 813
Liked others: 180
Was liked: 134
Rank: 2d
GD Posts: 422
KGS: quantumf/komi/balvenie/loads more
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
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #35 Posted: Sun May 14, 2017 2:23 am 
Lives in sente
User avatar

Posts: 813
Liked others: 180
Was liked: 134
Rank: 2d
GD Posts: 422
KGS: quantumf/komi/balvenie/loads more
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
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #36 Posted: Sun May 14, 2017 2:56 am 
Dies in gote
User avatar

Posts: 59
Liked others: 0
Was liked: 38
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
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #37 Posted: Sun May 14, 2017 7:00 am 
Lives in gote

Posts: 648
Location: Littleton, CO
Liked others: 230
Was liked: 188
Rank: KGS 4k
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. :roll: I bungled it up a couple times to add another few attempts.)

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

Posts: 46
Liked others: 5
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
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #39 Posted: Sun May 14, 2017 12:07 pm 
Gosei
User avatar

Posts: 1828
Location: Bellevue, WA
Liked others: 89
Was liked: 817
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
 Profile  
 
Offline
 Post subject: Re: L19 Programming Problem Championship: Round 3
Post #40 Posted: Sun May 14, 2017 12:12 pm 
Dies in gote

Posts: 46
Liked others: 5
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
 Profile  
 
Display posts from previous:  Sort by  
Post new topic Reply to topic  [ 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: Bing [Bot], Yahoo [Bot] and 2 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