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 [email protected]
To unsubscribe from this group, send email to [EMAIL PROTECTED]
For more options, visit this group at
http://groups-beta.google.com/group/algogeeks
-~----------~----~----~----~------~----~------~--~---
