2012 Canadian Computing Competition, Stage 1

Problem S3: Absolutely Acidic

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 sensors in the river, and each sensor gives an integer reading R. 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 Format

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

Output Format

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

5
1
1
1
4
3

Sample Output 1

3

Sample Input 2

4
10
6
1
8

Sample Output 2

9

All Submissions
Best Solutions

Point Value: 7
Time Limit: 5.00s
Memory Limit: 16M
Added: Feb 29, 2012

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, TEXT, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

yes

[quote]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.[/quote]
"more than two" should be "more than one" or "more than or equal to two". If programmed exactly as the problem statement requires, the solution won't pass if [code]length(highest_readings) == 2[/code] and [code]length(second_highest_readings) > 1[/code], because according to the rules exactly, it won't produce an answer. This situation appears in case 3. I understand this is a official problem statement, but it can still be corrected for future PEG users.

length(highest_readings) == 2

length(second_highest_readings) > 1

Not necessary. The line before asks you to [quote]find the absolute difference between the two most frequent readings.[/quote]
Naturally if there are exactly two most frequent readings, you simply output their absolute difference.

That entire second paragraph is just a clarification for some special cases.

I guess I am using something that exists in 3.4 but not 3.2; can someone post the traceback or otherwise enlighten me?  Thanks,

The default parameter was added in 3.4.

Thanks, jargon.