Codeforces will not be available in the period 01:00-05:00 May, 30 (MSK, UTC +3) because of maintenance. ×

practice_practice's blog

By practice_practice, history, 2 months 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

»
2 months 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).

»
2 months 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.
  • »
    »
    2 months 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

    • »
      »
      »
      2 months 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.

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

        I have solved all the questions . And it was not this -(B[cur_index]-B[cur_index-1])*(B[cur_index+2]-B[cur_index+1]) .

        Rather , it is this — (B[cur_index]-B[cur_index-1])*(n-B[cur_index+1]+1) I can't thank you :3 But thank you may be if you suggest me more similar problems :D

»
5 weeks 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]).