Editorial for Road to Zero, Nastya and Strange Generator, Pair of Topics

Problem Discussed Today: 
  1. Road to Zero (1342A)
  2. Nastya and Strange Generator ( 1341C )
  3. Pair of Topics ( 1324 )
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 rewrite the inequality from ai+aj>bi+bj to (ai−bi)+(aj−bj)>0. This looks much simpler. Let's build the array c where ci=ai−bi and sort this array. Now our problem is to find the number of pairs i<j such that ci+cj>0.

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