In this HackerRank ByteLandian Tours problem solution The country of Byteland contains N cities and N - 1 bidirectional road between them such that there is a path between any two cities. The cities are numbered (0,..., N - 1). The people were very unhappy about the time it took to commute, especially salesmen who had to go about every city selling goods. So it was decided that new roads would be built between any two "somewhat near" cities. Any two cities in Bytleland that can be reached by traveling on exactly two old roads are known as "somewhat near" each other.
Now a salesman situated in city 0, just like any other typical salesman, has to visit all cities exactly once and return back to city 0 in the end. In how many ways can he do this?
Problem solution in Python.
#!/bin/python3
import os
import sys
import math
#
# Complete the bytelandianTours function below.
#
def bytelandianTours(n, roads):
if n <= 2:
return 1
m = 1000000007
nbr = list()
for i in range(n):
nbr.append(list())
for a,b in roads:
nbr[a].append(b)
nbr[b].append(a)
city = 0
if len(nbr[0]) == 1:
city = nbr[0][0]
nbr[city].sort(key=lambda x: len(nbr[x]), reverse = True)
if len(nbr[nbr[city][0]]) == 1:
return math.factorial(len(nbr[city])) % m
if len(nbr[city]) > 2 and len(nbr[nbr[city][2]]) > 1:
return 0
if len(nbr[nbr[city][1]]) > 1:
next_route = nbr[city][1]
nbr[next_route].remove(city)
rslt = (2 * math.factorial(len(nbr[city]) - 2)) % m
else:
next_route = -1
rslt = (2 * math.factorial(len(nbr[city]) - 1)) % m
#print(city, nbr)
parent = city
city = nbr[city][0]
nbr[city].remove(parent)
while True:
nbr[city].sort(key=lambda x: len(nbr[x]), reverse = True)
#print(city, nbr)
if len(nbr[nbr[city][0]]) == 1:
rslt = (rslt * (math.factorial(len(nbr[city])) %m)) %m
if next_route != -1:
city = next_route
next_route = -1
continue
else:
break
if len(nbr[city]) > 1 and len(nbr[nbr[city][1]]) > 1:
return 0
rslt = (rslt * (math.factorial(len(nbr[city])-1) %m)) %m
parent = city
city = nbr[city][0]
nbr[city].remove(parent)
return rslt
if __name__ == '__main__':
fptr = open(os.environ['OUTPUT_PATH'], 'w')
t = int(input())
for t_itr in range(t):
n = int(input())
roads = []
for _ in range(n-1):
roads.append(list(map(int, input().rstrip().split())))
result = bytelandianTours(n, roads)
fptr.write(str(result) + '\n')
fptr.close()
Problem solution in Java.
import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;
public class Solution {
private static final int MODULUS = 1000000007;
private static class Node {
Set<Node> neighbors = new HashSet<>();
}
/*
* Complete the bytelandianTours function below.
*/
static int bytelandianTours(int n, int[][] roads) {
Node[] nodes = new Node[n];
for (int i = 0; i < n; i++) {
nodes[i] = new Node();
}
for (int[] road : roads) {
nodes[road[0]].neighbors.add(nodes[road[1]]);
nodes[road[1]].neighbors.add(nodes[road[0]]);
}
long result = 1;
int nonLeaves = 0;
for (Node node : nodes) {
if (node.neighbors.size() > 1) {
nonLeaves++;
int leaves = leafNeighbors(node);
if (leaves + 2 < node.neighbors.size()) {
return 0;
} else {
// System.out.println(String.format("Multiplying by %d!", node.neighbors.size() - 2));
for (int i = 2; i <= leaves; i++) {
result = (result*i) % MODULUS;
}
}
}
}
if (nonLeaves > 1) {
result = (result*2) % MODULUS;
}
return (int) result;
}
private static int leafNeighbors(Node n) {
int leaves = 0;
for (Node other : n.neighbors) {
if (other.neighbors.size() == 1) {
leaves++;
}
}
return leaves;
}
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 = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");
for (int tItr = 0; tItr < t; tItr++) {
int n = scanner.nextInt();
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");
int[][] roads = new int[n-1][2];
for (int roadsRowItr = 0; roadsRowItr < n-1; roadsRowItr++) {
String[] roadsRowItems = scanner.nextLine().split(" ");
scanner.skip("(\r\n|[\n\r\u2028\u2029\u0085])*");
for (int roadsColumnItr = 0; roadsColumnItr < 2; roadsColumnItr++) {
int roadsItem = Integer.parseInt(roadsRowItems[roadsColumnItr]);
roads[roadsRowItr][roadsColumnItr] = roadsItem;
}
}
int result = bytelandianTours(n, roads);
bufferedWriter.write(String.valueOf(result));
bufferedWriter.newLine();
}
bufferedWriter.close();
scanner.close();
}
}
Problem solution in C++.
#include<iostream>
#include<vector>
using namespace std ;
#define MOD 1000000007
#define MAXN 10002
vector<int> G[MAXN];
int n, fac[MAXN];
char isLeaf[MAXN];
int get_answer() {
int ret = 1,path = n;
for(int i = 0;i < n; i++)
path -= isLeaf[i] = G[i].size() == 1;
for(int i = 0;i < n; i++)
if(!isLeaf[i]) {
int ct = 0, ct2 = 0 ;
for(int j = 0;j < G[i].size();j++)
if(!isLeaf[G[i][j]]) ct++;
else ct2++;
if(ct > 2) return 0 ;
ret = 1LL * ret * fac[ct2] % MOD;
}
return path == 1 ? ret : 2 * ret % MOD;
}
int main() {
fac[0] = 1 ;
for(int i = 1; i < MAXN; i++)
fac[i] = 1LL * i * fac[i - 1] % MOD;
int runs ;
cin >> runs;
while(runs--) {
cin >> n;
for(int i = 0; i < MAXN; i++)
G[i].clear();
for(int i = 1; i < n; i++) {
int a, b;
cin >> a >> b;
G[a].push_back(b);
G[b].push_back(a);
}
cout << get_answer() << endl;
}
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>
#define MOD 1000000007
char* readline();
char** split_string(char*);
/*
* Complete the bytelandianTours function below.
*/
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, int* numdesc*/){
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;
numdesc[i] = 1;
}
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++;
}
for(int i = n - 1; i >= 0; i--){
int currnode = parentqueue[i];
for(int j = 0; j < numchildren[currnode]; j++){
int childnode = childrenlist[currnode][j];
numdesc[currnode] += numdesc[childnode];
}
}*/
}
int bytelandianTours(int n, int** roads) {
struct edge sortedge[2*(n - 1)];
int edgebds[n + 1], parentlist[n], *childrenlist[n], numchildren[n], parentqueue[n], numdesc[n];
setuptree(n, roads, sortedge, edgebds/*, parentlist, childrenlist, numchildren, parentqueue, numdesc*/);
bool isbig[n];
int numbig = 0;
for(int i = 0; i < n; i++){
isbig[i] = (edgebds[i + 1] - edgebds[i] > 1);
numbig += isbig[i];
}
int numbigneigh[n];
long toreturn = (numbig < 2? 1 : 2);
for(int i = 0; i < n; i++){
int numleaf = 0;
numbigneigh[i] = 0;
for(int j = edgebds[i]; j < edgebds[i + 1]; j++){
if(isbig[sortedge[j].to]){
numbigneigh[i]++;
}
else{
numleaf++;
toreturn = (toreturn*numleaf)%MOD;
}
}
if(numbigneigh[i] > 2){
return 0;
}
}
return toreturn;
}
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 = bytelandianTours(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