Cerinta completa
You are given an array with -bit integers: .
BIT(x, i) = (x >> i) & 1, where is the lower bit of in binary form. If we regard every bit as a vertex of a graph G, there is an undirected edge between vertices and if there is a value such that BIT(d[k], i) == 1 && BIT(d[k], j) == 1.
For every subset of the input array, how many connected-components are there in that graph?
A connected component in a graph is a set of nodes which are accessible to each other via a path of edges. There may be multiple connected components in a graph.
Example
In the real challenge, there will be nodes associated with each integer in represented as a bit binary value. For clarity, only bits will be shown in the example but all will be considered in the calculations.
Decimal Binary Edges Node ends
d[0] = 1 0001 0
d[1] = 2 0010 0
d[2] = 3 0011 1 0 and 1
d[3] = 5 0101 1 0 and 2
Consider all subsets:
Edges
Subset Count Nodes Connected components
{1} 0 64
{2} 0 64
{3} 1 0-1 63
{5} 1 0-2 63
{1,2} 0 64
{1,3} 1 0-1 63
{1,5} 1 0-2 63
{2,3} 1 0-1 63
{2,5} 1 0-2 63
{3,5} 2 0-1-2 62
{1,2,3} 1 0-1 63
{1,2,5} 1 0-2 63
{1,3,5} 2 0-1-2 62
{2,3,5} 2 0-1-2 62
{1,2,3,5} 2 0-1-2 62
Sum 944
The values and have bits set, so they have edge each. If a subset contains only a or , there will be one connected component with nodes, and components with node for a total of .
If both and are in a subset, component with nodes and is formed since node is one end of each edge described. The other nodes are solitary, so there are connected components total.
All other values have only bit set, so they have no edges. They have components with node each.
Function Description
Complete the findConnectedComponents function in the editor below.
findConnectedComponents has the following parameters:
- int d[n]: an array of integers
Returns
- int: the sum of the number of connected components for all subsets of
Input Format
The first row contains the integer , the size of .
The next row has space-separated integers, .
Constraints
Limbajul de programare folosit: java8
Cod:
import java.io.*;
import java.util.*;
public class Solution {
static class DSURollback {
int[] parent = new int[64];
int[] size = new int[64];
int components = 64;
int[] stkA = new int[4096];
int[] stkB = new int[4096];
int top = 0;
DSURollback() {
for (int i = 0; i < 64; i++) {
parent[i] = i;
size[i] = 1;
}
}
int find(int x) {
while (parent[x] != x) x = parent[x];
return x;
}
void union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) {
stkA[top] = -1;
stkB[top] = -1;
top++;
return;
}
if (size[ra] < size[rb]) {
int t = ra; ra = rb; rb = t;
}
// attach rb to ra
stkA[top] = ra;
stkB[top] = rb;
top++;
parent[rb] = ra;
size[ra] += size[rb];
components--;
}
int snapshot() {
return top;
}
void rollback(int snap) {
while (top > snap) {
top--;
int ra = stkA[top];
int rb = stkB[top];
if (ra == -1) continue;
parent[rb] = rb;
size[ra] -= size[rb];
components++;
}
}
}
static int n;
static int[][] bits;
static DSURollback dsu;
static long answer;
static void dfs(int idx) {
if (idx == n) {
answer += dsu.components;
return;
}
// Exclude d[idx]
dfs(idx + 1);
// Include d[idx]
int snap = dsu.snapshot();
int[] arr = bits[idx];
if (arr.length >= 2) {
int base = arr[0];
for (int i = 1; i < arr.length; i++) {
dsu.union(base, arr[i]);
}
}
dfs(idx + 1);
dsu.rollback(snap);
}
private static class FastScanner {
private final InputStream in;
private final byte[] buffer = new byte[1 << 16];
private int ptr = 0, len = 0;
FastScanner(InputStream is) { this.in = is; }
private int read() throws IOException {
if (ptr >= len) {
len = in.read(buffer);
ptr = 0;
if (len <= 0) return -1;
}
return buffer[ptr++];
}
long nextLong() throws IOException {
int c;
do { c = read(); } while (c <= ' ' && c != -1);
int sign = 1;
if (c == '-') { sign = -1; c = read(); }
long val = 0;
while (c > ' ') {
val = val * 10 + (c - '0');
c = read();
}
return sign == 1 ? val : -val;
}
int nextInt() throws IOException { return (int) nextLong(); }
}
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
n = fs.nextInt();
bits = new int[n][];
for (int i = 0; i < n; i++) {
long x = fs.nextLong();
int[] tmp = new int[64];
int c = 0;
while (x != 0) {
int b = Long.numberOfTrailingZeros(x);
tmp[c++] = b;
x &= (x - 1);
}
bits[i] = Arrays.copyOf(tmp, c);
}
dsu = new DSURollback();
answer = 0;
dfs(0);
System.out.println(answer);
}
}
Scor obtinut: 1.0
Submission ID: 464619509
Link challenge: https://www.hackerrank.com/challenges/subset-component/problem