Given a radius, find the coordinates (x, y) such that the distance between (x, y) to the origin is greater than the radius. However, I want to find the distance that is the smallest distance that is greater than the radius. Problem is seen here: open.kattis.com/problems/discdistrict. My code works well for radii that are less than or equal to 5000. However, for large radii, my code starts to break and takes exponentially longer to finish!! Are there any ideas?

Examples: 1 yields (1, 1). 5 yields (2, 5). 10 yields (5, 9). (radius | radius >= 10,000) takes an exponentially long period of time.

import java.util.ArrayList;
import java.util.Collections;
import java.util.Scanner;

public class disc_district {

    public static void main(String[] args) {
        
        Scanner new_scanner = new Scanner(System.in);

        int radius = new_scanner.nextInt();
        new_scanner.close();

        //ArrayList<Double> new_distance = new ArrayList<>();

        double min_max_dist = Double.MAX_VALUE - 1;
        int[] new_min_pair = new int[2];

        for (int i = (radius / 2); i <= radius; i  ) {
            int start = (int)Math.floor(Math.sqrt(Math.pow(radius, 2) - Math.pow(i, 2)))   1;
            for (int j = Math.max(i, start); j <= radius; j  ) {
            //for (int j = i; j <= radius; j  ) {
                double new_dist = Math.sqrt(Math.pow(i, 2)   Math.pow(j, 2));

                if (new_dist > radius) {
                    if (min_max_dist > new_dist) {
                        min_max_dist = new_dist;
                        new_min_pair[0] = i;
                        new_min_pair[1] = j;
                    }
                }
            }
        }
        System.out.println(new_min_pair[0]   " "   new_min_pair[1]);
    }
}

Thanks again!

CodePudding user response：

It does not takes an exponential time to finish, just a quadratic time, that is O(radius² / 4). This is because you use 2 nested loops. You can speed up the inner-most loop by just solving a basic conic inequation.

Indeed, you are searching for j values where sqrt(i² j²) > r with r = radius. This means i² j² > r² since all values are expected to be positives ones. This means j² > r² - i² and so j > sqrt(r² - i²). As a result, you can start the second inner loop to the value Math.sqrt(Math.pow(r, 2) - Math.pow(i, 2)) if it is bigger than i (note that the expression in the square root is always positive since i <= r).

The resulting code is:

        for (int i = (radius / 2); i <= radius; i  ) {
            int start = (int)Math.floor(Math.sqrt(Math.pow(radius, 2) - Math.pow(i, 2)))   1;
            for (int j = Math.max(i, start); j <= radius; j  ) {
                System.out.println(i   " "   j);
            }
        }

Note that if you want to get one value, you can just use a break instruction so to avoid many unneeded computations.

Assuming the initial code is correct and you really need all the values to be printed, the complexity of the new code is optimal (each iteration is done in a constant time and is strictly useful since it results in a printed line), but it is still quadratic. A deeper analysis of the code shows its (optimal) complexity is O(radius² / 11.68). Thus the new code is only about ~3 times faster in theory. It can still be slow since there are a lot of values to be printed. It may be interesting to better control when the output is flushed.

Update:

Based on the additional information (about the distance being minimized and only one solution required to be printed), here is the resulting code:

        double min_max_dist = Double.MAX_VALUE - 1;
        int[] new_min_pair = new int[2];

        for (int i = (radius / 2); i <= radius; i  ) {
            int start = (int)Math.floor(Math.sqrt(Math.pow(radius, 2) - Math.pow(i, 2)))   1;
            int j = Math.max(i, start);
            double new_dist = Math.sqrt(Math.pow(i, 2)   Math.pow(j, 2));
            if (new_dist > radius) {
                if (min_max_dist > new_dist) {
                    min_max_dist = new_dist;
                    new_min_pair[0] = i;
                    new_min_pair[1] = j;
                }
            }
        }
        System.out.println(new_min_pair[0]   " "   new_min_pair[1]);

This code find the solution that minimize the distance. It runs in O(n/2) time, that is, a linear time.