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
6 - Complete Search

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.

Maximum Distance
CF - Easy

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=(x2−x1)2+(y2−y1)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
Bronze
Milk Pails
Easy
Show TagsComplete Search
Bronze
Diamond Collector
Easy
Show TagsComplete Search
Bronze
Daisy Chains
Easy
Show TagsComplete Search
Bronze
Counting Liars
Normal
Show TagsComplete Search, Sorting
Bronze
Cow Gymnastics
Normal
Show TagsComplete Search
Bronze
Bovine Genomics
Normal
Show TagsComplete Search
Bronze
Triangles
Normal
Show TagsComplete Search
Bronze
Lifeguards
Normal
Show TagsComplete Search
Bronze
Why Did the Cow Cross the Road II
Normal
Show TagsComplete Search
Bronze
Guess the Animal
Hard
Show TagsComplete Search
Silver
Bovine Genomics
Hard
Show TagsComplete Search
Bronze
Load Balancing
Hard
Show TagsComplete Search
Bronze
Sleeping in Class
Hard
Show TagsComplete Search
Bronze
Contaminated Milk
Very Hard
Show TagsComplete Search
Bronze
Cowntact Tracing
Very Hard
Show TagsComplete Search
Bronze
Bull in a China Shop
Very Hard
Show TagsComplete Search
Bronze
Moo Language
Very Hard
Show TagsComplete Search
Silver
Load Balancing
Very 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!

Join Forum
PrevNext