CF - Cellular Network
Authors: Nathan Wang, Benjamin Qi, Maggie Liu, Brad Ma, George Pong
Solution 1 - Binary Search on a Sorted Array
Time Complexity:
C++
#include <bits/stdc++.h>using namespace std;// returns the first index in the array that is >= value, or arr.size() if no// such index existsint firstAtLeast(const vector<int> &arr, int value) {int lo = 0, hi = arr.size();while (lo < hi) {int mid = (lo + hi) / 2;if (arr[mid] >= value) hi = mid;
Java
import java.io.*;import java.util.*;public class CellularNetwork {static final int TWO_BILLION = 2000000000;// returns the first index in the array that is >= value,// or towers.length if no such index existsstatic int firstAtLeast(int[] towers, int value) {int low = 0, high = towers.length;
Solution 2 - Two Pointers
For each city, we need to find the minimum distance to a tower, which we will call pairing. Observe that if a tower 's position is greater a city 's position, then all towers with a coordinate greater that of cannot pair to provide the minimum distance with . Furthermore, if a city has a position less than , then any towers with a position less than that of 's tower cannot provide the minimum distance for . These two details allow us to use two pointers to solve this problem.
We store two pointers, one for the current city and one for the current tower. We start at the first city and first tower, both with the smallest coordinate. We calculate the distance between the city and towers with increasingly higher coordinates until the current tower's coordinate is greater than that of the current city. One of these distances must be the minimum distance from the city to all towers. Then, we start the process for the next city and keep the pointer at the current tower. We repeat this process for all cities in order of their position. The maximum out of all the minimum distances between a city and a tower will be our answer.
Time Complexity:
C++
#include <bits/stdc++.h>using namespace std;typedef long long ll;typedef pair<int, int> pii;typedef vector<int> vi;#define mp make_pair#define pb push_back
Python
n, m = map(int, input().split())# We remove all the duplicate cities and towerscities = sorted(list(set(map(int, input().split()))))towers = sorted(list(set(map(int, input().split()))))"""We start at the first city. For each city, we calculate the distance to towersuntil the selected tower's position is greater than the city's position. (Asthen, the distance will only increase). Then, we continue for the next city
Java
import java.io.*;import java.util.*;public class CellularNetwork2 {static final int MOD = 1000000007;static final int MAXIMUM_SIZE = 100000;public static void main(String[] args) {Kattio io = new Kattio();
Solution 3 - Using a Set
We use the set to store the coordinates of the cellular towers. For each city, we want to find the closest tower and calculate the distance. The minimal will be the maximum of all these distances. To find the closest tower to a certain city, we check the towers to the left and right and determine which one is closer.
For each city, we use
lower_bound
to
find the closest tower to the right of the city. If this tower is found,
calculate the distance between this tower and the city. If the tower is not at
the beginning of the set, the previous tower in the set will be the tower to the
left of the city. Define to be the minimum of the distance to
the tower on the right and the distance to the tower on the left. Then, set
to be the maximum of itself and .
Time Complexity:
C++
#include <algorithm>#include <iostream>#include <set>using namespace std;int main() {int n, m;cin >> n >> m;int cities[n];set<int> towers;
Java
import java.io.*;import java.util.*;public class CellularNetwork {Code Snippet: Kattio (Click to expand)public static void main(String[] args) {Kattio io = new Kattio();int n = io.nextInt();int m = io.nextInt();
Join the USACO Forum!
Stuck on a problem, or don't understand a module? Join the USACO Forum and get help from other competitive programmers!