Problems with Subproblems

On Codeforces, a problem is either solved or not. Other platforms divide problems into subproblems with different constraints, each awarding points, so the verdict shows your score. This format is common in major contests like national and international Olympiads.

Iso-celestial

Codeforces

You are given \(N\) points on a \(2\) dimensional coordinate plane, where \(N \leq 3000\). Your task is to count the number of triplets of points which form an isosceles triangle.

Scoring

The problem consists of three subproblems which differ only in the constraints on \(N\), as described by the table.

Subproblem	Constraints	Points
1	\(N = 3\)	33
2	\(N \leq 100\)	33
3		34

Note

In the third subproblem there are no additional constraints, meaning that the only constraints that will hold are the ones from the statement. For \(N\) that means \(1 \leq N \leq 3000\).

Solution for Subproblem 1

Here we are only given 3 points so either they form an isosceles triangle or they don’t. For this we can check if any 2 edges have equal lengths:

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

int n;

long long x[3001], y[3001];

long double dist(int i, int j) {
    long double dy = y[i] - y[j];
    long double dx = x[i] - x[j];

    return sqrtl(dy * dy + dx * dx);
}

bool f(int a, int b, int c) {
    long double ab = dist(a, b);
    long double ac = dist(a, c);
    long double bc = dist(b, c);

    return (ab == ac || ab == bc || ac == bc);
}

int main() {
    cin >> n;

    for (int i = 0 ; i < n ; i++) {
        cin >> x[i]>> y[i];
    }

    cout << f(0, 1, 2);
}

Solution for Subproblem 2

Since \(N \leq 100\) in this subproblem, we can loop over all triplets and test each one using the solution from the previous subproblem. This approach performs \(O(N^3)\) checks, which is too slow for the full problem, where \(N \leq 3000\).

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

int n;

long long x[3001], y[3001];

long double dist(int i, int j); // same as before
bool f(int a, int b, int c); // same as before

int main () {

    cin >> n;

    for (int i = 0 ; i < n ; i++) {
        cin >> x[i]>> y[i];
    }

    int counter = 0;

    for (int i = 0 ; i < n ; i++) {
        for (int j = i + 1 ; j < n ; j++) {
            for (int k = j + 1 ; k < n ; k++) {
                if (f(i, j, k)) counter++;
            }
        }
    }

    cout << counter;
}

Solution for Subproblem 3 (Full solution)

Here we need to think outside the box and make observations to come up with faster solutions. Lets consider a single point \(P\) and calculate the distance between \(P\) and every other point.

We can observe that if two points \(X\) and \(Y\) have the same distance from \(P\), then the triplet \((P, X, Y)\) forms an isosceles triangle. If there are \(K\) points all at the same distance from \(P\) then any pair from those \(K\) points when grouped with \(P\) will form an isosceles triangle.

This gives us an algorithm which performs \(O(N^2)\) steps. For each point \(P\), loop over every other point \(Q\) and count the number of times each distinct distance appears. Then loop over the distinct distances. Let \(C\) be the count for that distance. Add \(C \choose 2\) to the answer.

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

int n;

long long x[3001], y[3001];

long double dist (int i, int j); // same as before

int main () {

    cin >> n;

    for (int i = 0 ; i < n ; i++) {
        cin >> x[i]>> y[i];
    }

    int counter = 0;

    for (int i = 0 ; i < n ; i++) {
        long double all[n];

        for (int j = 0 ; j < n ; j++) {
            all[j] = dist(i, j);
        }

        sort(all, all + n);

        int cnt = 1;

        for (int j = 1 ; j < n ; j++) {
            if (all[j] != all[j-1]) {
                counter += cnt * (cnt - 1) / 2;
                cnt = 0;
            }
            cnt++;
        }

        counter += cnt * (cnt - 1) / 2;
    }

    cout << counter;
}

The looping over all distinct distances is done by sorting all the distances, and going through this sorted order, but taking an action only when the current distance is different to the previous one. To simplify the code, we are conveniently using the fact that the distance of the point to itself will be listed at the index \(0\) in the sorted array, so the iteration can start from the index \(1\).