_kite's blog

A combinatorics Help
By _kite, history, 5 years ago, In English

An array of n elements is given. In this array, How many intervals [l,r] contain at least two 2 ? How many intervals [l,r] contain at least one 4? How many intervals contain two 2 and one 4 together? Note that, [1,1],[2,2] these intervals are also valid. Each of them contains 1 element.

Size of n is 1e5.

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

Comments Comments (5)
| Write comment?
»
5 years ago, # |
← Rev. 4   Vote: I like it +8 Vote: I do not like it

Hint: For the first problem, For each 2, count the number of intervals that contain it assuming that it is the rightmost 2 in that interval.

The same trick applies to the rest of the problems (with small variations).

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

How many intervals [l,r] contain at least two 2 ?

-> Store the indices for all '2' that appear in the array in increasing order.
-> Now iterate over this new array (lets call this new array B and original array as A). For each index of the new array B calculate the number of segments in the original array A which have A[B[cur_index]] as the leftmost 2. (This is simply (B[cur_index]-B[cur_index-1])*(B[cur_index+2]-B[cur_index+1]) if cur_index-1 and cur_index+2 are defined. You have to take care of end points)
Similarly go for other questions.
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I have solved 1st two questions. But same approach is not working for 3rd one

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

      The idea is similar.

      B will now have indices of all 4s and 2s. Just think about it.

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

You can use binary search.Make an array,pre2[],pre4[],to denote the # of 2's and 4's before a index.For problem 1,find the largest index j for each i that pre2[j-1]+2<=pre2[i].Do it for the other tasks,as well.For problem 3,find max(pre2[j-1]+2<=pre2[i],pre4[j-1]+1<=pre4[i]).

→ Reply