Table of Contents
Alex vs Fedor – 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++ Alex vs Fedor HackerRank Solution
/**
* BE CAREFUL!! I have define int li
*/
//#define _GLIBCXX_DEBUG
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <cmath>
#include <ctime>
#include <stack>
#include <set>
#include <bitset>
#include <map>
#include <cassert>
#include <memory.h>
#include <limits>
#include <numeric>
using namespace std;
int timer;
#define mp make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
typedef long long li;
typedef long double ld;
typedef vector<int> vi;
typedef pair <int, int> pi;
void solve();
void prec();
vector<vector<long long int>> removed(vector<vector<li>> vector);
li det(vector<vector<long long int>> vector);
#define FILENAME "souvenir"
int main(){
string s = FILENAME;
#ifdef DEBUG
freopen("/Users/RiaD/Contests/Contests/input", "r", stdin);
//freopen("/Users/RiaD/Contests/Contests/output", "w", stdout);
//cout<<FILENAME<<endl;
//assert (s != "change me please");
clock_t start = clock();
#else
//freopen(FILENAME ".in", "r", stdin);
//freopen(FILENAME ".out", "w", stdout);
#endif
cout.sync_with_stdio(0);
cout.precision(20);
cout << fixed;
//rprec();
int t = 1;
//cin >> t;
while (t--) {
++timer;
solve();
}
#ifdef DEBUG
//cerr<<"\n\n"<<(clock() - start) / 1.0 / CLOCKS_PER_SEC<<"\n\n\n";
#endif
return 0;
}
typedef vector<li> vli;
vector<vector<long long int>> removed(vector<vli> v) {
v.pop_back();
for(int i = 0; i < v.size(); ++i) {
v[i].pop_back();
}
return v;
}
int dsu[110];
int get(int v) {
if(v == dsu[v])
return v;
return dsu[v] = get(dsu[v]);
}
void unite(int a, int b) {
a = get(a);
b = get(b);
dsu[a] = b;
}
void solve() {
int n, m;
cin >> n >> m;
for(int i = 0; i < n; ++i) {
dsu[i] = i;
}
vector<vector<li>> mat(n, vector<li>(n, 0));
vector<pair<li, pi>> v;
for(int i = 0; i < m; ++i) {
li a, b, w;
cin >> a >> b >> w;
--a, --b;
--mat[a][b];
--mat[b][a];
++mat[a][a];
++mat[b][b];
v.push_back(mp(w, mp(a,b)));
}
li all = det(removed(mat));
sort(v.begin(), v.end());
li msts = 1;
for(int i = 0; i < m;) {
//cout << "edges with w=" << v[i].first << "\n";
int j;
vector<pi> edges;
for(j = i; v[i].first == v[j].first; ++j) {
//cout << get(v[j].second.first) << " " << get(v[j].second.second) << "\n";
edges.push_back(mp(get(v[j].second.first), get(v[j].second.second)));
}
for(j = i; v[i].first == v[j].first; ++j) {
unite(v[j].second.first, get(v[j].second.second));
}
map<int, vector<pi>> ng2edgesInIt;
for(pi& x: edges) {
ng2edgesInIt[get(x.first)].push_back(x);
}
for(auto& x: ng2edgesInIt) {
map<int, int> toIds;
for(auto& y: x.second) {
if(!toIds.count(y.first)) {
int cnt = toIds.size();
toIds[y.first] = cnt;
}
if(!toIds.count(y.second)) {
int cnt = toIds.size();
toIds[y.second] = cnt;
}
}
vector<vli> matr (toIds.size(), vli(toIds.size()));
for(auto y: x.second) {
y.first = toIds[y.first];
y.second = toIds[y.second];
matr[y.first][y.second]--;
matr[y.second][y.first]--;
matr[y.first][y.first]++;
matr[y.second][y.second]++;
}
msts *= det(removed(matr));
}
i = j;
}
li g = __gcd(msts, all);
cout << (msts/g) << "/" << (all/g);
}
li det(vector<vli> mat) {
int n = mat.size();
if(n == 0)
return 1;
for(int col = 0; col < n; ++col) {
bool found = false;
for(int row = col; row < n; ++row) {
if(mat[row][col]) {
mat[row].swap(mat[col]);
found = true;
break;
}
}
if(!found) {
return 0;
}
for(int row = col + 1; row < n; ++row) {
while(true) {
li del = mat[row][col] / mat[col][col];
for (int j = col; j < n; ++j) {
mat[row][j] -= del * mat[col][j];
}
if (mat[row][col] == 0)
break;
else
mat[row].swap(mat[col]);
}
}
}
li res = 1;
for(int i = 0; i < n; ++i) {
res *= mat[i][i];
}
return abs(res);
}
Java Alex vs Fedor HackerRank Solution
import java.io.*;
import java.math.BigDecimal;
import java.math.MathContext;
import java.util.*;
public class Solution {
public static void main(String[] args) throws NumberFormatException, IOException {
// long start = System.currentTimeMillis();
// System.out.println(getSpanningTreeCount(makeKn(14)) + " (" + (System.currentTimeMillis() - start) + " ms)");
// if (true) {
// return;
// }
// List<Node> nodes = makeCn(100);
// List<Node> nodes = makeKn(10);
//
// Edge nedge = new Edge(nodes, 0,1,99);
// nodes.get(0).edges.add(nedge);
// nodes.get(1).edges.add(nedge);
// System.out.println(nodes.get(0).edges);
List<Node> nodes = null;
if (nodes == null) {
Scanner scanner = new Scanner(System.in);
int n = scanner.nextInt();
int m = scanner.nextInt();
if (n > m) { // Not connected or exacly one spanning tree
System.out.println("1/1");
return;
}
nodes = new ArrayList<Node>(n);
for (int i = 0; i < n; i++) {
nodes.add(new Node(i));
}
Set<Edge> edges = new HashSet<>(2*m);
int edgeCount[] = new int[n];
boolean sameWeight = true;
int commonWeight = 0;
for (int i = 0; i < m; i++) {
int node1 = scanner.nextInt()-1;
int node2 = scanner.nextInt()-1;
int weight = scanner.nextInt();
Edge edge = new Edge(nodes, node1, node2, weight);
edges.add(edge);
edgeCount[node1]++;
edgeCount[node2]++;
if (sameWeight) {
if (i == 1) {
commonWeight = weight;
} else if (weight != commonWeight) {
sameWeight = false;
}
}
}
if (sameWeight) { // All edges (and spanning trees) have the same weight
System.out.println("1/1");
return;
}
for (int i = 0; i < n; i++) {
nodes.get(i).edges = new ArrayList<>(edgeCount[i]);
}
for (Edge edge : edges) {
edge.node1.edges.add(edge);
edge.node2.edges.add(edge);
}
}
// Make nodes with few edges first (guess determinant calculation benefits from that)
Comparator<? super Node> edgeCountComp = (n1,n2) -> Integer.compare(n1.edges.size(), n2.edges.size());
Collections.sort(nodes, edgeCountComp.reversed());
if (nodes.get(nodes.size()-1).edges.size() == 1) {
// Remove nodes with single edge
// Performance does not matter here
do {
while (nodes.get(nodes.size()-1).edges.size() == 1) {
Node node = nodes.remove(nodes.size()-1);
Edge edge = node.edges.get(0);
edge.getOther(node).edges.remove(edge);
}
Collections.sort(nodes, edgeCountComp.reversed());
} while (nodes.get(nodes.size()-1).edges.size() == 1);
}
// Renumber nodes
for (int i = 0; i < nodes.size(); i++) {
nodes.get(i).node = i;
}
long total = getSpanningTreeCount(nodes);
if (total <= 1) {
System.out.println("1/1");
return;
}
long minCount = getMinSpanningTreeCount(nodes);
// Count minimal trees
// Beregn determinant af en matrice for at finde antal spanning trees
// Sorter kanter efter vægt
// Grupper knuder forbundet med lavest vægt. Beregn antal spanning trees pr gruppe. Kollaps gruppe.
if (total == minCount) {
System.out.println("1/1");
return;
}
if (total % minCount == 0) {
System.out.println("1/" + (total/minCount));
return;
}
System.err.println(total);
// Just measure performance of spanning tree count
int maxCommonDivider = (int) Math.sqrt(minCount);
int div = 2;
while (div <= maxCommonDivider) {
if (minCount % div == 0 && total % div == 0) {
minCount/= div;
total /= div;
} else {
div++;
}
maxCommonDivider = (int) Math.sqrt(minCount);
}
System.out.println(minCount + "/" + total);
}
private static long getMinSpanningTreeCount(List<Node> nodes) {
Map<Node,Node> oldToNewNode = new LinkedHashMap<>();
Queue<Node> nodesToSearch = new LinkedList<>();
List<Node> subGraphNodes = new ArrayList<>();
long minConnectedSpanningTreeCouint = 1;
while (nodes.size() > 1) {
int minWeight = Integer.MAX_VALUE;
Edge minEdge = null;
for (Node node : nodes) {
for (Edge edge : node.edges) {
if (minEdge == null || edge.weight < minWeight) {
minWeight = edge.weight;
minEdge = edge;
}
}
}
Node collapsedNode = new Node(nodes.size());
subGraphNodes.clear();
oldToNewNode.clear();
nodesToSearch.add(minEdge.node1);
oldToNewNode.put(minEdge.node1, new Node(0));
while (!nodesToSearch.isEmpty()) {
Node node = nodesToSearch.poll();
Node newNode = oldToNewNode.get(node);
subGraphNodes.add(newNode);
for (Edge edge : node.edges) {
if (edge.weight == minWeight) {
Node otherNode = edge.getOther(node);
if (!oldToNewNode.containsKey(otherNode)) {
oldToNewNode.put(otherNode, new Node(oldToNewNode.size()));
nodesToSearch.add(otherNode);
}
Node newOtherNode = oldToNewNode.get(otherNode);
if (node.node < otherNode.node) {
Edge newEdge = new Edge(newNode, newOtherNode, minWeight);
newNode.edges.add(newEdge);
newOtherNode.edges.add(newEdge);
}
}
}
}
if (subGraphNodes.size() != oldToNewNode.size() || subGraphNodes.size() <= 1) {
throw new IllegalStateException("Subgraph size: " + subGraphNodes.size());
}
minConnectedSpanningTreeCouint *= getSpanningTreeCount(subGraphNodes);
// Create a list of remaining nodes, and fix edges pointing at collapsed sugraph
List<Node> newNodes = new ArrayList<>();
for (Node node : nodes) {
if (!oldToNewNode.containsKey(node)) {
newNodes.add(node);
for (Edge edge : node.edges) {
if (oldToNewNode.containsKey(edge.getOther(node))) {
if (edge.node1 == node) {
edge.node2 = collapsedNode;
} else {
edge.node1 = collapsedNode;
}
collapsedNode.edges.add(edge);
}
}
}
}
newNodes.add(collapsedNode);
if (nodes.size() <= newNodes.size()) {
throw new IllegalStateException("Expected that there would be fewer nodes");
}
nodes = newNodes;
// Renumber nodes
for (int i = 0; i < nodes.size(); i++) {
nodes.get(i).node = i;
}
}
return minConnectedSpanningTreeCouint;
}
private static long getSpanningTreeCount(List<Node> nodes) {
int matrix[][] = new int[nodes.size()-1][nodes.size()-1];
// Skip last row and column
for (int i = 0; i < nodes.size()-1; i++) {
Node node = nodes.get(i);
matrix[i][i] = node.edges.size();
for (Edge edge : node.edges) {
int node2 = edge.getOther(node).node;
if (node2 < nodes.size()-1) {
matrix[i][node2]--;
}
}
}
long determinant = determinant(matrix);
return determinant;
}
private static long determinant(int[][] matrix) {
return determinantBigDecimal(matrix);
}
private static long determinantDouble(int[][] matrix) {
int n = matrix.length;
double newMatrix[][] = new double[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
newMatrix[i][j] = matrix[i][j];
}
}
double det = 1;
for (int diagonal = 0; diagonal < n; diagonal++) {
double diagonalVal = newMatrix[diagonal][diagonal];
if (isZero(diagonalVal)) {
// Swap two columns
det = -det;
for (int col = diagonal; col < n; col++) {
if (!isZero(newMatrix[col][diagonal])) {
double[] column = newMatrix[diagonal];
newMatrix[diagonal] = newMatrix[col];
newMatrix[col] = column;
break;
}
}
diagonalVal = newMatrix[diagonal][diagonal];
}
det *= diagonalVal;
System.out.println(diagonalVal);
for (int row2 = diagonal+1; row2 < n; row2++) {
if (!isZero(newMatrix[diagonal][row2])) {
double row2BelowDiagonalVal = newMatrix[diagonal][row2];
double mult = row2BelowDiagonalVal / diagonalVal;
newMatrix[diagonal][row2] = 0;
for (int col = diagonal+1; col < n; col++) {
newMatrix[col][row2] = newMatrix[col][row2] - mult * newMatrix[col][diagonal];
}
}
}
}
return Math.round(det);
}
private static long determinantBigDecimal(int[][] matrix) {
MathContext mathContext = new MathContext(40);
int n = matrix.length;
BigDecimal newMatrix[][] = new BigDecimal[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
newMatrix[i][j] = BigDecimal.valueOf(matrix[i][j]);
}
}
BigDecimal det = BigDecimal.ONE;
for (int diagonal = 0; diagonal < n; diagonal++) {
BigDecimal diagonalVal = newMatrix[diagonal][diagonal];
if (isZero(diagonalVal)) {
// Swap two columns
det = det.negate();
for (int col = diagonal; col < n; col++) {
if (!isZero(newMatrix[col][diagonal])) {
BigDecimal[] column = newMatrix[diagonal];
newMatrix[diagonal] = newMatrix[col];
newMatrix[col] = column;
break;
}
}
diagonalVal = newMatrix[diagonal][diagonal];
}
det = det.multiply(diagonalVal);
for (int row2 = diagonal+1; row2 < n; row2++) {
if (!isZero(newMatrix[diagonal][row2])) {
BigDecimal row2BelowDiagonalVal = newMatrix[diagonal][row2];
BigDecimal mult = row2BelowDiagonalVal.divide(diagonalVal, mathContext);
newMatrix[diagonal][row2] = BigDecimal.ZERO;
for (int col = diagonal+1; col < n; col++) {
newMatrix[col][row2] = newMatrix[col][row2].subtract(mult.multiply(newMatrix[col][diagonal], mathContext), mathContext);
}
}
}
}
return det.add(new BigDecimal("0.5")).longValue();
}
private static boolean isZero(double d) {
return -1e-10 < d && d < 1e-10;
}
private static boolean isZero(BigDecimal d) {
return BigDecimal.ZERO.equals(d);
}
private static long determinantSlow(int[][] matrix) {
int n = matrix.length;
if (n <= 2) {
if (matrix.length == 1) {
return matrix[0][0];
} else {
return matrix[0][0]*matrix[1][1]-matrix[0][1]*matrix[1][0];
}
}
int subMatrix[][] = new int[n-1][n];
for (int i = 1; i < n; i++) {
System.arraycopy(matrix[i], 1, subMatrix[i-1], 0, n-1);
}
long det = 0;
for (int i = 0; i < n; i++) {
if (matrix[i][0] != 0) {
long subDet = determinantSlow(subMatrix) * matrix[i][0];
if ((i&1) == 0) {
det += subDet;
} else {
det -= subDet;
}
}
if (i != n-1) {
// Consider Arrays.copyOf - which is fastest?
System.arraycopy(matrix[i], 1, subMatrix[i], 0, n-1);
}
}
return det;
}
private static List<Node> makeKn(int n) {
List<Node> nodes = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
Node node = new Node(i);
nodes.add(node);
node.edges = new ArrayList<>(n-1);
}
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
Edge edge = new Edge(nodes, i, j, 1);
nodes.get(i).edges.add(edge);
nodes.get(j).edges.add(edge);
}
}
return nodes;
}
private static List<Node> makeCn(int n) {
List<Node> nodes = new ArrayList<>(n);
for (int i = 0; i < n; i++) {
Node node = new Node(i);
nodes.add(node);
node.edges = new ArrayList<>(2);
}
for (int i = 0; i < n; i++) {
Edge edge = new Edge(nodes, i, (i+1)%n, (int) (Math.random()*100));
nodes.get(i).edges.add(edge);
nodes.get((i+1)%n).edges.add(edge);
}
return nodes;
}
public static class Node {
public int node;
public List<Edge> edges;
public Node(int node) {
this.node = node;
edges = new ArrayList<>(2);
}
@Override
public String toString() {
return "Node " + node;
}
}
public static class Edge {
public Node node1;
public Node node2;
public int weight;
public Edge(List<Node> nodes, int node1, int node2, int weight) {
this(nodes.get(node1), nodes.get(node2), weight);
}
public Edge(Node node1, Node node2, int weight) {
this.node1 = node1;
this.node2 = node2;
this.weight = weight;
}
public Node getOther(Node node) {
return node == node1 ? node2 : node1;
}
@Override
public String toString() {
return "Edge [node1=" + node1 + ", node2=" + node2 + ", weigth=" + weight + "]";
}
}
private static class Fraction {
public static Fraction ONE = new Fraction(1,1);
public static Fraction ZERO = new Fraction(0,1);
final long top;
final long bottom;
public Fraction(long top, long bottom) {
this.top = top;
this.bottom = bottom;
}
public static Fraction create(long top, long bottom) {
// TODO: If going to be used: Handle case where either top or bottom divedes the other
if (top == bottom) {
if (top == 0) {
return ZERO;
}
return ONE;
}
while ((top & 1) == 0 && (bottom & 1) == 0) {
top >>= 1;
bottom >>= 1;
}
if (top == 1 || bottom == 1) {
return new Fraction(top,bottom);
}
int max = (int) Math.sqrt(Math.min(top, bottom));
for (int div = 2; div <= max; div++) {
if (top % div == 0 && bottom % div == 0) {
do {
top /= div;
bottom /= div;
} while (top % div == 0 && bottom % div == 0);
max = (int) Math.sqrt(Math.min(top, bottom));
}
}
return new Fraction(top,bottom);
}
@Override
public String toString() {
return top + "/" + bottom;
}
}
}
C Alex vs Fedor HackerRank Solution
/**
* BE CAREFUL!! I have define int li
*/
//#define _GLIBCXX_DEBUG
#include <stdio.h>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <deque>
#include <cmath>
#include <ctime>
#include <stack>
#include <set>
#include <bitset>
#include <map>
#include <cassert>
#include <memory.h>
#include <limits>
#include <numeric>
using namespace std;
int timer;
#define mp make_pair
#define pb push_back
#define all(a) a.begin(), a.end()
typedef long long li;
typedef long double ld;
typedef vector<int> vi;
typedef pair <int, int> pi;
void solve();
void prec();
vector<vector<long long int>> removed(vector<vector<li>> vector);
li det(vector<vector<long long int>> vector);
#define FILENAME "souvenir"
int main(){
string s = FILENAME;
#ifdef DEBUG
freopen("/Users/RiaD/Contests/Contests/input", "r", stdin);
//freopen("/Users/RiaD/Contests/Contests/output", "w", stdout);
//cout<<FILENAME<<endl;
//assert (s != "change me please");
clock_t start = clock();
#else
//freopen(FILENAME ".in", "r", stdin);
//freopen(FILENAME ".out", "w", stdout);
#endif
cout.sync_with_stdio(0);
cout.precision(20);
cout << fixed;
//rprec();
int t = 1;
//cin >> t;
while (t--) {
++timer;
solve();
}
#ifdef DEBUG
//cerr<<"\n\n"<<(clock() - start) / 1.0 / CLOCKS_PER_SEC<<"\n\n\n";
#endif
return 0;
}
typedef vector<li> vli;
vector<vector<long long int>> removed(vector<vli> v) {
v.pop_back();
for(int i = 0; i < v.size(); ++i) {
v[i].pop_back();
}
return v;
}
int dsu[110];
int get(int v) {
if(v == dsu[v])
return v;
return dsu[v] = get(dsu[v]);
}
void unite(int a, int b) {
a = get(a);
b = get(b);
dsu[a] = b;
}
void solve() {
int n, m;
cin >> n >> m;
for(int i = 0; i < n; ++i) {
dsu[i] = i;
}
vector<vector<li>> mat(n, vector<li>(n, 0));
vector<pair<li, pi>> v;
for(int i = 0; i < m; ++i) {
li a, b, w;
cin >> a >> b >> w;
--a, --b;
--mat[a][b];
--mat[b][a];
++mat[a][a];
++mat[b][b];
v.push_back(mp(w, mp(a,b)));
}
li all = det(removed(mat));
sort(v.begin(), v.end());
li msts = 1;
for(int i = 0; i < m;) {
//cout << "edges with w=" << v[i].first << "\n";
int j;
vector<pi> edges;
for(j = i; v[i].first == v[j].first; ++j) {
//cout << get(v[j].second.first) << " " << get(v[j].second.second) << "\n";
edges.push_back(mp(get(v[j].second.first), get(v[j].second.second)));
}
for(j = i; v[i].first == v[j].first; ++j) {
unite(v[j].second.first, get(v[j].second.second));
}
map<int, vector<pi>> ng2edgesInIt;
for(pi& x: edges) {
ng2edgesInIt[get(x.first)].push_back(x);
}
for(auto& x: ng2edgesInIt) {
map<int, int> toIds;
for(auto& y: x.second) {
if(!toIds.count(y.first)) {
int cnt = toIds.size();
toIds[y.first] = cnt;
}
if(!toIds.count(y.second)) {
int cnt = toIds.size();
toIds[y.second] = cnt;
}
}
vector<vli> matr (toIds.size(), vli(toIds.size()));
for(auto y: x.second) {
y.first = toIds[y.first];
y.second = toIds[y.second];
matr[y.first][y.second]--;
matr[y.second][y.first]--;
matr[y.first][y.first]++;
matr[y.second][y.second]++;
}
msts *= det(removed(matr));
}
i = j;
}
li g = __gcd(msts, all);
cout << (msts/g) << "/" << (all/g);
}
li det(vector<vli> mat) {
int n = mat.size();
if(n == 0)
return 1;
for(int col = 0; col < n; ++col) {
bool found = false;
for(int row = col; row < n; ++row) {
if(mat[row][col]) {
mat[row].swap(mat[col]);
found = true;
break;
}
}
if(!found) {
return 0;
}
for(int row = col + 1; row < n; ++row) {
while(true) {
li del = mat[row][col] / mat[col][col];
for (int j = col; j < n; ++j) {
mat[row][j] -= del * mat[col][j];
}
if (mat[row][col] == 0)
break;
else
mat[row].swap(mat[col]);
}
}
}
li res = 1;
for(int i = 0; i < n; ++i) {
res *= mat[i][i];
}
return abs(res);
}
Leave a comment below
