The Programming Riddles Thread!

[eLiu]

Not independent. If you have two bachelors and both want one hooker and one blow, you need to make one triplet. Independent distribution could cause the hooker and blow to go to different bachelors and you'd have zero triplets.

Yup, that's one issue. The other issue is say two guys want hooker1 & they're happy with any blow. You could end up matching both of them to hooker1, but hooker1 can only be *used* once You cannot do two independent bipartite matchings and just try to mesh them together.

iCyborg, your solution (as stated at least) will not work for the same reason. Say you |F|=|G|=|H|=2 and <f_1,g_1,h_1> and <f_2,g_1,h_2> are both valid triples. Your scheme would produce a matching of size 2, even though g_1 would be used twice. It might be possible to add more edges and/or nodes to resolve this issue? But I don't see it right now.

FYI, the time complexity of maximum matching (on any graph; bipartite doesn't win anything in the unweighted case) is O(sqrt(V)*E). For you current graph, V = |F| + |G|*|H|, E = O(V^2). Even if it did produce the right answer, you can do better.

Pia: Yes, tripartite matching is NP complete. If I could solve tripartite matching, I could solve this problem. But if I could solve this problem, I could not solve tripartite matching. The issue is in the preferences. In this problem, only the gentlemen (F) get preferences. So this problem is a (very) special case of tripartite matching.

Another example if my statement isn't clear: we know subset sum is NP. What about subset sum with exactly 2 integers per subset? 3 integers? 4? (They're all polynomial... granted the power is a function of the number of integers. Neat exercise to derive that function if you haven't seen it.) Knowing how to solve subset sum will solve all of these individual problems, but knowing how to solve these individual problems does not solve subset sum. Even goofier example: traveling salesman on a (circularly) linked list is really easy!

Don't worry, I wouldn't stick an NP problem on here, haha.

 

[Ken g6]

#1 is

Spoiler

Floyd's Cycle-Finding Algorithm

. It happens to be something I would use if I ever wrote a fixed-N GPU sieve for PrimeGrid.

#2 might be a

Spoiler

network flow problem

, but I'm really not good at those.

 

[eLiu]

#1 is

Spoiler

Floyd's Cycle-Finding Algorithm

. It happens to be something I would use if I ever wrote a fixed-N GPU sieve for PrimeGrid.

#2 might be a

Spoiler

network flow problem

, but I'm really not good at those.

#1: Neat, I didn't know it had a name. Wiki-searching that turns up a 'common' name using 2 animals, which I have heard of from primality testing before. What is a fixed-N sieve? I don't remember enough of my discrete math bits to have any idea on what the best primality testers are in practice, but sounds like you're telling me this is a good one.

#2: Yes, that is the right type of problem... that class is amongst my favorite type of problems, haha. But figuring out how to use that stuff to solve the problem is the tricky bit; it's not straightforward (or I didn't think so anyway).

 

[Ken g6]

*sigh* I always get those backwards. http://primegrid.wikia.com/wiki/Fixed-K_sieve is what I meant.

 

[iCyborg]

iCyborg, your solution (as stated at least) will not work for the same reason. Say you |F|=|G|=|H|=2 and <f_1,g_1,h_1> and <f_2,g_1,h_2> are both valid triples. Your scheme would produce a matching of size 2, even though g_1 would be used twice. It might be possible to add more edges and/or nodes to resolve this issue? But I don't see it right now.

Nah, I realized it wasn't good on my own later. I saw that it was tripartite and knew it was NP so I thought I had seen a way to get around it, but nope, wrong approach.

Network flow is quite related to graph matching. Now that you've told us the method, how about:
(for every member of F, G, H there's a vertex + S, T, source and sink)
S (source) is connected to every vertex from H, for every preference <f,h> we make an edge from the corresponding vertices in H to F, and then for every preference <f,g> we make an edge from F to G. And then from every G to T. Basically putting F between H and G (or G and F).
All the capacities would be 1 obviously. No idea about complexities without consulting some algorithm book. Actually, can't really remember any algorithms either, though I remember some names

Added: forgot that it needs capacities on vertices of H,G,F as well, not just edges.

 

[eLiu]

Nah, I realized it wasn't good on my own later. I saw that it was tripartite and knew it was NP so I thought I had seen a way to get around it, but nope, wrong approach.

Network flow is quite related to graph matching. Now that you've told us the method, how about:
(for every member of F, G, H there's a vertex + S, T, source and sink)
S (source) is connected to every vertex from H, for every preference <f,h> we make an edge from the corresponding vertices in H to F, and then for every preference <f,g> we make an edge from F to G. And then from every G to T. Basically putting F between H and G (or G and F).
All the capacities would be 1 obviously. No idea about complexities without consulting some algorithm book. Actually, can't really remember any algorithms either, though I remember some names

Added: forgot that it needs capacities on vertices of H,G,F as well, not just edges.

Sweet, congrats That's almost the max-flow version.

Spoiler

You can convert from having vertex capacities to edge capacities instead. You actually don't need vertex capacities on the G and H guys (why?). For F, duplicate every vertex. Connect each vertex to its copy w/an edge of capacity 1--voila, vertex capacity converted to edge capacity.

Now you can use classic max flow which get times like O(V^2*E) (blocking flow or push relabel) or O(V*E^2) (edmonds karp--augmenting paths); some fancier ones exist that get like O(V*E*log(??)) (?? b/c i forget; this is like blocking flow w/a fancy data structure i think?). At least one of those algorithms has an even better special case for graphs w/unit capacities. This is what I came up with initially too... but there's something even better.

I'll give you some hints--

Spoiler

maximum matching sounds good.

And

Spoiler

you can even use the same graph that you stated w/my modification.

You guys are quick, I thought these would take longer

 

[iCyborg]

Well, you've practically given us the answer, I suppose you want the explanation why it's correct:
So the graph is as you've described, without S and T.
Let's say that there are n people, or |F| = n. If we set just the n edges between F pairs, we will get a matching of size n, so max is more than that. Let's suppose that A is the maximum matching. We can look at how many hookups does it generate, let's say k. For all the non-hooked f (pairs of corresponding vertices) either there's no edge from H-F or from F-G (or neither, but then we put between the f pair), so the two vertices for some f are connected to a total of one edge. All the hooked ones have both H-F and F-G, so the two of them are incidental to 2. In other words, if A has size n+k, there are exactly k hookups
Now, let's suppose that we can generate k+1 hookups -> we can connect the corresponding edges so we will have 2*(k+1), and for the other n-(k+1)=n-k-1 f pairs we can connect the pairs at the worst since there's always an edge between them. In other words, we have a matching with 2k+2 + n-k-1 = n+k+1 edges which is a contradiction with A being the maximum matching. So A has the max hookups, in other words maximum matching algorithm on the graph will solve the problem. According to the net, we can do that in O(E*sqrt(V)).

 

[eLiu]

Well, you've practically given us the answer, I suppose you want the explanation why it's correct:
So the graph is as you've described, without S and T.
Let's say that there are n people, or |F| = n. If we set just the n edges between F pairs, we will get a matching of size n, so max is more than that. Let's suppose that A is the maximum matching. We can look at how many hookups does it generate, let's say k. For all the non-hooked f (pairs of corresponding vertices) either there's no edge from H-F or from F-G (or neither, but then we put between the f pair), so the two vertices for some f are connected to a total of one edge. All the hooked ones have both H-F and F-G, so the two of them are incidental to 2. In other words, if A has size n+k, there are exactly k hookups
Now, let's suppose that we can generate k+1 hookups -> we can connect the corresponding edges so we will have 2*(k+1), and for the other n-(k+1)=n-k-1 f pairs we can connect the pairs at the worst since there's always an edge between them. In other words, we have a matching with 2k+2 + n-k-1 = n+k+1 edges which is a contradiction with A being the maximum matching. So A has the max hookups, in other words maximum matching algorithm on the graph will solve the problem. According to the net, we can do that in O(E*sqrt(V)).

Haha well you weren't supposed to read the hints right off the bat...

My thinking was that if someone wanted to work on it and got stuck, they could read the hints (w/the 2nd hint being much stronger than the first) at their own pace if they get stuck. Also b/c I was afraid I'd do what I did & completely forget about this thread. So, sorry if I gave it away :/

 

[Borealis7]

ok, lets stop the Discrete Math nonsense and get back to riddles!

here's an easy one. like i said earlier, i can sort a set of N integers in the range [0..K], in O(N + K) complexity. assuming no Memory restrictions, how do i do that?

and here's something to think about: (not a hint, but read it after you got a solution)

Spoiler

it shouldn't come as a surprise that i can do this sort in what appears to be less than O(NLogN) complexity, because its not. after all, in most cases N <<< K. so if i sort in O(K) complexity and K > NLogN then its not really that effective. but if N = O(K) then fire away and sort quickly!

 

[iCyborg]

Haha well you weren't supposed to read the hints right off the bat...

My thinking was that if someone wanted to work on it and got stuck, they could read the hints (w/the 2nd hint being much stronger than the first) at their own pace if they get stuck. Also b/c I was afraid I'd do what I did & completely forget about this thread. So, sorry if I gave it away :/

I had already thought about it earlier, didn't see a way, and I didn't want to spend much time pondering about it. So I went straight for the hints


@Borealis
How is an algorithm for a specific matching problem + complexity discussion discrete math nonsense, and algorithm for a specific sorting problem + complexity question not? Looks like if you want the math nonsense to stop, then we shouldn't answer your question for the exact same reasons either

 

[Borealis7]

because my question doesn't involve math. i just want a psuedo-code answer, not a full complexity analysis. the point is funding the trick that does what i ask, and its for funz!

discrete math is not fun...

 

[iCyborg]

If you read my previous post more carefully (or at all), you'd see that the only complexity analysis was a single quote for the complexity of the matching algorithm. The rest was explaining why eLiu's stuff works. Your hint contains 3x more complexity analysis than my post. And math is fun
I think the solution may have even been mentioned in this thread: some sort of counting sort, it's well known these have O(n+k) complexity and are applicable to cases like these.