Co-Authored-By: Claude Sonnet 5.5 <[email protected]> Claude-Session: https://claude.ai/code/session_017ic4b4aCTv6BYCer55YdjZ
17 lines
483 B
Plaintext
17 lines
483 B
Plaintext
Simplifying debts: pairwise vs greedy vs exact
|
|
==============================================
|
|
|
|
Goa trip: 6 pairwise payments, 3 greedy, 3 exact
|
|
|
|
Balances (Rs): a +4, b +3, c +3, d -4, e -6
|
|
greedy: 4 payments
|
|
e pays a Rs 4.00
|
|
d pays b Rs 3.00
|
|
e pays c Rs 2.00
|
|
d pays c Rs 1.00
|
|
exact: 3 payments
|
|
e pays b Rs 3.00
|
|
e pays c Rs 3.00
|
|
d pays a Rs 4.00
|
|
why: {a, d} cancel exactly (+4 -4) and {b, c, e} cancel exactly (+3 +3 -6), so two separate groups need 1 + 2 = 3 payments
|