Share My O(N!) NPC solution, TLE for large case


  • 4
    F
    import java.util.*;
    
    public class Solution {
        public int minTransfers(int[][] trans) {
            Map<Integer, Integer> net = new HashMap<>();
            for(int i = 0; i < trans.length; i++){
                net.put(trans[i][0], net.getOrDefault(trans[i][0], 0) - trans[i][2]);
                net.put(trans[i][1], net.getOrDefault(trans[i][1], 0) + trans[i][2]);
            }
            int[] temp = new int[net.size()];
            int i = 0;
            for(int j : net.values()){
                if(j != 0)temp[i++] = j;
            }
            int[] a = new int[i];
            System.arraycopy(temp, 0, a, 0, i);
            transactions.clear();
            number = Integer.MAX_VALUE;
            mintran(a, 0);
            return number;
        }
    
        private List<int[]> transactions = new ArrayList<>();
        private int number = Integer.MAX_VALUE;
    
        private void mintran(int[] a, int start){
            //System.out.println(Arrays.toString(a));
            if(transactions.size() >= number) return;
            if(number == (a.length + 1)/2) return;
    
            if(a.length < 2){
                number = 0;
                return;
            }else if(a.length == 2) {
                number = a[0] == 0 ? 0 : 1;
                return;
            }else{
                int ind = -1;
                int max = Integer.MIN_VALUE;
                int i = start;
                for(; i < a.length; i++){
                    if(Math.abs(a[i]) > max){
                        max = Math.abs(a[i]);
                        ind = i;
                    }
                }
    
                if(max == 0 || start == a.length){
                    if(transactions.size() < number){
                        number = transactions.size();
                    }
                    return;
                }
    
                int temp = a[ind];
                a[ind] = a[start];
                a[start] = temp;
    
                for(i = start + 1; i < a.length; i++){
                    if(a[i] * a[start] < 0) {
                        transactions.add(new int[]{a[i], a[start]});
                        temp = a[i];
                        a[i] += a[start];
                        mintran(a, start + 1);
                        a[i] = temp;
                        transactions.remove(transactions.size()-1);
                    }
                }
    
                temp = a[ind];
                a[ind] = a[start];
                a[start] = temp;
    
            }
        }
    
        public static void main(String[] args) {
            int[][] A = new int[][] {{0,1,1}, {2,3,2}, {4,5,3}, {6,7,4}, {8,9,5}, {10,11,6}, {12,13,7}, {14,15,2}, {14,16,2}, {14,17,2}, {14,18,2}};
            Solution solution = new Solution();
            System.out.println(solution.minTransfers(A));
        }
    }
    

  • 0
    P

    Lol
    Thank you for sharing.


  • 0

    @fatalme

    It seems your code also fails on the following test case(should be 11 instead of 14):

    [[0,1,1],[2,3,2],[4,5,3],[6,7,4],[8,9,5],[10,11,6],[12,13,7],[14,15,2],[14,16,2],[14,17,2],[14,18,2]]


  • 0
    F

    @Stomach_ache
    It's 11, I just got it. it takes several minutes to compute.


  • 0

    @fatalme

    ohhh, yeah, it's correct.


  • 8
    I

    Thanks for the idea, made some improvement, got accepted, 35ms.

    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;
    }
    

  • 0
    F

    @iaming

    A modified version of the C++ version, only takes 8ms:

    public class Solution {
    
        public int minTransfers(int[][] trans) {
    	
    		Map<Integer, Integer> map = new HashMap<>();
    		for(int[] t : trans){
    			map.put(t[0], map.getOrDefault(t[0], 0) - t[2]);
    			map.put(t[1], map.getOrDefault(t[1], 0) + t[2]);
    		}
    		int[] a = new int[map.size()];
    		int len = 0;
    		for(int v : map.values()){
    			if(v != 0){
    				a[len++] = v;
    			}
    		}
    		
    		if(len == 0) return 0;
    		
    		int[] dp = new int[1 << len];
    		Arrays.fill(dp, Integer.MAX_VALUE/2);
    		//System.out.println(Arrays.toString(a));
    		for(int i = 1; i < dp.length; i++){
    		
    			int sum = 0, count = 0;
    			for(int j = 0; j < len; j++){
    				if((1<<j & i) != 0){
    					sum += a[j];
    					count++;
    				}
    			}
    			
    			if(sum == 0){
    				dp[i] = count - 1;
    				for(int j = 1; j < i; j++){
    					if(((i & j) == j) && dp[j] + dp[i-j] < dp[i]) dp[i] = dp[j] + dp[i - j];
    				}
    			}
    		
    		}
    		
    		return dp[dp.length - 1];
    		
        }
    }
    

  • 0
    I

    @fatalme great, this is better, O(2^2n).


  • 0
    Y

    @iaming said in Share My O(N!) NPC solution, TLE for large case:

    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;
    }

    I tried the following test case with your solution:
    {{1, 8, 1}, {1, 9, 1}, {1, 1000, 1},{2, 8, 10}, {1, 400, 950}, {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}, {200, 800, 100}, {300, 900, 100}, {400, 1000, 1000}, {500, 1100, 10}, {600, 1200, 10}, {700, 1300, 10}}
    The program has already taken hours and is still running....


  • 0
    I

    @yuhaowang001 That is how big n! is, try the 2^2n one.


  • 0
    F

    @yuhaowang001
    Yes, it is that slow, I have optimized the code, and now it takes only 2 days. ;-). And the result is correct:

    public class OptimalAccountBalancing {
        public int minTransfers(int[][] trans) {
            Map<Integer, Integer> net = new HashMap<>();
            for(int i = 0; i < trans.length; i++){
                net.put(trans[i][0], net.getOrDefault(trans[i][0], 0) - trans[i][2]);
                net.put(trans[i][1], net.getOrDefault(trans[i][1], 0) + trans[i][2]);
            }
            int[] temp = new int[net.size()];
            int i = 0;
            for(int j : net.values()){
                if(j != 0)temp[i++] = j;
            }
            int[] a = new int[i];
            System.arraycopy(temp, 0, a, 0, i);
    
            if(a.length == 0){
                return 0;
            }else if(a.length == 2) {
                return 1;
            }
    
            number = Integer.MAX_VALUE;
            mintran(a, 0, new int[]{0});
            return number;
        }
    
        private int number = Integer.MAX_VALUE;
    
        private void mintran(int[] a, int start, int[] res){
            //System.out.println(Arrays.toString(a));
            if(res[0] >= number) return;
            if(number == (a.length + 1)/2) return;
    
            int ind = -1;
            int max = Integer.MIN_VALUE;
            int i = start;
            for(; i < a.length; i++){
                if(Math.abs(a[i]) > max){
                    max = Math.abs(a[i]);
                    ind = i;
                }
            }
    
            if(max == 0 || start == a.length){
                if(res[0] < number){
                    number = res[0];
                    System.out.println(number);
                }
                return;
            }
    
            int temp = a[ind];
            a[ind] = a[start];
            a[start] = temp;
    
            for(i = start + 1; i < a.length; i++){
                temp = a[i];
                if(a[i] * a[start] < 0) {
                    a[i] += a[start];
                    res[0]++;
                    mintran(a, start + 1, res);
                    res[0]--;
                    a[i] = temp;
                }
            }
    
            temp = a[ind];
            a[ind] = a[start];
            a[start] = temp;
    
        }
    
        public static void main(String[] args) {
            int[][] A = new int[][] {{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}};
            OptimalAccountBalancing solution = new OptimalAccountBalancing();
            System.out.println(solution.minTransfers(A));
        }
    }
    
    

  • 0
    S

    Thanks folks for sharing the solution. Really like the idea of using for(int i = 1; i < state; i++) to loop through all possible subsets of current 'state'. My code got TLE as well, as I used very inefficient HashMap to record answer of subsets, recursion to obtain all possible subsets, and String to represent different subsets. The answer it provides is correct though.

        public int minTransfers(int[][] transactions) {
            if(transactions == null || transactions.length == 0) return 0;
            Map<Integer, Long> map = new HashMap<>();
            for(int[] tran : transactions) {
                map.put(tran[0], map.getOrDefault(tran[0], 0L) + (long)tran[2]);
                map.put(tran[1], map.getOrDefault(tran[1], 0L) - (long)tran[2]);
            }
            List<Long> nums = new ArrayList<>(map.size());
            for(Map.Entry<Integer, Long> entry : map.entrySet()) {
                long total = entry.getValue();
                if(total != 0) nums.add(total);
            }
            int n = nums.size();
            if(n == 0) return 0;
            Map<String, long[]> dp = new HashMap<>();
            List<Integer> set = new ArrayList<>(n);
            for(int i = 0; i < n; i++) set.add(i);
            return (int)helper(nums, set, dp)[0];
        }
        private long[] helper(List<Long> nums, List<Integer> set, Map<String, long[]> dp) {
            String state = iString(set);
            long[] res = dp.get(state);
            if(res != null) return res;
            res = new long[2];
            if(set.size() == 1) {
                res[0] = 0;
                res[1] = nums.get(set.get(0));
                dp.put(state, res);
                return res;
            }
            List<Integer> temp = new ArrayList<>();
            List<List<Integer>> permutaion = new ArrayList<>();
            permute(set, 0, temp, permutaion);
            long min = Integer.MAX_VALUE;
            //System.out.println(permutaion + " " + set);
            for(List<Integer> perm : permutaion) {
                List<Integer> other = flip(set, perm);
                long[] left = helper(nums, perm, dp);
                long[] right = helper(nums, other, dp);
                long total = left[0] + right[0];
                total += left[1] == 0 || right[1] == 0 ? 0 : 1;
                min = Math.min(min, total);
            }
            long sum = 0;
            for(int idx : set) sum += nums.get(idx);
            res[0] = min;
            res[1] = sum;
            dp.put(state, res);
            return res;
        }
        private void permute(List<Integer> indices, int i, List<Integer> temp, List<List<Integer>> res) {
            if(i == indices.size()) {
                if(!temp.isEmpty() && temp.size() < indices.size()) res.add(new ArrayList<Integer>(temp));
                return;
            }
            permute(indices, i + 1, temp, res);
            temp.add(indices.get(i));
            permute(indices, i + 1, temp, res);
            temp.remove(temp.size() - 1);
            return;
        }
        private List<Integer> flip(List<Integer> indices, List<Integer> set) {
            List<Integer> res = new ArrayList<>();
            int j = 0;
            for(int i = 0; i < set.size(); i++) {
                while(indices.get(j) != set.get(i)) res.add(indices.get(j++));
                j++;
            }
            while(j < indices.size()) res.add(indices.get(j++));
            return res;
        }
        private String iString(List<Integer> list) {
            StringBuilder sb = new StringBuilder(list.size() * 2);
            for(int i : list) {
                sb.append(i);
                sb.append('#');
            }
            return sb.toString();
        }
    

  • 0
    This post is deleted!

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.