you're right. I didn't understand it. your solution is correct. My
version would only work in cases in which we didn't need to print the
same minimum sum as many times as it appears. . .but it wouldn't even
be very good at this.
In other words, I solved a completely different problem, yes?
On Dec 1, 5:58 am, "arxor" <[EMAIL PROTECTED]> wrote:
> 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
-~----------~----~----~----~------~----~------~--~---
