daw_9's blog

Number of elements whose frequency is 1.
By daw_9, 11 years ago, In English

Given a sequence of N non-negative integers a[1..N], and two indices (l, r) then f(l, r) is the number of elements in a[l..r] whose frequency in [l, r] is 1.

How would you find the maximum value of this function (faster than O(N2)), ie. compute max(f(l, r)) for all l ≤ r ?

Example. If a[] = { 1, 1, 2, 5, 6, 5, 4, 3 }, then some values of f are f(1, 3) = 1 (2 is the only number in a[1..3] that appears just once), f(3, 5) = 3, f(4, 6) = 1, f(1, 8) = 4. In this particular case the maximum value that f may achieve is 4.

Regards.

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

»
11 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Make a new array next[], where next[i] is the index of a value A[i] which occurs after ith position. Thus, A[i] = A[next[i]] for each i.

Then it amounts to finding number of elements in a range larger than some value of X. And this problem is solvable using Fenwick but im not sure how : [

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Well the latter problem is also easy if queries are provided offline: you sort queries by X and then step-by-step add 1 on positions for every possible values from 1 to X_1 then X_2 to X_3 and so on.

    → Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Could you provide a concrete example of how the problem translates using the next array ?

    Thanks.

    → Reply
    • »
      »
      »
      11 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Suppose you have an arrar arr with containing the values (N is the size of the array), you have another arrar id with same length, this id array is an identity array, that is: id[0] = 0, id[1] = 1, id[2] = 2 ... id[N-1] = N-1 - sort arr and id by the order of values in arr and breaking ties with id, that is:

      arr = { 1, 4, 2, 2, 7, 4, 1 },
id  = { 0, 1, 2, 3, 4, 5, 6 }

      affter sort: ~~~~~ arr = { 1, 1, 2, 2, 4, 4, 7 } id = { 0, 6, 2, 3, 1, 5, 4 } ~~~~~

      define array next of size N and fill with the index of the next value of i, -1 it have not a next equal value.

      fill( next, -1 )
for i = 0; i < N-1; i++
   if arr[i] == arr[i + 1]
      next[ id[i] ] = id[ id[i + 1] ]

      Affter that you'll have this:

      next = { 6, 5, 3, -1, -1, -1, -1 }

      next[i] is an index for the original array.

      → Reply
      • »
        »
        »
        »
        11 years ago, # ^ |
        ← Rev. 2   Vote: I like it 0 Vote: I do not like it

        Thanks for your reply. But my question was not how to compute the next[] array, but rather, given next[] what would be the new problem we are trying to solve ? Originally the problem is to maximize the function f(l,r) (over all possible l,r).

        → Reply
        • »
          »
          »
          »
          »
          11 years ago, # ^ |
          ← Rev. 2   Vote: I like it 0 Vote: I do not like it

          count the number of values larger than r in the range of (l,r) for each query.

          BTW, give a link to the problem and I will prolly solve the problem and paste the code.

          → Reply
          • »
            »
            »
            »
            »
            »
            11 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            There are no queries involved in this problem.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              11 years ago, # ^ |
                Vote: I like it -8 Vote: I do not like it

              Doh, misunderstood at first. But wait a minute you assume you know O(N*N) solution?

              → Reply
»
11 years ago, # |
  Vote: I like it +8 Vote: I do not like it

What about a segment tree where each segment [l;r] keeps count of elements in interval. which are valued one?

→ Reply
»
11 years ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

O(n*log(n)) solution(sorry for my bad English)
1. Simple way to calculate f(1,i):
Let's make an array A with 1 on places of first occurrence of every number, and -1 on second occurrence of every number, other elements equal 0. Now partial sum[1..i] is equal to f(1,i). Also we can move left border from 1 to 2, by changing only 2 elements of this array — second and third occurrence of first number. We can also move left border to 3, 4, ... in the same way.
2. Build segment tree of the array of partial sums. We need to perform following operations: increasing all elements on segment and calculating maximum on segment. To move left border we need to increase 2 suffixes of the array. For each left border l maximum on current suffix of the array is equal to max(f(l, i)), l<=i<=n.

→ Reply
  • »
    »
    11 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks for such a neat solution.

    → Reply
»
11 years ago, # |
  Vote: I like it +7 Vote: I do not like it

Where can I submit this problem? Can you give a link?

→ Reply