CF - Cellular Network

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

Edit This Page

Official Editorial

Solution 1 - Binary Search

Time Complexity: O(Nlog⁡N)\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 first_at_least(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;

Python

def first_at_least(value: int) -> int:
	"""
	:return the first index in the array that is >= value, or len(arr)
	if no such index exists
	"""
	lo = 0
	hi = len(towers)
	while lo < hi:
		mid = (lo + hi) // 2
		if towers[mid] > value:

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();

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!

Join Forum