**Problem Discussed Today:**

**Editorial**

**Idea:**

Consider the initial moment of time. Note that the array is r=[1,2,…,n], count=[1,1,…,1]. So the generator will choose a random position from the entire array – let it be the position i1. In the next step, r=[1,2,…i1+1,i1+1,i+2,…,n], count=[1,1,…,0,2,1,…,1]. That is, now there is only one maximum and it is reached at the position i1+1. Thus, we will fill in the entire suffix starting at position i1: a=[×,…,×,1,…,i1]. After this, this procedure will be repeated for some i2 (1≤i2<i1) and the array will become a=[×,…,×,i1+1,…,i1+i2,1,…,i1] . That is, we need to check that the array consists of several ascending sequences.

Solution Link: Solution

**Idea:**

Let's iterate over all elements of c from left to right. For simplicity, we consider only "greater" summands. Because our sum (ci+cj) must be greater than 0, then at least one of these summands will be positive. So, if ci≤0, just skip it. Now ci>0 and we need to calculate the number of such j that ci+cj>0 and j<i. It means that each cj≥−ci+1 (for some j<i) will be okay. Such leftmost position j can be found with std::lower_bound or binary search. Then add the value i−j to the answer and consider the next element.

Solution Link: Solution

If there is

**an error**in the above-discussed solutions, then please feel free to drop in the comment section**Thank You for Reading**
## Comments

## Post a Comment