I think this case should be 4. As for why you're getting WA, you're almost certainly running into the same issue I was. Hint: these graphs get big. Like, really big.

Thanks for the hint bernds, it was just the nudge I needed!

Haven't made much progress today due to spending most of my day packing for a Hawaii vacation starting tomorrow . I'll be mostly in the air tomorrow, so I won't be able to post an update until next week (and Round 5 will be in two weeks). Sorry for the inconvenience, and thanks for participating!

Thanks, Solomon, for setting up the contest!

Some thoughts about the problems:

Problem A: Viewing the people as vertices of a graph, with an edge connecting those whose paths cross, the problem is to find the maximal length of a clique. My first tries did that without taking the special form of the graph into account, and thus were too slow. After Solomon's post with a pointer to some paper on this problem for circle graphs I thought about it some more and realized that in the situation at hand, we have what's called a permutation graph, and that once the corresponding permutation has been found, finding cliques just amounts to finding maximal decreasing sequences in the sequence of values. It turns that both these things are easily accomplished (less than 20 lines of Python code, not counting comments and blank lines), so in the end I was quite happy with the solution.

Problem B: Was relatively easy for me (profiting, it seems, from the fact, that Python works with arbitrary large integers out of the box).

Problem E: My solution is quite straightforward - apply some easy heuristics first, and then do backtracking. Fortunately it is fast enough for the given test cases. I tested it on some 14x14 problem I found on the net, and had to interrupt it after a couple of minutes ...


Best, Ulrich

_________________
u-go.net

I didn't have quite as much time this weekend; I didn't really try C or D. I have pretty much the same thoughts about A and B as Ulrich.
I was trying to teach it the kind of deductions that humans would make. I may have been in the wrong mindset since I worked on a similar puzzle game once where the goal was to create human-solvable puzzles of varying diffculties. After the fact I'm guessing they probably want to find any solution if it exists. I guess I could have added a brute-force step, but the program I had was becoming unwieldy anyway and I kind of gave up on it.

Thanks, Solomon, for arranging this round!

I regret not having much time this week. That overflow tricked me for quite some time in problem B. Then I wrote up a program to solve A - when I realized that I solved something completely different than what the problem was about . Then I couldn't think up an efficient enough solution to find maximal full graphs...
If I had some more time I would have attempted D which seemed straightforward enough even if somewhat complex.
And I really liked problem E. Unfortunately I didn't have much time to think about it - and that "must not contain circles" criteria seemed hard to take into account.

So, you have a number of subgraphs, none of which contain cycles. What you do is: iterate over all the nodes you have. If you've already seen the one you're looking at, skip it, otherwise traverse the subgraph from that node, and mark all the nodes you encounter with the same ID value (think of it as a color maybe), and record for each node you visit that you've already seen it.
Then, later when you're considering whether you can connect two nodes, just check if they have different colors. If not, you'd be making a cycle. Otherwise, just change all nodes of the newly connected graph to have the same color.

Also traveling for a few weeks, hope to be back for R5