L19 Programming Problem Championship: Round 3 (Graphs)

[Kirby]

Still get TLE on dominoes2. When I tried using an array to store lists of rules, I got memory limit exceeded.

For me, these problems are about 10% getting the right answer, and 90% trying to get it fast enough.

I must be doing something inefficient... A little frustrating for something that should be simpler...

Maybe I'll take another look tonight. Depends on my mood.

[bernds]

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?

[bernds]

Still get TLE on dominoes2. When I tried using an array to store lists of rules, I got memory limit exceeded.

I'll give the same advice as I gave to quantumf earlier: consider the theme of the round and how it relates to the problem. What kind of data structure are you trying to build? Have you ever worked with such a structure before or at least seen one in another program? Think about how you need to represent it.

If you've never taken any kind of algorithms or data structures course, you'll probably want to go and buy a book. I have a really old one by Robert Sedgewick which has pretty good coverage; it looks like modern versions of that are available, even on Kindle.

[quantumf]

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: Select all

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?

[bernds]

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

I can confirm that my program computes 11 as well.

It's most likely a very simple issue somewhere. Maybe a corner case when any of the numbers are zero? Maybe there's an issue related to counting from 1..n versus 0..n-1?

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.

[Solomon]

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.

[peti29]

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.

[jeromie]

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.

[peti29]

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

[bernds]

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.

[Kirby]

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.

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

[Solomon]

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: Select all

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: Select all

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

[Solomon]

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?

[jeromie]

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.