L19 Programming Problem Championship: Round 4 (Japan)

[Tryss]

As it turned out, more than what I actually wrote up on the whiteboard, they were evaluating how well I asked questions to clear up the ambiguity behind the problem they posed...

Not sure I agree that this is a good way of interviewing, but people do it that way sometimes.

That depend on what the job is about: If they need you to work with the client (intern or extern) to define their exact needs, this skill may be far more important than your "problem solving" skill.

Missunderstanding between the client and the dev team can cost some serious money

[Kirby]

As it turned out, more than what I actually wrote up on the whiteboard, they were evaluating how well I asked questions to clear up the ambiguity behind the problem they posed...

Not sure I agree that this is a good way of interviewing, but people do it that way sometimes.

That depend on what the job is about: If they need you to work with the client (intern or extern) to define their exact needs, this skill may be far more important than your "problem solving" skill.

Missunderstanding between the client and the dev team can cost some serious money

Agree. I suppose my main point was just that programming interviews are not always the same as programming competition questions. Programming jobs aren't always, either. It often comes down to what they are looking for and/or what the requirements are.

[peti29]

Hm. This is the first time that I'm reasonably sure that my solution is correct, yet I get rejected with "wrong answer". I suspect that Problem B (Pachinko Probability) might be erroneous... (44% wrong answer can be a hint?)

• Maybe there is a trick with the input? Maybe there are 500 machines thus no EOF after the last one?
• Maybe there is some definition ambiguity? Can a declaration of "gate"-ness erase the outgoing edges of a node for example?

Hah, I just tried those two to no avail...

Edit: ah, never mind, I got it.
Edit2: 7th best time
Edit3: ... out of 18

[Solomon]

For Problem A, I started off with a pretty naive algorithm that was only passing half of the test cases. After some digging on special graphs, I find myself reading this paper (1981, Rotem) for Problem A... I'm kind of sure it's the right idea, but we'll see.

[Solomon]

Really puzzled with how much I'm struggling with problem B...it seems like a simple DFS + memo table should get me there, but I'm hitting WA . Some of my test cases below and my output:

TC1: (ignore the purple; gates are marked with (G))

Code: Select all

9
8
0 4
1 4
2 4
3 4
4 5
4 6
4 7
4 8
2
5
7

winning paths 8
total paths 16

TC2:

Code: Select all

12
11
0 2
1 2
1 3
3 4
3 5
5 6
6 8
6 9
5 7
7 10
10 11
3
2
4
9

winning paths 4
total paths 6

TC3: (click image for full size if it's too small to read (800 px limit)):

Code: Select all

26
34
0 1
0 2
0 3
0 4
1 5
1 6
1 7
3 7
3 8
3 9
3 10
4 10
4 11
6 12
6 13
8 14
9 14
10 14
10 15
11 15
11 24
11 16
14 17
15 17
16 17
16 18
16 19
16 20
18 21
18 22
21 23
21 24
12 25
13 25
8
2
5
7
17
19
22
23
24

winning paths 17
total paths 20

I also tried cases where the starting node and the ending node are the same, such as:

Code: Select all

5 1
2 4
0
winning paths 0
total paths 4

Some of my submission errors were from me not being sure if total paths should be 4 or 1; tried both scenarios and nothing came out of it unfortunately . Any help appreciated!

[bernds]

I also tried cases where the starting node and the ending node are the same, such as:

Code: Select all

5 1
2 4
0
winning paths 0
total paths 4

Some of my submission errors were from me not being sure if total paths should be 4 or 1; tried both scenarios and nothing came out of it unfortunately . Any help appreciated!

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.

[Solomon]

I also tried cases where the starting node and the ending node are the same, such as:

Code: Select all

5 1
2 4
0
winning paths 0
total paths 4

Some of my submission errors were from me not being sure if total paths should be 4 or 1; tried both scenarios and nothing came out of it unfortunately . Any help appreciated!

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!

[Solomon]

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!

[ugoertz]

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

[bernds]

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.

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

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.

[peti29]

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.

[bernds]

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.

[quantumf]

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!

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