L19 Programming Problem Championship: Round 3 (Graphs)

[gamesorry]

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?

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

I should use

Code: Select all

edges = [[] for i in range(n+1)]

instead of

Code: Select all

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

in initialization

[bernds]

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]

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]

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]

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]

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]

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

[bernds]

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]

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]

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.

[quantumf]

Any suggestions for how to construct a tough/pathological problem for BuildDependencies? I've tried very long (100,000 files that depend in sequence on one another) and very wide (100,000 files that depend on a single file), but my code is near instantaneous with these, and yet I'm getting TLE on test 2. Are we expected to deal with circular dependencies?

[gamesorry]

Are we expected to deal with circular dependencies?

I think there are no circular dependencies in test data (I didn't handle such cases).

[jeromie]

Any suggestions for how to construct a tough/pathological problem for BuildDependencies? I've tried very long (100,000 files that depend in sequence on one another) and very wide (100,000 files that depend on a single file), but my code is near instantaneous with these, and yet I'm getting TLE on test 2. Are we expected to deal with circular dependencies?

There is extra, unused data in the file, I.e. Files that do not need to be rebuilt. It is those extra unconnected files that gave my algorithm fits. (I think.)

[Solomon]

Well I managed to get E and F as I'd hoped (I think I spent more time tinkering with input and forgetting about cin.ignore() than the actual algorithm for E...), but with only 30 minutes before I have to visit family and not coming back until past the deadline, it looks like I won't be able to squeeze D in (although I'll most likely be pondering the problem at the dinner table...).

[gamesorry]

Overlooking the following statement for Problem F costs me 26 trials to figure out:
(I even used 'try - except ValueError' statements to catch the weird input exception)

"The input for each room consists of one or more lines"

but finally I got all problems despite the huge penalties

Edit: Ah, it seems some of you have already pointed out the pitfall ...