Editorial for UHCC1 P5 - Binary Triangles
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
Subtask 1
Precompute the distance between each pair of points, this takes time , then bruteforce all
3-tuples and check if they form a triangle. This solution has time complexity
which is within the constraints.
Subtask 2
First notice that you can completely ignore the square root in the distance formula as it makes no difference. Since all coordinates are binary, we can replace the square of the difference with absolute value of the difference, for
. This distance formula counts exactly the number of coodinates that are different given two points. Now if we write the coordinates as a binary integer, mark the
bit to
if the
coodinate is
. Then we recognize the distance formula as taking the bitwise XOR of the two integers and count the number of
bits.
The precomputation process can be optimized using bitset XOR and popcount, reducing the time from to
. This solution has time complexity
which is within the constraints.
Comments
bitset
bitset