progress

~/problems / Advanced DP / Bitmask DP

Optimal Account Balancing

On a phone? Coding is easier on a laptop: email this problem to yourself . Meanwhile: quiz this topic or fight a boss.

hard ~45 min RipplingSalesforcePinterest

A group of friends shares costs on a trip. Each entry [payer, other, amount] in transactions means payer paid amount on behalf of other, so other owes payer that much. People are numbered 0 to 15.

At the end of the trip they settle up. A transfer is one payment of any amount from one person to another. Write min_transfers(transactions) -> int that returns the fewest transfers that leave everyone even.

Each person's balance is what they paid for others minus what others paid for them. A positive balance means they are owed money, a negative one means they owe it. Everyone is even once the transfers bring every balance to zero. The transfers don't have to follow the original entries: anyone may pay anyone.

min_transfers([[0, 1, 30], [1, 2, 30]])
# 1   (balances 0: +30, 1: 0, 2: -30; person 2 pays person 0 directly)

min_transfers([[0, 3, 7], [1, 4, 4], [2, 4, 2], [2, 0, 1]])
# 3   (balances +6, +4, +3, -7, -6: person 4 pays 0 six; person 3 pays 1 four and 2 three)

min_transfers([[0, 1, 5], [1, 2, 5], [2, 0, 5]])
# 0   (everyone paid 5 and had 5 paid for them)

In the second example, always settling the biggest debt against the biggest credit takes 4 transfers: 0 gets 6 from 3, then 1 gets 4 from 4, then 2 gets 2 from 4 and 1 from 3.

Constraints:

  • 1 <= len(transactions) <= 1000.
  • 0 <= payer, other <= 15 and payer != other. 1 <= amount <= 10^5.
  • ⭐ Bonus: settling one person at a time and trying every partner (backtracking) is fine for up to about 10 people with a non-zero balance. A speed test with 16 such people earns a star in about O(2^m · m), where m is the number of people whose balance isn't zero.
Show hint

After working out the balances, people at zero drop out. If g people's balances add up to zero, they can settle among themselves in g - 1 transfers, and a group that sums to zero can never do it in fewer. So you want to split the m people into as many zero-sum groups as possible. With m <= 16, you can afford to look at every subset.

Topic: Bitmask DP. dp[mask][last] over subsets (n <= ~20): TSP, assignment.

0:00
Ctrl ' run · Ctrl ↵ submit
esc