CCC '12 S3 - Absolutely Acidic - DMOJ: Modern Online Judge

CCC '12 S3 - Absolutely Acidic

View as PDF

Submit solution

All submissions

Best submissions

Points: 7 (partial)

Time limit: 3.0s

Memory limit: 256M

Problem type

Canadian Computing Competition: 2012 Stage 1, Senior #3

You are gathering readings of acidity level in a very long river in order to determine the health of the river. You have placed $N$ $N$ sensors $(2 \le N \le 2\,000\,000)$ $(2 \leq N \leq 2 000 000)$ in the river, and each sensor gives an integer reading $R$ $R$ $(1 \le R \le 1\,000)$ $(1 \leq R \leq 1 000)$ . For the purposes of your research, you would like to know the frequency of each reading, and find the absolute difference between the two most frequent readings.

If there are more than two readings that have the highest frequency, the difference computed should be the largest such absolute difference between two readings with this frequency. If there is only one reading with the largest frequency, but more than one reading with the second largest frequency, the difference computed should be the largest absolute difference between the most frequently occurring reading and any of the readings which occur with second-highest frequency.

Input Specification

The first line of input will be the integer $N$ $N$ $(2 \le N \le 2\,000\,000)$ $(2 \leq N \leq 2 000 000)$ , the number of sensors. The next $N$ $N$ lines each contain the reading for that sensor, which is an integer $R$ $R$ $(1 \le R \le 1\,000)$ $(1 \leq R \leq 1 000)$ . You should assume that there are at least two different readings in the input.

Output Specification

Output the positive integer value representing the absolute difference between the two most frequently occurring readings, subject to the tie-breaking rules outlined above.

Sample Input 1

Copy

Output for Sample Input 1

Copy

Sample Input 2

Copy

Output for Sample Input 2

Copy

Comments

0

gavin_chen commented on Nov. 10, 2024, 9:38 p.m.

If their are more than two numbers in the input with the same amount of occurrences, do I calculate the absolute difference using the two with the same number of occurrences, or do I calculate it with the second most frequent amount of occurrences?

0

4EVr_Working commented 59 days ago

If multiple numbers have the same amount of occurrences, I think you would calculate the absolute difference of the two numbers that will cause you to get the largest possible absolute value.

If there are more than two readings that have the highest frequency, the difference computed should be the largest such absolute difference between two readings with this frequency.