Hi, ljb, Let me have a try to prove the correctness of it.
Let define a property A(S) : S is a set of ordered pair (i,j), and every pair (x,y) whose sum(x,y) is less than min{S} = sum(mi,mj) is already output. Initially, we have S_1 = {(1,1)}, A(S_1) holds. Suppose that for n, A(S_n) holds, then we construct S_(n + 1) by letting S_(n + 1) = S_n \ {(mi,mj)} U {(mi,mj+1),(mi+1,mj)} where (mi, mj) is in S_n, sum(mi, mj) = min{S_n}, and we can prove that A(S_(n + 1)) holds. To verify the algorithm partially, we can try to solve the problem: http://acm.pku.edu.cn/JudgeOnline/problem?id=2442 and my solution got Accepted. Please correct me if I'm wrong. Best regards. On Dec 1, 5:01 pm, "ljb" <[EMAIL PROTECTED]> wrote: > I dont understant how you deal with multiple involvement. --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups-beta.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---