## Monday, November 21, 2016

### LeetCode 465 － Optimal Account Balancing

A group of friends went on holiday and sometimes lent each other money. For example, Alice paid for Bill's lunch for \$10. Then later Chris gave Alice \$5 for a taxi ride. We can model each transaction as a tuple (x, y, z) which means person x gave person y \$z. Assuming Alice, Bill, and Chris are person 0, 1, and 2 respectively (0, 1, 2 are the person's ID), the transactions can be represented as `[[0, 1, 10], [2, 0, 5]]`.
Given a list of transactions between a group of people, return the minimum number of transactions required to settle the debt.
Note:
1. A transaction will be given as a tuple (x, y, z). Note that `x ≠ y` and `z > 0`.
2. Person's IDs may not be linear, e.g. we could have the persons 0, 1, 2 or we could also have the persons 0, 2, 6.
Example 1:
```Input:
[[0,1,10], [2,0,5]]

Output:
2

Explanation:
Person #0 gave person #1 \$10.
Person #2 gave person #0 \$5.

Two transactions are needed. One way to settle the debt is person #1 pays person #0 and #2 \$5 each.
```
Example 2:
```Input:
[[0,1,10], [1,0,1], [1,2,5], [2,0,5]]

Output:
1

Explanation:
Person #0 gave person #1 \$10.
Person #1 gave person #0 \$1.
Person #1 gave person #2 \$5.
Person #2 gave person #0 \$5.

Therefore, person #1 only need to give person #0 \$4, and all debt is settled.```

```统计每个人借出/借入的金钱总数

def minTransfers(self, transactions): """ :type transactions: List[List[int]] :rtype: int """ vdict = collections.defaultdict(dict) def solve(rich, poor): rlen, plen = len(rich), len(poor) if min(rlen, plen) <= 1: return max(rlen, plen) ri = pi = 0 rich.sort() poor.sort() trich, tpoor = tuple(rich), tuple(poor) ans = vdict[trich].get(tpoor) if ans is not None: return ans ans = 0x7FFFFFFF for ri in range(rlen): for pi in range(plen): nrich = rich[:ri] + rich[ri+1:] npoor = poor[:pi] + poor[pi+1:] if rich[ri] == poor[pi]: ans = min(solve(nrich, npoor) + 1, ans) elif rich[ri] > poor[pi]: ans = min(solve(nrich + [rich[ri] - poor[pi]], npoor) + 1, ans) else: ans = min(solve(nrich, npoor + [poor[pi] - rich[ri]]) + 1, ans) vdict[trich][tpoor] = ans return ans loan = collections.defaultdict(int) for s, t, v in transactions: loan[s] += v loan[t] -= v rich = [v for k, v in loan.iteritems() if v > 0] poor = [-v for k, v in loan.iteritems() if v < 0] return solve(rich, poor)

https://discuss.leetcode.com/topic/68755/share-my-o-n-npc-solution-tle-for-large-case/2
``````public int minTransfers(int[][] transactions) {
Map<Integer, Integer> net = new HashMap<>();
for (int[] t : transactions) {
net.put(t[0], net.getOrDefault(t[0], 0) - t[2]);
net.put(t[1], net.getOrDefault(t[1], 0) + t[2]);
}
int[] a = new int[net.size()];
int cnt = 0;
for (int v : net.values()) {
if (v != 0) a[cnt++] = v;
}
return helper(a, 0, cnt, 0);
}
int helper(int[] a, int start, int n, int num) {
int ans = Integer.MAX_VALUE;
while(start < n && a[start] == 0) start++;
for (int i = start + 1; i < n; ++i) {
if (a[i] < 0 && a[start] > 0 || a[i] > 0 && a[start] < 0) {
a[i] += a[start];
ans = Math.min(ans, helper(a, start + 1, n, num + 1));
a[i] -= a[start];
}
}
return ans == Integer.MAX_VALUE ? num : ans;
}``````
X.
https://discuss.leetcode.com/topic/68740/looks-that-this-is-a-wrong-question-the-expected-solution-didn-t-consider-this-case/14
The question can be transferred to a 3-partition problem, which is NP-hard.
http://www.mathmeth.com/tom/files/settling-debts.pdf

in the problem, construct an isolated system. It mean the total amount of money in the system keeps constant. Thus, what matters is the amount of extra money each person have after all transactions complete. For example, if id1 gave id2 5\$, then after that transaction id1's money decreased to 5\$, on the contrary id2's money increased to 5\$. That way, we know how did change account of each person. For imagination let's consider the following input [[1,2,3],[2,3,5], [4,1,6]]:
``````           id|  trans |  total |
---------------------
1 | -3 + 6 |   +3   |
---------------------
2 | +3 - 5 |   -2   |
----------------------
3 |    +5  |   +5   |
----------------------
4 |    -6  |   -6   |
----------------------
``````
Now, we have some negative account changes and positive account changes. By the way it is not hard to see that they compensate each other. Now, our task is to balance the accounts, by performing minimal amount of transactions. For instance we can balance these accounts, by performing the following transactions: [1,2,2], [3,4,5], [1,4,1]. After that, all accounts become balanced, i.e 0 extra money in total. But we have performed 3 transactions. Can we do better? May be. The number of transactions depend on the order of pairs taking part in each transaction. Consequently, the next question is, 'how to know which set of pairs give minimum number of transactions?'. One solution idea is just, brute force through all pairs and just take the minimum number of transactions. Another idea is just take some random combinations of pairs and take the minimum number of trans so far.
P.S: May be there are other elegant and exact solutions and this solution doesn't pretend to the best one, but it is quite reasonable. The more random shuffles you do, the more probability of hitting the answer. For that test cases 1000 is enough, may be less...
``````                if(n == p) continue;
if(n>p){
stNeg.push(n-p);
} else {
stPos.push(p-n);
}
``````
there are three cases (let's assume the persons are Person N and Person P):
1. n == p: P pays N \$p
2. n > p: P pays N \$p
3. n < p: P pays N \$n
Basically, P pays N with all money he owns (n >= p), or P pays N in full (n < p).
However, this missed the case that P pays N \$x, where \$x < p and \$x < n.
For example, the first person of (2, 50, 50, ..., 50) could pay \$1 to both the first and last person of (51, 50, 50, ..., 50, 51), and get the minimal number of transactions. (This may not be a good example, but you know what I mean.)
I considered only the cases when some of the pairs pays off to close others account. Now, question is what if a pair makes transaction with some x\$, where x<p and x< n and achieve minimal amount of transactions? Intuitively, such kind of transaction cannot decrease the total amount of transactions. Because, it doesn't change the state of the isolated system (total money flow doesn't change). But i think it is provable too.
``````    public int minTransfers(int[][] transactions) {
if(transactions == null || transactions.length == 0) return 0;
Map<Integer, Integer> acc = new HashMap<>();
for(int i = 0;i<transactions.length;i++){
int id1 = transactions[i][0];
int id2 = transactions[i][1];
int m = transactions[i][2];
acc.put(id1, acc.getOrDefault(id1, 0)-m);
acc.put(id2, acc.getOrDefault(id2, 0)+m);
}
List<Integer> negs = new ArrayList<>();
List<Integer> poss = new ArrayList<>();
for(Integer key:acc.keySet()){
int m = acc.get(key);
if(m == 0) continue;
}
int ans = Integer.MAX_VALUE;
Stack<Integer> stNeg = new Stack<>(), stPos = new Stack<>();
for(int i =0;i<1000;i++){
for(Integer num:negs) stNeg.push(num);
for(Integer num:poss) stPos.push(num);
int cur = 0;
while(!stNeg.isEmpty()){
int n = stNeg.pop();
int p = stPos.pop();
cur++;
if(n == p) continue;
if(n>p){
stNeg.push(n-p);
} else {
stPos.push(p-n);
}
}
ans = Math.min(ans, cur);
Collections.shuffle(negs);
Collections.shuffle(poss);
}
return ans;
}``````
{{1, 8, 1}, {1, 9, 1}, {2, 8, 10}, {3, 9, 20}, {4, 10, 30}, {5, 11, 40}, {6, 12, 50}, {7, 13, 60}, {20, 80, 10}, {30, 90, 20}, {40, 100, 30}, {50, 110, 40}, {60, 120, 50}, {70, 130, 60}}
Yes, I see. Thank you for pointing out! But I think the reason is randomization, not that type of transactions you mentioned. My solution takes 1000 random permutations. But actually, it worth considering all permutations. So in that case the algorithm would run O(n!) time. After i increased the number of iterations up 100000, My solution started to churning out answers from 18 - 14. Therefore I decided to add some simple correction to perform obvious transactions first:
``````        int base = 0;
for(Integer key:negInts.keySet()){

if(!posInts.containsKey(key) ||  posInts.get(key) == 0 || negInts.get(key) == 0) continue;
int p = posInts.get(key);
int n = negInts.get(key);
base += Math.min(n,p);
if(p == n){
posInts.put(key, 0);
negInts.put(key, 0);
continue;
}
if(p>n){
posInts.put(key, p-n);
negInts.put(key, 0);
continue;
}
if(n>p){
posInts.put(key, 0);
negInts.put(key, n-p);
continue;
}
}
for(Integer key:negInts.keySet()){
if(negInts.get(key) == 0) continue;
}
for(Integer key:posInts.keySet()){
if(posInts.get(key) == 0) continue;
}
``````
The code above first makes transactions where we can balance two accounts by one transaction. It means where n == p. So the rest of the accounts are balanced randomly. Now the code gives correct answers with higher probability.
``````public class Solution {
public int minTransfers(int[][] transactions) {
if(transactions == null || transactions.length == 0) return 0;
Map<Integer, Integer> acc = new HashMap<>();
for(int i = 0;i<transactions.length;i++){
int id1 = transactions[i][0];
int id2 = transactions[i][1];
int m = transactions[i][2];
acc.put(id1, acc.getOrDefault(id1, 0)-m);
acc.put(id2, acc.getOrDefault(id2, 0)+m);
}
// int neg = 0, pos = 0;
List<Integer> negs = new ArrayList<>();
List<Integer> poss = new ArrayList<>();
HashMap<Integer, Integer> negInts = new HashMap<>();
HashMap<Integer, Integer> posInts = new HashMap<>();
for(Integer key:acc.keySet()){
int m = acc.get(key);
if(m == 0) continue;
if(m<0) negInts.put(-m, negInts.getOrDefault(-m,0)+1);
else posInts.put(m, posInts.getOrDefault(m,0)+1);
}
int base = 0;
for(Integer key:negInts.keySet()){

if(!posInts.containsKey(key) ||  posInts.get(key) == 0 || negInts.get(key) == 0) continue;
int p = posInts.get(key);
int n = negInts.get(key);
base += Math.min(n,p);
if(p == n){
posInts.put(key, 0);
negInts.put(key, 0);
continue;
}
if(p>n){
posInts.put(key, p-n);
negInts.put(key, 0);
continue;
}
if(n>p){
posInts.put(key, 0);
negInts.put(key, n-p);
continue;
}
}
for(Integer key:negInts.keySet()){
if(negInts.get(key) == 0) continue;
}
for(Integer key:posInts.keySet()){
if(posInts.get(key) == 0) continue;
}
int ans = Integer.MAX_VALUE;
Stack<Integer> stNeg = new Stack<>(), stPos = new Stack<>();
for(int i =0;i<=1000;i++){
for(Integer num:negs) stNeg.push(num);
for(Integer num:poss) stPos.push(num);
int cur = base;
while(!stNeg.isEmpty()){
int n = stNeg.pop();
int p = stPos.pop();
cur++;
if(n == p) continue;
if(n>p){
stNeg.push(n-p);
} else {
stPos.push(p-n);
}
}
ans = Math.min(ans, cur);
Collections.shuffle(negs);
Collections.shuffle(poss);
}
return ans;
}
}``````
1.     public int minTransfers(int[][] transactions) {
2.         Map<Integer, Integer> balances = new HashMap<>();
3.         for(int[] tran: transactions) {
4.             balances.put(tran[0], balances.getOrDefault(tran[0], 0) - tran[2]);
5.             balances.put(tran[1], balances.getOrDefault(tran[1], 0) + tran[2]);
6.         }
7.         List<Integer> poss = new ArrayList<>();
8.         List<Integer> negs = new ArrayList<>();
9.         for(Map.Entry<Integer, Integer> balance : balances.entrySet()) {
10.             int val = balance.getValue();
11.             if (val > 0) poss.add(val);
12.             else if (val < 0) negs.add(-val);
13.         }
14.         int min = Integer.MAX_VALUE;
15.         Stack<Integer> ps = new Stack<>();
16.         Stack<Integer> ns = new Stack<>();
17.         for(int i = 0; i < 10; i++) {
18.             for(int pos: poss) {
19.                 ps.push(pos);
20.             }
21.             for(int neg: negs) {
22.                 ns.push(neg);
23.             }
24.             int count = 0;
25.             while (!ps.isEmpty()) {
26.                 int p = ps.pop();
27.                 int n = ns.pop();
28.                 if (p > n) {
29.                     ps.push(p - n);
30.                 } else if (p < n) {
31.                     ns.push(n - p);
32.                 }
33.                 count++;
34.             }
35.             min = Math.min(min, count);
36.             Collections.shuffle(poss);
37.             Collections.shuffle(negs);
38.         }
39.         return min;
40.     }

X. greedy - which not get best solution
https://discuss.leetcode.com/topic/68733/java-recursion
``````    public int minTransfers(int[][] transactions) {
//I thought it's kind of network flow problem
Map<Integer,Integer> map = new HashMap<>();
for(int[] t : transactions){
map.put(t[1],map.getOrDefault(t[1],0)-t[2]);
map.put(t[0],map.getOrDefault(t[0],0)+t[2]);
}
int[] count = new int[1];
helper(map,count);
return count[0];
}
//this getMax() and getMin() function is to get the index(key) of the MaxValue and MinValue
private int getMax(Map<Integer,Integer> map){
int max = -1;
for(Map.Entry<Integer,Integer> entry : map.entrySet()){
if(max == -1) max = entry.getKey();
else if(entry.getValue() > map.get(max)){
max = entry.getKey();
}
}
return max;
}
private int getMin(Map<Integer,Integer> map){
int min = -1;
for(Map.Entry<Integer,Integer> entry : map.entrySet()){
if(min == -1) min = entry.getKey();
else if(entry.getValue() < map.get(min)){
min = entry.getKey();
}
}
return min;
}

private void helper(Map<Integer,Integer> map, int[] count){
int max = getMax(map);
int min = getMin(map);
//This means richest one and poorest one are both \$0, means balance.
if(map.get(max) == 0 && map.get(min) == 0) return;
//Or we get the min abs value of max and min
int minValue = Math.min(map.get(max),-map.get(min));
//let the richest give the poorest the as much as possible money
map.put(max, map.get(max)-minValue);
map.put(min, map.get(min)+minValue);
//after done this, add the count
count[0]++;
helper(map,count);
}``````

A, B, 2
A, C, 4
B, D, 5
C, D, 4
D, E, 7

A, -6
B, -3
C, 0
D, 2
E, 7
. 1point 3acres 璁哄潧

A -3,
B -2,
C, 0
D, 2
E, 3.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�

private List<int[]> transactions = new ArrayList<>();
private List<int[]> finaltransactions = new ArrayList<>();
private int number = Integer.MAX_VALUE;

private void mintran(int[] a, int start){

if(a.length < 2). 1point 3acres 璁哄潧
return;
else if(a.length == 2) {
if(a[0] != 0){
}
return;
}else{
int ind = -1;. From 1point 3acres bbs
int max = Integer.MIN_VALUE;
int i = start;
for(; i < a.length; i++){.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
if(Math.abs(a[i]) > max){. 鍥磋鎴戜滑@1point 3 acres
max = Math.abs(a[i]);.1point3acres缃�
ind = i;
}.鏈枃鍘熷垱鑷�1point3acres璁哄潧
}

if(max == 0 || start == a.length){
if(transactions.size() < number){. visit 1point3acres.com for more.
finaltransactions = new ArrayList<>(transactions);
number = transactions.size();
}
return;
}

int temp = a[ind];.鏈枃鍘熷垱鑷�1point3acres璁哄潧
a[ind] = a[start];
a[start] = temp;

for(i = start + 1; i < a.length; i++){
if(a[i] * a[start] < 0) {. 1point 3acres 璁哄潧
temp = a[i];. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
a[i] += a[start];
mintran(a, start + 1);. 1point 3acres 璁哄潧
a[i] = temp;
transactions.remove(transactions.size()-1);
}
}

temp = a[ind];. 1point 3acres 璁哄潧
a[ind] = a[start];
a[start] = temp;

}
}
payOnce每次产生的list长度应该是lender的个数*borrower的个数，即为a*b, a+b=n (总人数)。在pay函数里，queue的长度应该按a*b为等比数列增加吗？那最后不就是(a*b)^n?
1.         class Balance {
2.                 int level;
3.                 List<Integer> lender;
4.                 List<Integer> borrower;
5. . Waral 鍗氬鏈夋洿澶氭枃绔�,
6.                 Balance(int level, List<Integer> posVals, List<Integer> negVals) {. 1point3acres.com/bbs
7.                         this.level = level;
8.                         lender = posVals;
9.                         borrower = negVals;
10.                 }

11.                 public List<Balance> payOnce() {.1point3acres缃�
12.                         List<Balance> ans = new ArrayList<>();
13.                         for (int i = 0; i < lender.size(); i++)
14.                                 for (int j = 0; j < borrower.size(); j++) {. From 1point 3acres bbs
15.                                         int pos = lender.get(i);
16.                                         int neg = borrower.get(j);
17.                                         List<Integer> newLender = new ArrayList<>(lender);
18.                                         List<Integer> newBorrower = new ArrayList<>(borrower);
19.                                         newLender.remove(i);
20.                                         newBorrower.remove(j);. 1point 3acres 璁哄潧

21.                                         int diff = pos + neg;
22.                                         if (diff > 0)
24.                                         else if (diff < 0)

26.                                         ans.add(new Balance(level + 1, newLender, newBorrower));
27.                                 }. 鐗涗汉浜戦泦,涓€浜╀笁鍒嗗湴
28.                         return ans;. Waral 鍗氬鏈夋洿澶氭枃绔�,
29.                 }. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
30. .鏈枃鍘熷垱鑷�1point3acres璁哄潧
31.                 public boolean balanced() {
32.                         return lender.isEmpty() && borrower.isEmpty();
33.                 }
34. .鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
35.                 public String toString() {
36.                         return borrower.toString() + ", " + lender.toString()
37.                                         + ", # of payments: " + level;
38.                 }
39.         }
40. . 涓€浜�-涓夊垎-鍦帮紝鐙鍙戝竷
41.         public int pay(int[] paid) {
42.                 int n = paid.length;
43.                 long total = 0;.鐣欏璁哄潧-涓€浜�-涓夊垎鍦�
44.                 for (int amount : paid) {
45.                         total += amount;
46.                 }
47.                 if (total % n != 0).1point3acres缃�
48.                         throw new IllegalArgumentException(
49.                                         "Total amount can not be evenly divided.");. 鐣欏鐢宠璁哄潧-涓€浜╀笁鍒嗗湴
50.                 int avg = (int) total / n;

51.                 List<Integer> pos = new ArrayList<>();
52.                 List<Integer> neg = new ArrayList<>();
53.                 for (int amount : paid) {
54.                         int diff = amount - avg;
55.                         if (diff > 0)
57.                         else if (diff < 0)
59.                 }
60. . From 1point 3acres bbs
61.                 Balance initialBalance = new Balance(0, pos, neg);
62.                 Queue<Balance> queue = new LinkedList<>();
63.                 queue.offer(initialBalance);
64.                 int ans = Integer.MAX_VALUE; 鏉ユ簮涓€浜�.涓夊垎鍦拌鍧�.
65.                 while (true) {
66.                         Balance cur = queue.poll();
67.                         System.out.println(cur);
68.                         if (cur.balanced()) {. 1point 3acres 璁哄潧
69.                                 ans = cur.level;
70.                                 break;
71.                         }
72.                         List<Balance> nextLevel = cur.payOnce();
73.                         for (Balance newBalance : nextLevel)
74.                                 queue.offer(newBalance);. Waral 鍗氬鏈夋洿澶氭枃绔�,
75.                 }

76.                 return ans;
77.         }