CF - Cellular Network

Authors: Nathan Wang, Benjamin Qi, Maggie Liu, Brad Ma, George Pong

Official Editorial

Solution 1 - Binary Search on a Sorted Array

Time Complexity: O(NlogN)\mathcal{O}(N \log N)

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 exists
int 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 exists
static 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 TT's position is greater a city CC's position, then all towers with a coordinate greater that of TT cannot pair to provide the minimum distance with CC. Furthermore, if a city C1C_1 has a position less than C2C_2, then any towers with a position less than that of C1C_1's tower cannot provide the minimum distance for C2C_2. 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: O(N)\mathcal{O}(N)

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 towers
cities = 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 towers
until the selected tower's position is greater than the city's position. (As
then, 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 towers\texttt{towers} to store the coordinates of the cellular towers. For each city, we want to find the closest tower and calculate the distance. The minimal rr 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 dist\texttt{dist} to be the minimum of the distance to the tower on the right and the distance to the tower on the left. Then, set rr to be the maximum of itself and dist\texttt{dist}.

Time Complexity: O(NlogN)\mathcal{O}(N\log N)

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!