Sort by

recency

|

168 Discussions

|

1 week ago+ 1 comment

Solution in Python

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'cutTheTree' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. INTEGER_ARRAY data
#  2. 2D_INTEGER_ARRAY edges
#
sys.setrecursionlimit(10**7)

class Vertex:
    def __init__(self, value):
        self.value = value
        self.edges = []
        self.is_init = False
    
    def add_edge(self, vertex):
        self.edges.append(vertex)
        
def init(vertex, parent, sum_cache):
    vertex.is_init = True
    subtotal = vertex.value
    for adj in vertex.edges:
        if adj is not parent:
            subtree_sum = init(adj, vertex, sum_cache)
            sum_cache[(vertex, adj)] = subtree_sum
            sum_cache[(adj, vertex)] = sum_cache_total - subtree_sum
            subtotal += subtree_sum
    return subtotal

def min_diff(vertices, sum_cache, total_sum):
    min_diff_value = total_sum
    for v in vertices:
        for adj in v.edges:
            diff = abs(total_sum - 2 * sum_cache[(v, adj)])
            if diff < min_diff_value:
                min_diff_value = diff
    return min_diff_value

N = int(sys.stdin.readline())
values = list(map(int, sys.stdin.readline().split()))
vertices = [Vertex(val) for val in values]
for _ in range(N - 1):
    a, b = map(int, sys.stdin.readline().split())
    vertices[a - 1].add_edge(vertices[b - 1])
    vertices[b - 1].add_edge(vertices[a - 1])

sum_cache = {}
sum_cache_total = sum(values)
init(vertices[0], None, sum_cache)
result = min_diff(vertices, sum_cache, sum_cache_total)
print(result)

2 months ago+ 0 comments

!/bin/python3

simpelst one and solvable one i tried

import math import os import random import re import sys sys.setrecursionlimit(10**6)

def cutTheTree(data, edges): n = len(data) # adjacency (1-based nodes): convert to 0-based indices adj = [[] for _ in range(n)] for u, v in edges: u -= 1; v -= 1 adj[u].append(v) adj[v].append(u)

total = sum(data)
subtree = [0] * n
visited = [False] * n

def dfs(u, parent):
    s = data[u]
    for v in adj[u]:
        if v == parent:
            continue
        s += dfs(v, u)
    subtree[u] = s
    return s

dfs(0, -1)  # root at node 0 (original node 1)

ans = float('inf')
for u in range(1, n):  # each node except root (consider cut between u and its parent)
    diff = abs(total - 2 * subtree[u])
    if diff < ans:
        ans = diff
return ans

if name == 'main': fptr = open(os.environ['OUTPUT_PATH'], 'w')

n = int(input().strip())

data = list(map(int, input().rstrip().split()))

edges = []

for _ in range(n - 1):
    edges.append(list(map(int, input().rstrip().split())))

result = cutTheTree(data, edges)

fptr.write(str(result) + '\n')

fptr.close()

3 months ago+ 0 comments

import java.io.*;
import java.util.*;

public class Solution{
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        
        //Get vertex values and tree sum
        Vertex[] verts = new Vertex[N];
        N = 0;
        int sum = 0;
        for(String s : br.readLine().split(" ")){
            short v = Short.parseShort(s);
            sum += v;
            verts[N++] = new Vertex(v);
        }
        
        //Get edges
        while (--N > 0){
            String[] temp = br.readLine().split(" ");
            int i1 = Integer.parseInt(temp[0]) - 1;
            int i2 = Integer.parseInt(temp[1]) - 1;
            verts[i1].addEdge(verts[i2], sum);
            verts[i2].addEdge(verts[i1], sum);
        }
        
        //Initialize
        Vertex.init(verts[0]);
        
        //Find smallest diff
        int min = Integer.MAX_VALUE;
        for(Vertex vertex : verts){
            int curMin = vertex.minDiff(sum);
            //Update min
            min = (curMin < min) ? curMin : min;
        }
        
        //Output
        System.out.print(min);
    }
    
    private static class Vertex{
        private int minDiff;
        private short value;
        private boolean isInit;
        private List<Edge> edges;
        public Vertex(short value){
            this.value = value;
            this.isInit = false;
            this.edges = new ArrayList<Edge>();
        }
        
        public void addEdge(Vertex vertex, int value){
            edges.add(new Edge(vertex, value));
        }
        
        public int minDiff(int sum){
            int min = sum;
            for(Edge edge : edges){
                //Get difference of both possible trees
                int curMin = sum - 2*edge.value;
                //Make absolute value
                curMin = (curMin < 0) ? -curMin : curMin;
                //Update min
                min = (curMin < min) ? curMin : min;
            }
            return min;
        }
        
        public static void init(Vertex v){
            if (!v.isInit){
                v.init();
            }
        }
        
        private int init(){
            this.isInit = true;
            Edge caller = null;
            int sum = this.value;
            //For each edge
            for(Edge edge : edges){
                //If it's the caller, save for later
                if (edge.vertex.isInit){
                    caller = edge;
                //Otherwise, get the sum of
                //all vertices for that edge
                } else {
                    sum += edge.value = edge.vertex.init();
                }
            }
            //If it's the caller
            //subtract this vertex's
            //sum from the tree's sum
            if (caller != null){
                caller.value -= sum;
            }
            return sum;
        }
        
        private class Edge{
            public int value;
            public Vertex vertex;
            public Edge(Vertex vertex, int value){
                this.value = value;
                this.vertex = vertex;
            }
        }
    }
}

3 months ago+ 0 comments

#!/bin/python3

import math
import os
import random
import re
import sys

#
# Complete the 'cutTheTree' function below.
#
# The function is expected to return an INTEGER.
# The function accepts following parameters:
#  1. INTEGER_ARRAY data
#  2. 2D_INTEGER_ARRAY edges
#
sys.setrecursionlimit(10**7)

class Vertex:
    def __init__(self, value):
        self.value = value
        self.edges = []
        self.is_init = False
    
    def add_edge(self, vertex):
        self.edges.append(vertex)
        
def init(vertex, parent, sum_cache):
    vertex.is_init = True
    subtotal = vertex.value
    for adj in vertex.edges:
        if adj is not parent:
            subtree_sum = init(adj, vertex, sum_cache)
            sum_cache[(vertex, adj)] = subtree_sum
            sum_cache[(adj, vertex)] = sum_cache_total - subtree_sum
            subtotal += subtree_sum
    return subtotal

def min_diff(vertices, sum_cache, total_sum):
    min_diff_value = total_sum
    for v in vertices:
        for adj in v.edges:
            diff = abs(total_sum - 2 * sum_cache[(v, adj)])
            if diff < min_diff_value:
                min_diff_value = diff
    return min_diff_value

N = int(sys.stdin.readline())
values = list(map(int, sys.stdin.readline().split()))
vertices = [Vertex(val) for val in values]
for _ in range(N - 1):
    a, b = map(int, sys.stdin.readline().split())
    vertices[a - 1].add_edge(vertices[b - 1])
    vertices[b - 1].add_edge(vertices[a - 1])

sum_cache = {}
sum_cache_total = sum(values)
init(vertices[0], None, sum_cache)
result = min_diff(vertices, sum_cache, sum_cache_total)
print(result)

6 months ago+ 0 comments

#include<iostream>
#include<vector>
#include<climits>
using namespace std;

int value[100001], n, tot, best;
vector<vector<int> > v;
bool visited[100001];
int sum[100001];

int dfs(int node)
{
    int ret = 0;
    visited[node] = true;
    int sz = (int)v[node].size();
    for (int i = 0; i < sz; i++)
    {
        int next = v[node][i];
        if (!visited[next])
            ret += dfs(next);
    }
    return sum[node] = value[node] + ret;
}

int main()
{
    best = INT_MAX;
    tot = 0;
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> value[i];
        tot += value[i];
    }
    v.resize(n + 1);
    for (int i = 0; i < n - 1; i++)
    {
        int a, b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    dfs(1);
    for (int i = 1; i <= n; i++)
        if (abs(tot - sum[i] - sum[i]) < best)
            best = abs(tot - sum[i] - sum[i]);
    cout << best << endl;
    return 0;
}

Sort by

|

168 Discussions

|

!/bin/python3

Cookie support is required to access HackerRank