UmCaraLegal's blog

By UmCaraLegal, history, 2 months ago, In English,

Hi everyone !

We have a static array of size N and Q queries. Each Query given us two integers i and j.

For each query we need to answer what is the maximum frequency of the values of this range.

For example:

A = {3, 4, 3, 4, 4, 1 }

Query(0, 2) = 2 (The value 3 repeat 2 times)

Query(0, 5) = 3 (The value 4 repeat 3 times)

The problem can be found here : http://www.spoj.com/problems/FREQ2/

1 <= N, Q <= 100000, 0 <= A[i] <= 100000

OBS: I would like to know if this problem is possible to solve "online" and the total complexity O(N*log(N)) __ If you have any idea comment bellow, please :D.

Solution using Mo's algorithm (Offline Queries and O(N*sqrt(N)) :

You need to save the value's frequency in a array.

Freq[i] will determine how many times the value "i" has been appears in our current array

Every times you will need to remove a element, decrease Freq[A[i]] by one and check if your answer should be changed

And for Add a element, increase Freq[A[i]] by one and do: answer = max(answer, freq[A[i]])

Code : http://codepad.org/0D7V5uha

Thank you :) and sorry for my bad english

 
 
 
 
  • Vote: I like it  
  • +11
  • Vote: I do not like it  

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by UmCaraLegal (previous revision, new revision, compare).

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Is there an online way faster than N log^2 N? I couldn't find one.

»
2 months ago, # |
  Vote: I like it +89 Vote: I do not like it

It's strongly believed that it is impossible to do so it in even offline. There is a reduction from multiplication of two binary matrices of size to this problem, and the best known matrix multiplication algorithm at the moment is O(n2.37...). This yields a lower bound for this problem, and if you solve it in quasi-linear time it would be a breakthrough whose significance is comparable with solving P vs NP.

By the way, the name for the problem is "finding mode on a subsegment".

P.S. Downvoted for "sorry for bad English" part. C'mon, folks, stop adding it to each and every blogpost!

»
2 months ago, # |
Rev. 2   Vote: I like it +1 Vote: I do not like it

It can be solved online in per query :)

  • »
    »
    2 months ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    GreenGrape Could you explain this solution ? :D

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Let's split the array into blocks of size A. For each possible range of (some block start, some block end) compute three arrays: frequency of each number, the amount of numbers that give such frequency and one more (I will talk about it later). This will take time and memory.

      Now to obtain all existing frequences for an [L..R] segment you have to find the largest range that you've already computed the answer for and stretch it to the left and to the right. This will take O(A) for both ends.

      But this is not enough because to answer the "most frequent" query you have to iterate over the entire frequences array which takes O(N) time. Try to guess what should be done to reduce the complexity to with some additional array which I mentioned in the beginning :)

      Talking about A, the optimal choise would be .

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    It can be solved online in time per query and linear memory, though it is rather complicated.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it