DCEPCA09 - MMM

no tags 

Everyone knows how to find mean, median and mode of an array of numbers. For people who don’t know this, here is the description:

  • Mean is the arithmetic average of a set of values.
  • Median of a finite list of numbers can be found by arranging all the observations from lowest value to highest value and picking the middle one. If there is an even number of observations, then there is no single middle value; the median is then usually defined to be the mean of the two middle values.
  • The mode is the value that appears most often in a set of data. If more than one number is applicable to be the mode, select the highest value number amongst them as the mode.

The problem is just to find these 3 values. Given an array of numbers and two indices i and j, find the mean, median and mode of elements in the interval i to j including numbers at indices i and j. Note that i and j are 0 index based.

Constraints

2 <= N <= 10000
1 <= Q <= 10000
0 <= A[i] <= 10^8
0 <= i < N
i <= j < N

Input

First line contains N which is the total number of numbers in the array. The next line contains N numbers A[i] which are the elements of the array. Next line contains a number Q which defines the total number of queries we are making for the interval i to j. It is followed by Q lines each containing 2 numbers i and j which denotes the indices to be queried for.

Output

Print Q lines each containing 3 numbers Mean, Median and Mode respectively. If the answer for any case comes to be a floating point, then take the integer part of the number as the answer. For example: if mean, median and mode comes up to be 6.44 7.8 9 then the final answer is 6 7 9.

Example

Input:
5
6 5 3 7 7
2
1 2
0 4

Output: 4 4 5
5 6 7

hide comments
mahabub618: 2023-01-26 16:51:04

AC in one go. Can be solved using Segment tree, Mo's and Binary Search optimizely.

Last edit: 2023-01-26 16:53:16
joe85123: 2019-09-01 16:35:21

nice problem for using different data structures in one place. And pretty basic implementation.

DK...: 2019-03-10 15:37:31

O(n*sqrt(n*log(n))) works fine, even using fast i/o methods.

Avinash Thummala: 2012-12-30 22:08:48

Getting TLE. Used STL's Unordered_Map and Min-Max Heaps. Would their customized implementations do the job or am I missing some trick :-?

Rohan: 2012-12-26 00:03:16

my code is running well and good on ideone but here i am getting a RE after 7th case!

Last edit: 2012-12-26 00:03:30
Artur Laskowski: 2012-12-13 22:45:02

problem code: 8257109
I am sure that my result is correct, because I do everything like it is showed at description, then why it get WA. Are the test completly good?

>> Your code has bug.

Last edit: 2012-12-27 13:37:06
Alex Anderson: 2012-12-06 17:15:24

Kunal, when you get a RE, it stops running the cases. But the display still shows them all. You could be failing after the 1st or 2nd, or however many cases.

Kunal: 2012-12-06 17:15:24

@dce coders:-how many cases dude...getting sigsegv after 14th case!!!what may be the problem???
problem code:-8202951


Added by:dce coders
Date:2012-12-05
Time limit:0.5s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY JULIA KTLN NIM OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET
Resource:Own Problem