Created
June 19, 2017 19:47
-
-
Save jianminchen/a17106b9da5ce5f68e384791acd955af to your computer and use it in GitHub Desktop.
Path matching - score 100 - study code written in Java by Slamur - https://www.hackerrank.com/Slamur?hr_r=1
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.awt.*; | |
import java.io.*; | |
import java.math.BigDecimal; | |
import java.math.BigInteger; | |
import java.util.*; | |
import java.util.List; | |
import static java.lang.Math.max; | |
import static java.lang.Math.min; | |
public class F implements Runnable{ | |
// SOLUTION!!! | |
// HACK ME PLEASE IF YOU CAN!!! | |
// PLEASE!!! | |
// PLEASE!!! | |
// PLEASE!!! | |
private final static Random rnd = new Random(); | |
private final static String fileName = ""; | |
int[] codes; | |
int[] pattern; | |
int[][] graph; | |
ParentInfo parentInfo; | |
static class Query { | |
int from, to; | |
int index; | |
int lca; | |
int result; | |
Query(int from, int to, int index) { | |
this.from = from; | |
this.to = to; | |
this.index = index; | |
this.lca = -1; | |
this.result = 0; | |
} | |
} | |
QueryOnRootPath queryOnRootPath; | |
private void solve() { | |
int n = readInt(); | |
int queriesCount = readInt(); | |
char[] letters = readCharArray(); | |
this.codes = new int[n]; | |
for (int i = 0; i < n; ++i) { | |
codes[i] = letters[i] - 'a'; | |
} | |
char[] patternString = readCharArray(); | |
this.pattern = new int[patternString.length]; | |
for (int i = 0; i < pattern.length; ++i) { | |
pattern[i] = patternString[i] - 'a'; | |
} | |
GraphBuilder graphBuilder = GraphBuilder.createInstance(n); | |
for (int i = 0; i < n - 1; ++i) { | |
int from = readInt() - 1; | |
int to = readInt() - 1; | |
graphBuilder.addEdge(from, to); | |
} | |
this.graph = graphBuilder.build(); | |
this.parentInfo = new ParentInfo(graph).setRoot(0, n - 1); | |
Query[] queries = new Query[queriesCount]; | |
for (int index = 0; index < queriesCount; ++index) { | |
int from = readInt() - 1; | |
int to = readInt() - 1; | |
Query query = new Query(from, to, index); | |
queries[index] = query; | |
} | |
List<Query>[] queriesFrom = new List[n]; | |
List<Query>[] queriesTo = new List[n]; | |
for (int v = 0; v < n; ++v) { | |
queriesFrom[v] = new ArrayList<>(); | |
queriesTo[v] = new ArrayList<>(); | |
} | |
for (Query query : queries) { | |
query.lca = parentInfo.lca(query.from, query.to); | |
queriesFrom[query.from].add(query); | |
queriesTo[query.to].add(query); | |
} | |
this.queryOnRootPath = new QueryOnRootPath(reverse(pattern), n, queriesFrom, queriesCount); | |
dfsQuery(0); | |
int[] fromLimits = queryOnRootPath.limits; | |
this.queryOnRootPath = new QueryOnRootPath(pattern, n, queriesTo, queriesCount); | |
dfsQuery(0); | |
int[] toLimits = queryOnRootPath.limits; | |
for (Query query : queries) { | |
int from = query.from; | |
int to = query.to; | |
int lca = query.lca; | |
int fromLimit = fromLimits[query.index]; | |
int toLimit = toLimits[query.index]; | |
PrefixFunction prefixFunction = new PrefixFunction(pattern, pattern.length + pattern.length).init(); | |
for (int v = fromLimit; ; ) { | |
if (prefixFunction.add(codes[v])) { | |
++query.result; | |
} | |
if (v == lca) break; | |
v = parentInfo.parents[0][v]; | |
} | |
List<Integer> toParents = new ArrayList<>(); | |
for (int v = toLimit; v != lca; ) { | |
toParents.add(v); | |
v = parentInfo.parents[0][v]; | |
} | |
Collections.reverse(toParents); | |
for (int v : toParents) { | |
if (v == lca) continue; | |
if (prefixFunction.add(codes[v])) { | |
++query.result; | |
} | |
} | |
} | |
for (Query query : queries) { | |
out.println(query.result); | |
} | |
} | |
void dfsQuery(int from) { | |
int fromHeight = parentInfo.h[from]; | |
queryOnRootPath.add(from, codes[from]); | |
for (Query query : queryOnRootPath.queriesByIndex[from]) { | |
int lcaHeight = parentInfo.h[query.lca]; | |
int limitHeight = lcaHeight - pattern.length + 1; | |
queryOnRootPath.updateQuery(query, limitHeight); | |
} | |
for (int to : graph[from]) { | |
if (parentInfo.h[to] < fromHeight) { | |
dfsQuery(to); | |
} | |
} | |
queryOnRootPath.removeLast(); | |
} | |
static class QueryOnRootPath { | |
PrefixFunction prefixFunction; | |
FenwickTree tree; | |
List<Query>[] queriesByIndex; | |
int[] limits; | |
int[] rootPath; | |
int rootPathLastIndex; | |
QueryOnRootPath(int[] pattern, int size, List<Query>[] queriesByIndex, int queriesCount) { | |
this.prefixFunction = new PrefixFunction(pattern, size).init(); | |
this.tree = new FenwickTree(size); | |
this.queriesByIndex = queriesByIndex; | |
this.limits = new int[queriesCount]; | |
Arrays.fill(limits, -1); | |
this.rootPath = new int[size]; | |
this.rootPathLastIndex = size; | |
} | |
void add(int v, int code) { | |
--rootPathLastIndex; | |
rootPath[rootPathLastIndex] = v; | |
if (prefixFunction.add(code)) { | |
tree.inc(rootPathLastIndex); | |
} | |
} | |
void removeLast() { | |
if (prefixFunction.removeLast()) { | |
tree.dec(rootPathLastIndex); | |
} | |
++rootPathLastIndex; | |
} | |
int count(int limit) { | |
return tree.get(limit); | |
} | |
void updateQuery(Query query, int limitHeight) { | |
query.result += count(limitHeight); | |
limits[query.index] = rootPath[max(limitHeight + 1, rootPathLastIndex)]; | |
} | |
} | |
static int[] reverse(int[] a) { | |
int[] b = new int[a.length]; | |
for (int i = 0, j = a.length - 1; i < a.length; ++i, --j) { | |
b[i] = a[j]; | |
} | |
return b; | |
} | |
static class PrefixFunction { | |
int[] pattern; | |
int[] prefix; | |
int size; | |
PrefixFunction(int[] pattern, int maxSize) { | |
this.pattern = new int[pattern.length + 1]; | |
System.arraycopy(pattern, 0, this.pattern, 0, pattern.length); | |
this.pattern[pattern.length] = -1; | |
this.prefix = new int[pattern.length + 1 + maxSize]; | |
this.size = 0; | |
} | |
PrefixFunction init() { | |
prefix[0] = 0; | |
size = 1; | |
for (int i = 1; i < pattern.length; ++i) { | |
add(pattern[i]); | |
} | |
return this; | |
} | |
boolean add(int code) { | |
int len = prefix[size - 1]; | |
while (len > 0 && pattern[len] != code) { | |
len = prefix[len - 1]; | |
} | |
if (pattern[len] == code) { | |
++len; | |
} | |
prefix[size] = len; | |
++size; | |
return (prefix[size - 1] == pattern.length - 1); | |
} | |
boolean removeLast() { | |
--size; | |
return (prefix[size] == pattern.length - 1); | |
} | |
} | |
static class ParentInfo { | |
static final int MAX_BIT = 18; | |
int size; | |
int[][] graph; | |
int[][] parents; | |
int[] h; | |
ParentInfo(int[][] graph){ | |
this.size = graph.length; | |
this.graph = graph; | |
this.h = new int[size]; | |
this.parents = new int[MAX_BIT][size]; | |
} | |
ParentInfo setRoot(int root, int rootHeight) { | |
add(root, root); | |
h[root] = rootHeight; | |
parentDfs(root, -1); | |
return this; | |
} | |
void add(int v, int parent) { | |
parents[0][v] = parent; | |
h[v] = h[parent] - 1; | |
for (int bit = 0; bit < MAX_BIT - 1; ++bit) { | |
parents[bit + 1][v] = parents[bit][parents[bit][v]]; | |
} | |
} | |
void parentDfs(int from, int parent) { | |
if (parent != -1) add(from, parent); | |
for (int to : graph[from]) { | |
if (to != parent) parentDfs(to, from); | |
} | |
} | |
int lca(int a, int b) { | |
if (h[a] < h[b]) { | |
int tmp = a; | |
a = b; | |
b = tmp; | |
} | |
int delta = h[a] - h[b]; | |
for (int bit = MAX_BIT - 1; bit >= 0; --bit) { | |
if (delta >= (1 << bit)) { | |
b = parents[bit][b]; | |
delta -= (1 << bit); | |
} | |
} | |
if (a == b) return a; | |
for (int bit = MAX_BIT - 1; bit >= 0; --bit) { | |
if (parents[bit][a] != parents[bit][b]) { | |
a = parents[bit][a]; | |
b = parents[bit][b]; | |
} | |
} | |
return parents[0][a]; | |
} | |
} | |
static class FenwickTree { | |
int size; | |
int[] tree; | |
FenwickTree(int size) { | |
this.size = size; | |
this.tree = new int[size]; | |
} | |
void inc(int index) { | |
update(index, 1); | |
} | |
void dec(int index) { | |
update(index, -1); | |
} | |
void update(int index, int delta) { | |
for (; index < size; index |= (index + 1)) { | |
tree[index] += delta; | |
} | |
} | |
int get(int index) { | |
int sum = 0; | |
for (; index >= 0; index &= (index + 1), --index) { | |
sum += tree[index]; | |
} | |
return sum; | |
} | |
} | |
///////////////////////////////////////////////////////////////////// | |
private final static boolean FIRST_INPUT_STRING = false; | |
private final static boolean MULTIPLE_TESTS = true; | |
private final boolean ONLINE_JUDGE = !new File("input.txt").exists(); | |
private final static int MAX_STACK_SIZE = 128; | |
private final static boolean OPTIMIZE_READ_NUMBERS = false; | |
///////////////////////////////////////////////////////////////////// | |
public void run(){ | |
try{ | |
timeInit(); | |
Locale.setDefault(Locale.US); | |
init(); | |
if (ONLINE_JUDGE) { | |
solve(); | |
} else { | |
do { | |
try { | |
timeInit(); | |
solve(); | |
time(); | |
out.println(); | |
} catch (NumberFormatException e) { | |
break; | |
} catch (NullPointerException e) { | |
if (FIRST_INPUT_STRING) break; | |
else throw e; | |
} | |
} while (MULTIPLE_TESTS); | |
} | |
out.close(); | |
time(); | |
}catch (Exception e){ | |
e.printStackTrace(System.err); | |
System.exit(-1); | |
} | |
} | |
///////////////////////////////////////////////////////////////////// | |
private BufferedReader in; | |
private OutputWriter out; | |
private StringTokenizer tok = new StringTokenizer(""); | |
public static void main(String[] args){ | |
new Thread(null, new F(), "", MAX_STACK_SIZE * (1L << 20)).start(); | |
} | |
///////////////////////////////////////////////////////////////////// | |
private void init() throws FileNotFoundException{ | |
Locale.setDefault(Locale.US); | |
if (ONLINE_JUDGE){ | |
if (fileName.isEmpty()) { | |
in = new BufferedReader(new InputStreamReader(System.in)); | |
out = new OutputWriter(System.out); | |
} else { | |
in = new BufferedReader(new FileReader(fileName + ".in")); | |
out = new OutputWriter(fileName + ".out"); | |
} | |
}else{ | |
in = new BufferedReader(new FileReader("input.txt")); | |
out = new OutputWriter("output.txt"); | |
} | |
} | |
//////////////////////////////////////////////////////////////// | |
private long timeBegin; | |
private void timeInit() { | |
this.timeBegin = System.currentTimeMillis(); | |
} | |
private void time(){ | |
long timeEnd = System.currentTimeMillis(); | |
System.err.println("Time = " + (timeEnd - timeBegin)); | |
} | |
private void debug(Object... objects){ | |
if (ONLINE_JUDGE){ | |
for (Object o: objects){ | |
System.err.println(o.toString()); | |
} | |
} | |
} | |
///////////////////////////////////////////////////////////////////// | |
private String delim = " "; | |
private String readLine() { | |
try { | |
return in.readLine(); | |
} catch (IOException e) { | |
throw new RuntimeIOException(e); | |
} | |
} | |
private String readString() { | |
try { | |
while(!tok.hasMoreTokens()){ | |
tok = new StringTokenizer(readLine()); | |
} | |
return tok.nextToken(delim); | |
} catch (NullPointerException e) { | |
return null; | |
} | |
} | |
///////////////////////////////////////////////////////////////// | |
private final char NOT_A_SYMBOL = '\0'; | |
private char readChar() { | |
try { | |
int intValue = in.read(); | |
if (intValue == -1){ | |
return NOT_A_SYMBOL; | |
} | |
return (char) intValue; | |
} catch (IOException e) { | |
throw new RuntimeIOException(e); | |
} | |
} | |
private char[] readCharArray() { | |
return readLine().toCharArray(); | |
} | |
private char[][] readCharField(int rowsCount) { | |
char[][] field = new char[rowsCount][]; | |
for (int row = 0; row < rowsCount; ++row) { | |
field[row] = readCharArray(); | |
} | |
return field; | |
} | |
///////////////////////////////////////////////////////////////// | |
private long optimizedReadLong() { | |
int sign = 1; | |
long result = 0; | |
boolean started = false; | |
while (true) { | |
try { | |
int j = in.read(); | |
if (-1 == j) { | |
if (started) return sign * result; | |
throw new NumberFormatException(); | |
} | |
if (j == '-') { | |
if (started) throw new NumberFormatException(); | |
sign = -sign; | |
} | |
if ('0' <= j && j <= '9') { | |
result = result * 10 + j - '0'; | |
started = true; | |
} else if (started) { | |
return sign * result; | |
} | |
} catch (IOException e) { | |
throw new RuntimeIOException(e); | |
} | |
} | |
} | |
private int readInt() { | |
if (!OPTIMIZE_READ_NUMBERS) { | |
return Integer.parseInt(readString()); | |
} else { | |
return (int) optimizedReadLong(); | |
} | |
} | |
private int[] readIntArray(int size) { | |
int[] array = new int[size]; | |
for (int index = 0; index < size; ++index){ | |
array[index] = readInt(); | |
} | |
return array; | |
} | |
private int[] readSortedIntArray(int size) { | |
Integer[] array = new Integer[size]; | |
for (int index = 0; index < size; ++index) { | |
array[index] = readInt(); | |
} | |
Arrays.sort(array); | |
int[] sortedArray = new int[size]; | |
for (int index = 0; index < size; ++index) { | |
sortedArray[index] = array[index]; | |
} | |
return sortedArray; | |
} | |
private int[] readIntArrayWithDecrease(int size) { | |
int[] array = readIntArray(size); | |
for (int i = 0; i < size; ++i) { | |
array[i]--; | |
} | |
return array; | |
} | |
/////////////////////////////////////////////////////////////////// | |
private int[][] readIntMatrix(int rowsCount, int columnsCount) { | |
int[][] matrix = new int[rowsCount][]; | |
for (int rowIndex = 0; rowIndex < rowsCount; ++rowIndex) { | |
matrix[rowIndex] = readIntArray(columnsCount); | |
} | |
return matrix; | |
} | |
private int[][] readIntMatrixWithDecrease(int rowsCount, int columnsCount) { | |
int[][] matrix = new int[rowsCount][]; | |
for (int rowIndex = 0; rowIndex < rowsCount; ++rowIndex) { | |
matrix[rowIndex] = readIntArrayWithDecrease(columnsCount); | |
} | |
return matrix; | |
} | |
/////////////////////////////////////////////////////////////////// | |
private long readLong() { | |
if (!OPTIMIZE_READ_NUMBERS) { | |
return Long.parseLong(readString()); | |
} else { | |
return optimizedReadLong(); | |
} | |
} | |
private long[] readLongArray(int size) { | |
long[] array = new long[size]; | |
for (int index = 0; index < size; ++index){ | |
array[index] = readLong(); | |
} | |
return array; | |
} | |
//////////////////////////////////////////////////////////////////// | |
private double readDouble() { | |
return Double.parseDouble(readString()); | |
} | |
private double[] readDoubleArray(int size) { | |
double[] array = new double[size]; | |
for (int index = 0; index < size; ++index){ | |
array[index] = readDouble(); | |
} | |
return array; | |
} | |
//////////////////////////////////////////////////////////////////// | |
private BigInteger readBigInteger() { | |
return new BigInteger(readString()); | |
} | |
private BigDecimal readBigDecimal() { | |
return new BigDecimal(readString()); | |
} | |
///////////////////////////////////////////////////////////////////// | |
private Point readPoint() { | |
int x = readInt(); | |
int y = readInt(); | |
return new Point(x, y); | |
} | |
private Point[] readPointArray(int size) { | |
Point[] array = new Point[size]; | |
for (int index = 0; index < size; ++index){ | |
array[index] = readPoint(); | |
} | |
return array; | |
} | |
///////////////////////////////////////////////////////////////////// | |
@Deprecated | |
private List<Integer>[] readGraph(int vertexNumber, int edgeNumber) { | |
@SuppressWarnings("unchecked") | |
List<Integer>[] graph = new List[vertexNumber]; | |
for (int index = 0; index < vertexNumber; ++index){ | |
graph[index] = new ArrayList<>(); | |
} | |
while (edgeNumber-- > 0){ | |
int from = readInt() - 1; | |
int to = readInt() - 1; | |
graph[from].add(to); | |
graph[to].add(from); | |
} | |
return graph; | |
} | |
private static class GraphBuilder { | |
final int size; | |
final List<Integer>[] edges; | |
static GraphBuilder createInstance(int size) { | |
List<Integer>[] edges = new List[size]; | |
for (int v = 0; v < size; ++v) { | |
edges[v] = new ArrayList<>(); | |
} | |
return new GraphBuilder(edges); | |
} | |
private GraphBuilder(List<Integer>[] edges) { | |
this.size = edges.length; | |
this.edges = edges; | |
} | |
public void addEdge(int from, int to) { | |
addDirectedEdge(from, to); | |
addDirectedEdge(to, from); | |
} | |
public void addDirectedEdge(int from, int to) { | |
edges[from].add(to); | |
} | |
public int[][] build() { | |
int[][] graph = new int[size][]; | |
for (int v = 0; v < size; ++v) { | |
List<Integer> vEdges = edges[v]; | |
graph[v] = castInt(vEdges); | |
} | |
return graph; | |
} | |
} | |
///////////////////////////////////////////////////////////////////// | |
private static class IntIndexPair { | |
static Comparator<IntIndexPair> increaseComparator = new Comparator<F.IntIndexPair>() { | |
@Override | |
public int compare(F.IntIndexPair indexPair1, F.IntIndexPair indexPair2) { | |
int value1 = indexPair1.value; | |
int value2 = indexPair2.value; | |
if (value1 != value2) return value1 - value2; | |
int index1 = indexPair1.index; | |
int index2 = indexPair2.index; | |
return index1 - index2; | |
} | |
}; | |
static Comparator<IntIndexPair> decreaseComparator = new Comparator<F.IntIndexPair>() { | |
@Override | |
public int compare(F.IntIndexPair indexPair1, F.IntIndexPair indexPair2) { | |
int value1 = indexPair1.value; | |
int value2 = indexPair2.value; | |
if (value1 != value2) return -(value1 - value2); | |
int index1 = indexPair1.index; | |
int index2 = indexPair2.index; | |
return index1 - index2; | |
} | |
}; | |
static IntIndexPair[] from(int[] array) { | |
IntIndexPair[] iip = new IntIndexPair[array.length]; | |
for (int i = 0; i < array.length; ++i) { | |
iip[i] = new IntIndexPair(array[i], i); | |
} | |
return iip; | |
} | |
int value, index; | |
IntIndexPair(int value, int index) { | |
super(); | |
this.value = value; | |
this.index = index; | |
} | |
int getRealIndex() { | |
return index + 1; | |
} | |
} | |
private IntIndexPair[] readIntIndexArray(int size) { | |
IntIndexPair[] array = new IntIndexPair[size]; | |
for (int index = 0; index < size; ++index) { | |
array[index] = new IntIndexPair(readInt(), index); | |
} | |
return array; | |
} | |
///////////////////////////////////////////////////////////////////// | |
private static class OutputWriter extends PrintWriter { | |
final int DEFAULT_PRECISION = 12; | |
private int precision; | |
private String format, formatWithSpace; | |
{ | |
precision = DEFAULT_PRECISION; | |
format = createFormat(precision); | |
formatWithSpace = format + " "; | |
} | |
OutputWriter(OutputStream out) { | |
super(out); | |
} | |
OutputWriter(String fileName) throws FileNotFoundException { | |
super(fileName); | |
} | |
int getPrecision() { | |
return precision; | |
} | |
void setPrecision(int precision) { | |
precision = max(0, precision); | |
this.precision = precision; | |
format = createFormat(precision); | |
formatWithSpace = format + " "; | |
} | |
String createFormat(int precision){ | |
return "%." + precision + "f"; | |
} | |
@Override | |
public void print(double d){ | |
printf(format, d); | |
} | |
void printWithSpace(double d){ | |
printf(formatWithSpace, d); | |
} | |
void printAll(double...d){ | |
for (int i = 0; i < d.length - 1; ++i){ | |
printWithSpace(d[i]); | |
} | |
print(d[d.length - 1]); | |
} | |
@Override | |
public void println(double d){ | |
printlnAll(d); | |
} | |
void printlnAll(double... d){ | |
printAll(d); | |
println(); | |
} | |
} | |
///////////////////////////////////////////////////////////////////// | |
private static class RuntimeIOException extends RuntimeException { | |
/** | |
* | |
*/ | |
private static final long serialVersionUID = -6463830523020118289L; | |
RuntimeIOException(Throwable cause) { | |
super(cause); | |
} | |
} | |
///////////////////////////////////////////////////////////////////// | |
//////////////// Some useful constants and functions //////////////// | |
///////////////////////////////////////////////////////////////////// | |
private static final int[][] steps = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; | |
private static final int[][] steps8 = { | |
{-1, 0}, {1, 0}, {0, -1}, {0, 1}, | |
{-1, -1}, {1, 1}, {1, -1}, {-1, 1} | |
}; | |
private static boolean checkCell(int row, int rowsCount, int column, int columnsCount) { | |
return checkIndex(row, rowsCount) && checkIndex(column, columnsCount); | |
} | |
private static boolean checkIndex(int index, int lim){ | |
return (0 <= index && index < lim); | |
} | |
///////////////////////////////////////////////////////////////////// | |
private static boolean checkBit(int mask, int bit){ | |
return (mask & (1 << bit)) != 0; | |
} | |
private static boolean checkBit(long mask, int bit){ | |
return (mask & (1L << bit)) != 0; | |
} | |
///////////////////////////////////////////////////////////////////// | |
private static long getSum(int[] array) { | |
long sum = 0; | |
for (int value: array) { | |
sum += value; | |
} | |
return sum; | |
} | |
private static Point getMinMax(int[] array) { | |
int min = array[0]; | |
int max = array[0]; | |
for (int index = 0, size = array.length; index < size; ++index, ++index) { | |
int value = array[index]; | |
if (index == size - 1) { | |
min = min(min, value); | |
max = max(max, value); | |
} else { | |
int otherValue = array[index + 1]; | |
if (value <= otherValue) { | |
min = min(min, value); | |
max = max(max, otherValue); | |
} else { | |
min = min(min, otherValue); | |
max = max(max, value); | |
} | |
} | |
} | |
return new Point(min, max); | |
} | |
///////////////////////////////////////////////////////////////////// | |
private static int[] getPrimes(int n) { | |
boolean[] used = new boolean[n]; | |
used[0] = used[1] = true; | |
int size = 0; | |
for (int i = 2; i < n; ++i) { | |
if (!used[i]) { | |
++size; | |
for (int j = 2 * i; j < n; j += i) { | |
used[j] = true; | |
} | |
} | |
} | |
int[] primes = new int[size]; | |
for (int i = 0, cur = 0; i < n; ++i) { | |
if (!used[i]) { | |
primes[cur++] = i; | |
} | |
} | |
return primes; | |
} | |
///////////////////////////////////////////////////////////////////// | |
int[] getDivisors(int value) { | |
List<Integer> divisors = new ArrayList<>(); | |
for (int divisor = 1; divisor * divisor <= value; ++divisor) { | |
if (value % divisor == 0) { | |
divisors.add(divisor); | |
if (divisor * divisor != value) { | |
divisors.add(value / divisor); | |
} | |
} | |
} | |
return castInt(divisors); | |
} | |
///////////////////////////////////////////////////////////////////// | |
private static long lcm(long a, long b) { | |
return a / gcd(a, b) * b; | |
} | |
private static long gcd(long a, long b) { | |
return (a == 0 ? b : gcd(b % a, a)); | |
} | |
///////////////////////////////////////////////////////////////////// | |
private static class MultiSet<ValueType> { | |
public static <ValueType> MultiSet<ValueType> createMultiSet() { | |
Map<ValueType, Integer> multiset = new HashMap<>(); | |
return new MultiSet<>(multiset); | |
} | |
private final Map<ValueType, Integer> multiset; | |
private int size; | |
public MultiSet(Map<ValueType, Integer> multiset) { | |
this.multiset = multiset; | |
this.size = 0; | |
} | |
public int size() { | |
return size; | |
} | |
public void inc(ValueType value) { | |
int count = get(value); | |
multiset.put(value, count + 1); | |
++size; | |
} | |
public void dec(ValueType value) { | |
int count = get(value); | |
if (count == 0) return; | |
if (count == 1) multiset.remove(value); | |
else multiset.put(value, count - 1); | |
--size; | |
} | |
public int get(ValueType value) { | |
Integer count = multiset.get(value); | |
return (count == null ? 0 : count); | |
} | |
} | |
///////////////////////////////////////////////////////////////////// | |
private static class IdMap<KeyType> extends HashMap<KeyType, Integer> { | |
/** | |
* | |
*/ | |
private static final long serialVersionUID = -3793737771950984481L; | |
public IdMap() { | |
super(); | |
} | |
int getId(KeyType key) { | |
Integer id = super.get(key); | |
if (id == null) { | |
super.put(key, id = size()); | |
} | |
return id; | |
} | |
} | |
///////////////////////////////////////////////////////////////////// | |
private static int[] castInt(List<Integer> list) { | |
int[] array = new int[list.size()]; | |
for (int i = 0; i < array.length; ++i) { | |
array[i] = list.get(i); | |
} | |
return array; | |
} | |
private static long[] castLong(List<Long> list) { | |
long[] array = new long[list.size()]; | |
for (int i = 0; i < array.length; ++i) { | |
array[i] = list.get(i); | |
} | |
return array; | |
} | |
///////////////////////////////////////////////////////////////////// | |
/** | |
* Generates list with values 0..<n | |
* @param n - exclusive limit of sequence | |
*/ | |
private static List<Integer> order(int n) { | |
List<Integer> sequence = new ArrayList<>(); | |
for (int i = 0; i < n; ++i) { | |
sequence.add(i); | |
} | |
return sequence; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment