CCC '22 S4 - Good Triplets

View as PDF

Submit solution

Points: 15 (partial)
Time limit: 3.0s
Memory limit: 1G

Problem types
Canadian Computing Competition: 2022 Stage 1, Senior #4

Andrew is a very curious student who drew a circle with the center at (0, 0) and an integer circumference of C \ge 3. The location of a point on the circle is the counter-clockwise arc length from the right-most point of the circle.

Andrew drew N \ge 3 points at integer locations. In particular, the i^\text{th} point is drawn at location P_i (0 \le P_i \le C-1). It is possible for Andrew to draw multiple points at the same location.

A good triplet is defined as a triplet (a, b, c) that satisfies the following conditions:

  • 1 \le a < b < c \le N.
  • The origin (0, 0) lies strictly inside the triangle with vertices at P_a, P_b, and P_c. In particular, the origin is not on the triangle's perimeter.

Lastly, two triplets (a, b, c) and (a', b', c') are distinct if a \ne a', b \ne b', or c \ne c'.

Andrew, being a curious student, wants to know the number of distinct good triplets. Please help him determine this number.

Input Specification

The first line contains the integers N and C, separated by one space.

The second line contains N space-separated integers. The i^\text{th} integer is P_i (0 \le P_i \le C-1).

The following table shows how the available 15 marks are distributed.

Marks AwardedNumber of PointsCircumferenceAdditional Constraints
3 marks3 \le N \le 2003 \le C \le 10^6None
3 marks3 \le N \le 10^63 \le C \le 6\,000None
6 marks3 \le N \le 10^63 \le C \le 10^6P_1, P_2, \dots, P_N are all distinct (i.e., every location contains at most one point)
3 marks3 \le N \le 10^63 \le C \le 10^6None

Output Specification

Output the number of distinct good triplets.

Sample Input

8 10
0 2 5 5 6 9 0 0

Output for Sample Input


Explanation of Output for Sample Input

Andrew drew the following diagram.

The origin lies strictly inside the triangle with vertices P_1, P_2, and P_5, so (1, 2, 5) is a good triplet. The other five good triplets are (2, 3, 6), (2, 4, 6), (2, 5, 6), (2, 5, 7), and (2, 5, 8).


There are no comments at the moment.