PrevNext
Very Frequent
 0/19

Basic Complete Search

Authors: Darren Yao, Dong Liu

Contributors: Brad Ma, Nathan Gong

Problems involving iterating through the entire solution space.

Edit This Page
Resources
IUSACO

module is based off this


In many problems (especially in Bronze) it suffices to check all possible cases in the solution space, whether it be all elements, all pairs of elements, or all subsets, or all permutations. Unsurprisingly, this is called complete search (or brute force), because it completely searches the entire solution space.

Focus Problem – try your best to solve this problem before continuing!

Solution - Maximum Distance

We can iterate through every pair of points and find the square of the distance between them, by squaring the formula for Euclidean distance:

distance[(x1,y1),(x2,y2)]2=(x2x1)2+(y2y1)2.\text{distance}[(x_1,y_1),(x_2,y_2)]^2 = (x_2-x_1)^2 + (y_2-y_1)^2.

Maintain the current maximum square distance in max_squared.

C++

#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> x(n), y(n);
for (int &t : x) { cin >> t; }
for (int &t : y) { cin >> t; }

Java

import java.io.*;
import java.util.*;
public class MaxDist {
public static void main(String[] args) throws IOException {
Kattio io = new Kattio();
int n = io.nextInt();
int[] x = new int[n];
int[] y = new int[n];

Python

Warning!

Make sure to submit with PyPy, as this solution TLEs using normal Python.

n = int(input())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
max_squared = 0 # stores the current maximum
for i in range(n): # for each first point
for j in range(i + 1, n): # and each second point
dx = x[i] - x[j]
dy = y[i] - y[j]
square = dx * dx + dy * dy

A couple notes:

  • Since we're iterating through all pairs of points, we start the jj loop from j=i+1j = i+1 so that point ii and point jj are never the same point. Furthermore, it makes it so that each pair is only counted once. In this problem, it doesn't matter whether we double-count pairs or whether we allow ii and jj to be the same point, but in other problems where we're counting something rather than looking at the maximum, it's important to be careful that we don't overcount.
  • Secondly, the problem asks for the square of the maximum Euclidean distance between any two points. Some students may be tempted to maintain the maximum distance in an integer variable, and then square it at the end when outputting. However, the problem here is that while the square of the distance between two integer points is always an integer, the distance itself isn't guaranteed to be an integer. Thus, we'll end up shoving a non-integer value into an integer variable, which truncates the decimal part.

C++

The following solution correctly stores the maximum distance in a floating point variable.

#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<int> x(n), y(n);
for (int &t : x) { cin >> t; }
for (int &t : y) { cin >> t; }

However, it still fails on the following test case (it outputs 12, while the correct answer is 13):

2
0 3
2 0

Rounding suffices ((int) round(pow(max_dist, 2))), but the takeaway is that you should stick with integers whenever possible.

Java

The following solution correctly stores the maximum distance in a floating point variable.

import java.io.*;
import java.util.*;
public class MaxDist {
public static void main(String[] args) throws IOException {
Kattio io = new Kattio();
int n = io.nextInt();
int[] x = new int[n];
int[] y = new int[n];

However, it still fails on the following test case (it outputs 12, while the correct answer is 13):

2
0 3
2 0

Rounding suffices ((int) Math.round(Math.pow(maxDist, 2))), but the takeaway is that you should stick with integers whenever possible.

Python

The following solution correctly stores the maximum distance in a floating point variable.

import math
n = int(input())
x = list(map(int, input().split()))
y = list(map(int, input().split()))
max_dist = 0
for i in range(n):
for j in range(i + 1, n):
dx = x[i] - x[j]
dy = y[i] - y[j]
square = dx * dx + dy * dy
max_dist = max(max_dist, math.sqrt(square))
print(int(max_dist**2))

However, it still fails on the following test case (it outputs 12, while the correct answer is 13):

2
0 3
2 0

Rounding suffices (round(MaxDistance ** 2)), but the takeaway is that you should stick with integers whenever possible.

Problems

StatusSourceProblem NameDifficultyTags
BronzeEasy
Show TagsComplete Search
BronzeEasy
Show TagsComplete Search
BronzeEasy
Show TagsComplete Search
BronzeNormal
Show TagsComplete Search, Sorting
BronzeNormal
Show TagsComplete Search
BronzeNormal
Show TagsComplete Search
BronzeNormal
Show TagsComplete Search
BronzeNormal
Show TagsComplete Search
BronzeNormal
Show TagsComplete Search
BronzeHard
Show TagsComplete Search
SilverHard
Show TagsComplete Search
BronzeHard
Show TagsComplete Search
BronzeHard
Show TagsComplete Search
BronzeVery Hard
Show TagsComplete Search
BronzeVery Hard
Show TagsComplete Search
BronzeVery Hard
Show TagsComplete Search
BronzeVery Hard
Show TagsComplete Search
SilverVery Hard
Show TagsComplete Search

Module Progress:

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!

PrevNext