CF - The Meeting Place Cannot Be Changed

Authors: Aditya Gupta, George Pong

Edit This Page

Table of Contents

ExplanationImplementation

Official Analysis

Explanation

We can binary search on the location where the friends will meet up. Since we want a precision of 10−610^{-6}, we stop when the difference between high and low is less than 10−610^{-6}.

Whenever we are calculating the answer, we take note of which side the maximum answer came from. If the max answer comes from both sides, regardless of where we decide to go next, our answer will only increase, so we return that answer. Otherwise, if it only comes from one side of the point that we just calculated, we move our search towards that side, as moving it towards the other side will only increase our answer.

Implementation

Time Complexity: O(Nlog⁡M)\mathcal{O}(N\log M) where MM is the farthest north location

C++

#include <bits/stdc++.h>
using namespace std;


using ll = long long;


const double MAX_ERROR = 10e-7;


vector<double> locations;
vector<double> speeds;

Java

import java.util.*;


public class MeetingPlace {
	static final double MAX_ERROR = 10e-7;


	static List<Double> locations = new ArrayList<>();
	static List<Double> speeds = new ArrayList<>();


	static double min_ans = Double.MAX_VALUE;
	static double curr_min_time;

Python

num_friends = int(input())
friend_coords = list(map(int, input().split()))
friend_veloci = list(map(int, input().split()))




def all_friends_converge(seconds: int) -> bool:
	"""
	Checks whether all friends can converge on one point in the specified time interval.


	:param seconds: Amount of seconds given for friends to converge.

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