Re: [Bug-gnubg] OT: An algorithm problem

[Øystein Johansen]

> Here's my idea :
>
> Let's name S and T the two vectors.
>
> F = {Fx = [S[i],T[j]] such that i+j+2=k}
> (the +2 coming from python indexing starting at 0)

Yes, this was also one of my first ideas. (Keeping two index i, j  in 
each array and having the sum of i and j fixed). I even suggested this 
solution to the lecturer, who didn't have a clue at that moment, and he 
claimed that this would work. He says he has implemented a MATLAB code 
that does this.

[snip]

Your code seems to work, however Joseph, found an even simpler way
by using the i+j>k constrain as the end of iteration indicator. Really 
clever and simple to implement.

I will take a look at Jims implementation as well. It really looks rigid
but I'm not sure which method it uses. At first sight it looks like his 
idea is the same as Josephs, just more code.

> Seems to work for me .... and it looks O(ln k)

Seems to work here as well, and you implementation does all the 
preprocessing as well. Good work.

Thanks everyone!
-Øystein

(I'll write you a whining about this course in a minute)