Editorial for UHCC1 P5 - Binary Triangles - DMOJ: Modern Online Judge

Editorial for UHCC1 P5 - Binary Triangles

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: RAINY

Subtask 1

Precompute the distance between each pair of points, this takes time $O(N^2M)$ ~O(N^2M)~, then bruteforce all $O(N^3)$ ~O(N^3)~ 3-tuples and check if they form a triangle. This solution has time complexity $O(N^2(M+N))$ ~O(N^2(M+N))~ 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, $\sum_{k=1}^M(a_k-b_k)^2=\sum_{k=1}^M|a_k-b_k|$ for $a_k,b_k\in\{0,1\}$ ~a_k,b_k\in\{0,1\}~. 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 $i^{\text{th}}$ ~i^{\text{th}}~ bit to $1$ ~1~ if the $i^{\text{th}}$ ~i^{\text{th}}~ coodinate is $1$ ~1~. Then we recognize the distance formula as taking the bitwise XOR of the two integers and count the number of $1$ ~1~ bits.

The precomputation process can be optimized using bitset XOR and popcount, reducing the time from $O(N^2M)$ ~O(N^2M)~ to $O(N^2M/64)$ ~O(N^2M/64)~. This solution has time complexity $O(N^2(M/64+N))$ ~O(N^2(M/64+N))~ which is within the constraints.

Comments

0

thomas_li commented on Feb. 20, 2024, 5:37 p.m.

bitset

0

dnialh_ commented on Feb. 20, 2024, 5:55 p.m.

bitset