Editorial for CCC '22 S4 - Good Triplets - Olympiads Online Judge

Editorial for CCC '22 S4 - Good Triplets

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: d

For the first subtask, it suffices to follow the definition of a good triplet. Firstly, there are $\mathcal{O}(N^3)$ $O (N^{3})$ ways to select $(a, b, c)$ $(a, b, c)$ . Secondly, consider the condition that the origin is strictly inside the triangle. This is equivalent to saying that $P_a$ $P_{a}$ , $P_b$ $P_{b}$ , and $P_c$ $P_{c}$ divide the circle into $3$ $3$ arcs, and each arc is strictly shorter than $\frac{C}{2}$ $\frac{C}{2}$ . This leads to the following approach. Sort the positions so that $P_a \le P_b \le P_c$ $P_{a} \leq P_{b} \leq P_{c}$ , then check that

P_{b} - P_{a} < \frac{C}{2}

P_{c} - P_{b} < \frac{C}{2}

, and

(P_{a} + C) - P_{c} < \frac{C}{2}

For example, the first of these checks can be implemented in code as P[b]-P[a] < (C+1)/2 in C++ or Java, or P[b]-P[a] < (C+1)//2 in Python 3.

For the second subtask, the goal is to find a solution that works well when $C$ $C$ is small. Let $L_x$ $L_{x}$ be the number of points drawn at location $x$ $x$ . If three locations $i, j, k$ $i, j, k$ satisfy the second condition, we want to add $L_i \times L_j \times L_k$ $L_{i} \times L_{j} \times L_{k}$ to the answer. This approach is $\mathcal{O}(N + C^3)$ $O (N + C^{3})$ and is too slow. However, we can improve from three nested loops to two nested loops. If $i$ $i$ and $j$ $j$ are chosen already, either $k$ $k$ does not exist, or $k$ $k$ is in an interval. It is possible to replace the third loop with a prefix sum array. This algorithm's time complexity is $\mathcal{O}(N + C^2)$ $O (N + C^{2})$ .

It is possible to optimize this approach to $\mathcal{O}(N + C)$ $O (N + C)$ and earn $15$ $15$ marks. The idea is to eliminate both the $j$ $j$ and $k$ $k$ loop. Start at $i = 0$ $i = 0$ and compute $L_j \times L_k$ $L_{j} \times L_{k}$ in $\mathcal{O}(C)$ $O (C)$ time. The next step is to transition from $i = 0$ $i = 0$ to $i = 1$ $i = 1$ , and to maintain $L_j \times L_k$ $L_{j} \times L_{k}$ in $\mathcal{O}(1)$ $O (1)$ time. This requires strong familiarity with prefix sum arrays. Care with overflow and off-by-one errors is required.

Comments

23

neynt commented on March 6, 2022, 4:36 p.m. ← edited →

I found this problem a lot easier to think about if you count triplets of points that don't form a triangle and subtract that from the total number of triplets. These are exactly the triplets whose points all belong on a closed half of the circle, so sweeping two pointers along the circle suffices to do this in $\mathcal{O}(N + C)$ $O (N + C)$ time.