Soluție HackerRank pentru Bike Racers. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Bike Racers
Cerinta completa
There are [Expresie matematică indisponibilă în copia arhivată] bikers present in a city (shaped as a grid) having [Expresie matematică indisponibilă în copia arhivată] bikes. All the bikers want to participate in the HackerRace competition, but unfortunately only [Expresie matematică indisponibilă în copia arhivată] bikers can be accommodated in the race. Jack is organizing the HackerRace and wants to start the race as soon as possible. He can instruct any biker to move towards any bike in the city. In order to minimize the time to start the race, Jack instructs the bikers in such a way that the first [Expresie matematică indisponibilă în copia arhivată] bikes are acquired in the minimum time.
Every biker moves with a unit speed and one bike can be acquired by only one biker. A biker can proceed in any direction. Consider distance between bikes and bikers as Euclidean distance.
Jack would like to know the square of required time to start the race as soon as possible.
Input Format
The first line contains three integers, [Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată], and [Expresie matematică indisponibilă în copia arhivată], separated by a single space.
The following [Expresie matematică indisponibilă în copia arhivată] lines will contain [Expresie matematică indisponibilă în copia arhivată] pairs of integers denoting the co-ordinates of [Expresie matematică indisponibilă în copia arhivată] bikers. Each pair of integers is separated by a single space. The next [Expresie matematică indisponibilă în copia arhivată] lines will similarly denote the co-ordinates of the [Expresie matematică indisponibilă în copia arhivată] bikes.
Constraints
[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată]
[Expresie matematică indisponibilă în copia arhivată][Expresie matematică indisponibilă în copia arhivată], [Expresie matematică indisponibilă în copia arhivată][Expresie matematică indisponibilă în copia arhivată] [Expresie matematică indisponibilă în copia arhivată][Expresie matematică indisponibilă în copia arhivată]
Output Format
A single line containing the square of required time.
Sample Input
3 3 2
0 1
0 2
0 3
100 1
200 2
300 3
Sample Output
40000
Explanation
There’s need for two bikers for the race. The first biker (0,1) will be able to reach the first bike (100,1) in 100 time units. The second biker (0,2) will be able to reach the second bike (200,2) in 200 time units. This is the most optimal solution and will take 200 time units. So output will be 2002 = 40000.
Limbajul de programare folosit: java8
Cod:
import java.io.*;
import java.util.*;
public class Solution {
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++];
}
int nextInt() throws IOException {
int c;
do {
c = read();
} while (c <= ' ' && c != -1);
int sign = 1;
if (c == '-') {
sign = -1;
c = read();
}
int val = 0;
while (c > ' ') {
val = val * 10 + (c - '0');
c = read();
}
return val * sign;
}
}
private static int n, m, k;
private static long[][] dist2;
private static int[][] adj;
private static int[] pairU, pairV, level;
private static boolean bfs() {
ArrayDeque<Integer> q = new ArrayDeque<>();
Arrays.fill(level, -1);
for (int u = 0; u < n; u++) {
if (pairU[u] == -1) {
level[u] = 0;
q.add(u);
}
}
boolean foundAugPath = false;
while (!q.isEmpty()) {
int u = q.poll();
int[] edges = adj[u];
for (int v : edges) {
int pu = pairV[v];
if (pu == -1) {
foundAugPath = true;
} else if (level[pu] == -1) {
level[pu] = level[u] + 1;
q.add(pu);
}
}
}
return foundAugPath;
}
private static boolean dfs(int u) {
for (int v : adj[u]) {
int pu = pairV[v];
if (pu == -1 || (level[pu] == level[u] + 1 && dfs(pu))) {
pairU[u] = v;
pairV[v] = u;
return true;
}
}
level[u] = -1;
return false;
}
private static int maxMatching() {
Arrays.fill(pairU, -1);
Arrays.fill(pairV, -1);
int matching = 0;
while (bfs()) {
for (int u = 0; u < n; u++) {
if (pairU[u] == -1 && dfs(u)) {
matching++;
if (matching >= k) return matching;
}
}
}
return matching;
}
private static boolean can(long threshold) {
adj = new int[n][];
for (int i = 0; i < n; i++) {
int cnt = 0;
for (int j = 0; j < m; j++) {
if (dist2[i][j] <= threshold) cnt++;
}
int[] row = new int[cnt];
int p = 0;
for (int j = 0; j < m; j++) {
if (dist2[i][j] <= threshold) row[p++] = j;
}
adj[i] = row;
}
int match = maxMatching();
return match >= k;
}
public static void main(String[] args) throws Exception {
FastScanner fs = new FastScanner(System.in);
n = fs.nextInt();
m = fs.nextInt();
k = fs.nextInt();
long[] bx = new long[n], by = new long[n];
for (int i = 0; i < n; i++) {
bx[i] = fs.nextInt();
by[i] = fs.nextInt();
}
long[] cx = new long[m], cy = new long[m];
for (int i = 0; i < m; i++) {
cx[i] = fs.nextInt();
cy[i] = fs.nextInt();
}
dist2 = new long[n][m];
long[] all = new long[n * m];
int p = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
long dx = bx[i] - cx[j];
long dy = by[i] - cy[j];
long d = dx * dx + dy * dy;
dist2[i][j] = d;
all[p++] = d;
}
}
Arrays.sort(all);
long[] uniq = new long[p];
int u = 0;
for (int i = 0; i < p; i++) {
if (i == 0 || all[i] != all[i - 1]) uniq[u++] = all[i];
}
pairU = new int[n];
pairV = new int[m];
level = new int[n];
int lo = 0, hi = u - 1;
long ans = uniq[hi];
while (lo <= hi) {
int mid = (lo + hi) >>> 1;
long thr = uniq[mid];
if (can(thr)) {
ans = thr;
hi = mid - 1;
} else {
lo = mid + 1;
}
}
System.out.println(ans);
}
}
Scor obtinut: 1.0
Submission ID: 464614579
Link challenge: https://www.hackerrank.com/challenges/bike-racers/problem