In this HackerRank Repair Roads problem solution Two roads are adjacent if they have the same city at one of their endpoints. For the process to be efficient, no two robots will ever repair the same road, and no road can be visited twice. What is the minimum number of robots needed to accomplish the task?
Problem solution in Python.
#!/bin/python3
import os
import sys
#
# Complete the repairRoads function below.
#
import collections
import queue
def solve():
n = int(input().strip())
# read graph
graph = dict((i, []) for i in range(0, n))
for j in range(n - 1):
x, y = [int(p) for p in input().strip().split()]
graph[x].append(y)
graph[y].append(x)
# transform graph into tree
level = 1
root = 0
q = queue.Queue()
q.put((root, level, None))
seen = set([])
levels = collections.defaultdict(set)
tree = {}
while not q.empty():
item, level, parent = q.get()
levels[level].add(item)
seen.add(item)
tree[item] = dict(id=item, parent=parent, level=level, children=set([]),
leaf=None)
for child in graph[item]:
if child not in seen:
q.put((child, level + 1, item))
seen.add(child)
tree[item]['children'].add(child)
# print('Levels: %s' % levels)
# print('Tree: %s' % tree)
# count clusters
clusters = 1
has_items_in_cluster = False
for level in sorted(levels.keys(), reverse=True):
for item in levels[level]:
tree_item = tree[item]
if not tree_item['children']: # leaf
tree_item['leaf'] = True
else:
has_items_in_cluster = True
branches = 0
for child in tree_item['children']:
if not tree[child]['leaf']:
branches += 1
# branches == 0 -> visit point and go up
# branches == 1 -> visit downstream, point and go up
# branches % 2 == 0 -> have (branches // 2) clusters
# branches % 2 == 1 -> have (branches // 2) clusters and go up
if branches >= 2:
new_clusters = branches // 2
clusters += new_clusters
# print('New clusters: %d' % new_clusters)
if branches % 2 == 0:
has_items_in_cluster = False
# cluster will also include road up
parent = tree_item['parent']
if parent is not None:
# print('Cut %s and %s' % (item, parent))
tree[parent]['children'].remove(item)
# print(tree[item])
# print('Tree: %s' % tree)
if not has_items_in_cluster:
clusters -= 1 # last cluster was created but has no items
print(clusters)
t = int(input().strip())
for tt in range(t):
solve()
Problem solution in Java.
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;
public class Solution {
private Map<Integer, List<Integer>> roads = new HashMap<>();
/*
* Complete the repairRoads function below.
*/
static int repairRoads(int n, int[][] roads) {
/*
* Write your code here.
*/
Solution solution = new Solution();
for(int i=0;i<n-1;i++)
{
System.out.println(roads[i][0] + "-" + roads[i][1]);
solution.addRoad(roads[i][0],roads[i][1]);
}
return solution.solve();
}
private static final Scanner scanner = new Scanner(System.in);
public static void main(String[] args) throws IOException {
BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
int t = Integer.parseInt(scanner.nextLine().trim());
for (int tItr = 0; tItr < t; tItr++) {
int n = Integer.parseInt(scanner.nextLine().trim());
int[][] roads = new int[n-1][2];
for (int roadsRowItr = 0; roadsRowItr < n-1; roadsRowItr++) {
String[] roadsRowItems = scanner.nextLine().split(" ");
for (int roadsColumnItr = 0; roadsColumnItr < 2; roadsColumnItr++) {
int roadsItem = Integer.parseInt(roadsRowItems[roadsColumnItr].trim());
roads[roadsRowItr][roadsColumnItr] = roadsItem;
}
}
int result = repairRoads(n, roads);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
}
bufferedWriter.close();
}
private void addToTree(RoadTree roadTree, int level, Integer city, Integer parent) {
List<Integer> roadsFromCity = roads.get(city);
if (parent != null) {
roadsFromCity.remove(parent);
}
roadTree.add(city, roadsFromCity, level + 1);
for (Integer c : roadsFromCity) {
addToTree(roadTree, level + 1, c, city);
}
}
public int solve() {
int result = 0;
int level = 0;
RoadTree roadTree = new RoadTree(roads.size());
Integer root = roads.keySet().iterator().next();
addToTree(roadTree, level, root, null);
for (int i = roadTree.levels.lastKey() - 1; i > 0; i--) {
List<Integer> cities = roadTree.levels.get(i);
for (Integer city : cities) {
List<Integer> leaves = roadTree.roads.get(city);
if (leaves != null && leaves.isEmpty() == false) {
for (Integer integer : leaves) {
roadTree.points[city] += roadTree.points[integer];
}
if (roadTree.points[city] == 0) {
roadTree.points[city]++;
} else if (roadTree.points[city] % 2 == 0) {
result += roadTree.points[city] / 2;
roadTree.points[city] = 0;
}
for (Integer integer : leaves) {
roadTree.roads.remove(integer);
}
if (roadTree.points[city] == 0) {
roadTree.remove(city);
}
}
}
}
return result + (roadTree.points[root] + 1) / 2;
}
public static class RoadTree {
private int[] parents;
private Map<Integer, List<Integer>> roads = new HashMap<>();
private TreeMap<Integer, List<Integer>> levels = new TreeMap<>();
private int[] points;
public RoadTree(int numberOfCities) {
points = new int[numberOfCities];
parents = new int[numberOfCities];
}
public void add(Integer city, List<Integer> roads, Integer level) {
if (levels.containsKey(level) == false) {
levels.put(level, new ArrayList<Integer>());
}
this.roads.put(city, roads);
levels.get(level).add(city);
for (Integer integer : roads) {
parents[integer] = city;
}
}
public void remove(Integer city) {
roads.get(parents[city]).remove(city);
roads.remove(city);
}
}
public void addRoad(int city1, int city2) {
addConnection(city1, city2);
addConnection(city2, city1);
}
private void addConnection(int city1, int city2) {
if (roads.containsKey(city1)) {
roads.get(city1).add(city2);
} else {
List<Integer> cities = new ArrayList<>();
cities.add(city2);
roads.put(city1, cities);
}
}
}
Problem solution in C++.
#include<iostream>
#include<vector>
#include<stdio.h>
#include<set>
#include<string.h>
#include<stdlib.h>
using namespace std ;
#define INF (int)1e9
#define MAXN 10002
vector<int> G[MAXN] ;
int n ;
int parent[MAXN] ;
void dfs(int k,int p)
{
parent[k] = p ;
for(int i = 0;i < G[k].size();i++)
if(G[k][i] != p)
dfs(G[k][i],k) ;
}
int u[MAXN],v[MAXN],f[MAXN],nleaf[MAXN] ;
int solve()
{
memset(u,0,sizeof u) ;
memset(v,0,sizeof v) ;
memset(nleaf,0,sizeof nleaf) ;
memset(parent,255,sizeof parent) ;
dfs(0,-1) ;
for(int i = 1;i < n;i++) nleaf[parent[i]]++ ;
int nodes = n,ret = 0 ;
for(int i = 1;i < n;i++) if(nleaf[i] == 0 && u[i] == 0)
{
nleaf[parent[i]]-- ;
u[parent[i]] = 1 ;
parent[i] = -1 ;
nodes-- ;
}
if(nodes == 1) return 1 ;
while(nodes > 1)
{
ret++ ;
memset(f,255,sizeof f) ;
char mark[MAXN] = {} ;
for(int i = 1;i < n;i++) if(parent[i] != -1)
if(nleaf[i] > 1)
mark[i] = 1 ;
int a = -1,b = -1,c = -1 ;
for(int i = 1;i < n;i++) if(parent[i] != -1) if(nleaf[i] == 0)
{
int j = i ;
while(j > 0 && !mark[j]) j = parent[j] ;
if(f[j] == -1) f[j] = i ;
else
{
a = f[j] ;
b = i ;
c = j ;
break ;
}
}
if(a == -1 || b == -1) break ;
while(a != c) { int t = parent[a] ; parent[a] = -1 ; nleaf[t]-- ; nodes-- ; a = t ; }
while(b != c) { int t = parent[b] ; parent[b] = -1 ; nleaf[t]-- ; nodes-- ; b = t ; }
u[c] = 0 ;
for(int i = 1;i < n;i++) if(parent[i] == c) v[i] = 1 ;
v[c] = 1 ;
if(nodes == 1) break ;
if(c > 0 && nleaf[c] == 0) { int t = parent[c] ; parent[c] = -1 ; nleaf[t]-- ; nodes-- ; c = t ; }
while(c > 0 && nleaf[c] == 0 && !u[c])
{
if(v[c]) { int t = parent[c] ; parent[c] = -1 ; nleaf[t]-- ; nodes-- ; c = t ; }
else { int t = parent[c] ; parent[c] = -1 ; u[t] = 1 ; nleaf[t]-- ; nodes-- ; c = t ; }
}
if(nodes == 1 && c == 0 && u[c]) ret++ ;
}
return ret ;
}
int main()
{
int runs ;
scanf("%d",&runs) ;
while(runs--)
{
scanf("%d",&n) ;
for(int i = 0;i < MAXN;i++) G[i].clear() ;
for(int i = 1;i < n;i++)
{
int a,b ;
scanf("%d%d",&a,&b) ;
G[a].push_back(b) ;
G[b].push_back(a) ;
}
int ret = solve() ;
printf("%d\n",ret) ;
}
return 0 ;
}
Problem solution in C.
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char* readline();
char** split_string(char*);
struct edge{
int from;
int to;
};
bool precedge(struct edge e1, struct edge e2){
return e1.from < e2.from || (e1.from == e2.from && e1.to < e2.to);
}
void setuptree(int n, int** edges, struct edge *sortedge, int* edgebds, int* parentlist, int** childrenlist, int* numchildren, int* parentqueue){
for(int i = 0; i < n - 1; i++){
sortedge[2*i].from = edges[i][0];
sortedge[2*i].to = edges[i][1];
sortedge[2*i + 1].from = edges[i][1];
sortedge[2*i + 1].to = edges[i][0];
}
for(int i = 0; i < 2*(n - 1); i++){
int curr = i;
while(curr > 0){
int next = (curr - 1)/2;
if(precedge(sortedge[next], sortedge[curr])){
struct edge temp = sortedge[curr];
sortedge[curr] = sortedge[next];
sortedge[next] = temp;
curr = next;
}
else{
break;
}
}
}
for(int i = 2*n - 3; i >= 0; i--){
struct edge temp = sortedge[0];
sortedge[0] = sortedge[i];
sortedge[i] = temp;
int curr = 0;
while(true){
int next = curr;
if(2*curr + 1 < i && precedge(sortedge[next], sortedge[2*curr + 1])){
next = 2*curr + 1;
}
if(2*curr + 2 < i && precedge(sortedge[next], sortedge[2*curr + 2])){
next = 2*curr + 2;
}
if(next != curr){
struct edge temp = sortedge[curr];
sortedge[curr] = sortedge[next];
sortedge[next] = temp;
curr = next;
}
else{
break;
}
}
}
edgebds[0] = 0;
for(int i = 0; i < n; i++){
int index = edgebds[i];
while(index < 2*(n - 1) && sortedge[index].from == i){
index++;
}
edgebds[i + 1] = index;
}
for(int i = 0; i < n; i++){
parentlist[i] = -2;
childrenlist[i] = NULL;
numchildren[i] = 0;
}
int queuesize = 1;
parentqueue[0] = 0;
int queuedone = 0;
parentlist[0] = -1;
while(queuedone < queuesize){
int currnode = parentqueue[queuedone];
for(int i = edgebds[currnode]; i < edgebds[currnode + 1]; i++){
int nextnode = sortedge[i].to;
if(parentlist[nextnode] == -2){
parentlist[nextnode] = currnode;
queuesize++;
parentqueue[queuesize - 1] = nextnode;
numchildren[currnode]++;
childrenlist[currnode] = realloc(childrenlist[currnode], numchildren[currnode]*sizeof(int));
childrenlist[currnode][numchildren[currnode] - 1] = nextnode;
}
}
queuedone++;
}
}
int repairRoads(int n, int** roads) {
struct edge sortedge[2*(n - 1)];
int edgebds[n + 1], parentlist[n], *childrenlist[n], numchildren[n], parentqueue[n];
setuptree(n, roads, sortedge, edgebds, parentlist, childrenlist, numchildren, parentqueue);
int introb[n];//Number of robots to cover all roads below i
int extrob[n];//Number of robots to cover all roads below i plus ith parent road
int freerob[n];//Number of robots to cover all roads below i with one free to go to parent
int bypass[n];//Number of robots to cover all roads below i and not connected
for(int i = n - 1; i >= 0; i--){
int currnode = parentqueue[i];
introb[currnode] = 0;
extrob[currnode] = 1;
freerob[currnode] = 1;
bypass[currnode] = 0;
for(int j = 0; j < numchildren[currnode]; j++){
int childnode = childrenlist[currnode][j];
int oldint = introb[currnode];
int oldext = extrob[currnode];
int oldfree = freerob[currnode];
int oldby = bypass[currnode];
int check1, check2, check3;
check1 = oldint + extrob[childnode];
check2 = oldext + introb[childnode];
check3 = oldfree + freerob[childnode] - 1;
introb[currnode] = (check1 < check2? (check1 < check3? check1 : check3) : (check2 < check3? check2 : check3));
check1 = oldint + freerob[childnode];
check2 = oldext + introb[childnode];
check3 = oldfree + freerob[childnode] - 1;
extrob[currnode] = (check1 < check2? (check1 < check3? check1 : check3) : (check2 < check3? check2 : check3));
check1 = oldby + freerob[childnode];
check2 = oldfree + introb[childnode];
freerob[currnode] = (check1 < check2? check1 : check2);
check1 = oldby + introb[childnode];
check2 = oldfree + freerob[childnode] - 1;
bypass[currnode] = (check1 < check2? check1 : check2);
}
}
for(int i = 0; i < n; i++){
printf("%d: %d %d %d %d\n", i, introb[i], extrob[i], freerob[i], bypass[i]);
}
printf("\n");
return introb[0];
}
int main()
{
FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");
char* t_endptr;
char* t_str = readline();
int t = strtol(t_str, &t_endptr, 10);
if (t_endptr == t_str || *t_endptr != '\0') { exit(EXIT_FAILURE); }
for (int t_itr = 0; t_itr < t; t_itr++) {
char* n_endptr;
char* n_str = readline();
int n = strtol(n_str, &n_endptr, 10);
if (n_endptr == n_str || *n_endptr != '\0') { exit(EXIT_FAILURE); }
int** roads = malloc((n-1) * sizeof(int*));
for (int roads_row_itr = 0; roads_row_itr < n-1; roads_row_itr++) {
roads[roads_row_itr] = malloc(2 * (sizeof(int)));
char** roads_item_temp = split_string(readline());
for (int roads_column_itr = 0; roads_column_itr < 2; roads_column_itr++) {
char* roads_item_endptr;
char* roads_item_str = roads_item_temp[roads_column_itr];
int roads_item = strtol(roads_item_str, &roads_item_endptr, 10);
if (roads_item_endptr == roads_item_str || *roads_item_endptr != '\0') { exit(EXIT_FAILURE); }
roads[roads_row_itr][roads_column_itr] = roads_item;
}
}
int result = repairRoads(n, roads);
fprintf(fptr, "%d\n", result);
}
fclose(fptr);
return 0;
}
char* readline() {
size_t alloc_length = 1024;
size_t data_length = 0;
char* data = malloc(alloc_length);
while (true) {
char* cursor = data + data_length;
char* line = fgets(cursor, alloc_length - data_length, stdin);
if (!line) { break; }
data_length += strlen(cursor);
if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; }
size_t new_length = alloc_length << 1;
data = realloc(data, new_length);
if (!data) { break; }
alloc_length = new_length;
}
if (data[data_length - 1] == '\n') {
data[data_length - 1] = '\0';
}
data = realloc(data, data_length);
return data;
}
char** split_string(char* str) {
char** splits = NULL;
char* token = strtok(str, " ");
int spaces = 0;
while (token) {
splits = realloc(splits, sizeof(char*) * ++spaces);
if (!splits) {
return splits;
}
splits[spaces - 1] = token;
token = strtok(NULL, " ");
}
return splits;
}
0 Comments