L19 Programming Problem Championship: Round 3 (Graphs)

Solomon · **#21**

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.

peti29 · **#22**

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.

jeromie · **#23**

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.

peti29 · **#24**

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 · **#25**

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.

Kirby · **#26**

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 · **#27**

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 · **#28**

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:

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:

Solomon · **#29**

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?

jeromie · **#30**

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.

gamesorry · **#31**

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:

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

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

bernds · **#32**

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.

quantumf · **#33**

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.

quantumf · **#34**

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.

quantumf · **#35**

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.

ugoertz · **#36**

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

jeromie · **#37**

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

bernds · **#38**

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

Solomon · **#39**

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.

bernds · **#40**

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.

L19 Programming Problem Championship: Round 3 (Graphs)

Who is online