FAKE BABA Ai ,A((i1))subscript to and put equal to and increment the counter by . Repeat the process until we reach the start of the array. Note: For the answer to be a valid count, our condition that if Ai is not equal to i, it will be present either in position i1 or i2 holds for all the elements because at every step we reorganize the array and make Ai equal to i for i<=i<=n. So, if we are at index i, we are sure that Aj is equal to j fori<j<=n . Time complexity:O(n). CCS BOT https://www.codechef.com/COTY2019/problems/COTY04 The pseudocode can be restated as follows. We start at position 1 with energy 0. For each position i, we have to choose one of the following two options, then move to i+1 by reducing 1 unit of energy. 1. Gain V[i] amount of value. 2. Set the current energy to P[i]. Note that: 1. If the current energy is 0, we will be dead, since the world will be killed. :P 2. However, it is allowed to have 0 energy when reaching positionn . This is because the pseduocode tells us when i=n, we can collect V[n] and then we are done. The second option is crucial, where it simply means we can discard V[i] and extend our life to position P[i]+i instead. Based on these facts, it is easy to design a DP solution. Let f[i] be the minimum amount of Vvalues we have to sacrifice in order to reach position i without killing the world. Here, we do not consider V[i] when calculating f[i]. Then, it is easy to have the following recurrence. f[i]= { 0 if i=1, min1<=j<I and P([j]+j>=i) (f[j]+V[j]) if i>1. } The final answer is ∑(i=1 to n) V[i]  f[n]. However, the naive way to compute f[n] requires O(n^2) time, which is too slow for n=5*10^5 . Therefore, we need to optimize it by using some advanced data structure. There are at least two possible approaches. By using a Segment Tree Set f[i]=∞ , for all i>1 . We then try to compute f[1] ,f[2] ,…….f[n] one by one. Once the value of f[i] is determined, we try to use f[i] to update the interval f[i+1]…….f[ i +P[i]], i.e., set f[j] = f[i] if f[j] > f[i] , for all j € [i+1 ,i+P[i]]. Each update operation can be done efficiently, in O(log n) time, within a segment tree with lazy tags. Thus, we can compute f[n] in O( n log n) time. By using an Augmented Balanced Binary Search Tree Define A[i] =P[i] + i. Then, the condition P[j] +j>=i becomes A[j]>=i . We can build a balanced binary search tree, where the keys are A[i] 's. For each node A[i] , we also store the current f[i] , and the minimum f[.] in the subtree rooted at A[i] . Now, in order to compute f[i] , we just need to find the minimum f value of those nodes who have key values >=i . If we have a balanced binary search, this operation can also be done in O(log n) time. After f[i] is determined, we need to update the node A[i] in the tree as well as all the augmented information along the path from A[i] up to the root. Since the tree is balanced, this is yet another O(log n) operation. So, by using an augmented balanced BST, we also get an O(n log n)solution. Now the remaining question is that writing a balanced binary search tree is really painful. Luckily, we know all A[i] 's before hand, therefore, we can first sort the array A , then recursively build a balanced tree. Hackathon First, let's define the power of subsequence [L,R] as P(L,R), and S(L,R) as the sum of the elements between L and R. Then, obviously, P(L,R)=2(RL+1)S(L,R). Note that S(L,R) can be calculated in O(1) time using prefix sums. So,P(L,R) can be calculated in O(1) time, too. Also let's notice that P(L1,R)>=P(L,R) and P(L,R+1)>=P(L,R). Let's sort pi(i in the subscript) in nondecreasing order and iterate over this list. Initially, we disallow to take all the numbers. When we consider pi(i in the subscript), we want to allow taking it. Then, we find the lengthmaximum consucutive subsequence of allowed elements that contains pi(i in the subscript). This can be done, for example, using DSU (disjoint set of unions) and merging i with i1 if pi(i in the subscript) is allowed, and with i+1 if p(i+1)(i+1 in the subscript)is allowed. So, now we have a subsequence [L,R] such that L<=i<=R and for all j(L<=j<=R) pj(j in the subscript)<=pi(i in the subscript) , where L is the minimum possible and R is the maximum possible to hold the previous constraints. Let's add a triple (P(L,R),L,pi(i in the subscript)) to the list of events. These events will help us to answer the queries. So, let's get back to the queries. Suppose we have a query (l,r,x). At first, we will check the bounds. Using binary search, we can find the leftmost Rl(l in the subscript) such that P(l,Rl)>=x. Note that if Rl(l in the subscript), then the answer is 1 and we can skip this query in future. Now we can update the answer for this query with max(pl(l in the subscript),.....,p(rl(l in the subscript) in the subscript), which can be found using a segment tree. Also, we can find the rightmost Lr(r in the subscript)such that P(Lr(r in the subscript),r)>=x, and update the answer for this query with max(pLr(Lr(r in the subscript) in the subscript),.....,pr(rin the subscript). Then, we want to find a subsequence [l',r'] such that l<=l'<=r'<=r,P(l,r)>=x and max(pl'(l' in the subscript),.....,pr'(r' in the subscript)), is the minimum possible. We can notice that l'<=Lr(r in the subscript), because otherwise x<=P(l',r')<=P(l',r), and Lr(r in the subscript) is not the rightmost position such that P(Lr(r in the subscript),r)>=x. So,l<=l'<=Lr(r in the subscript). Now we find an event (P(L,R),L,pi(i in the subscript)) such that P(L,R)>=x and l<=l'<=Lr(r in the subscript) and pi(i in the subscript) is minumum possible. Then, we update the answer for this query with hi(i in the subscript). It's obvious that if R<=r, then this operation is correct. Otherwise, this operation is correct, because ,max(pL(L in the subscript),.....,pR(R in the subscript))>=max(pL(L in the subscript),.....,pr(r in the subscript))>=max(pLr(Lr(r in the subscript) in the subscript),.....,pr(r in the subscript)), so the answer is not improved. This can be implemented using scanline technique. We sort all the queries in nonincreasing order of xi(i in the subscript), and also sort the events in nondecreasing order of P(L,R). When we handle the ith query, we allow using the events such that P(L,R)>=xi(i in the subscript), it's the prefix of the sorted events. Also we keep a segment tree T, such that TL(L in the subscript) is the best event with such left position L. Initially,{TL(L in the subscript)=infinity} for all L. When we add an event (P(L,R),L,pj(j in the subscript)), we just do the following: TL(L in the subscript)=min(TL(L in the subscript),pj(j in the subscript)). When we answer the query, we update its answer with min(Tl(l in the subscript),......,TLr(Lr(r in the subscript) in the subscript). Sum Of Products Now, for the purpose of maximizing the value, we can ignore this 1/2 factor. Let's just redefine the value of an array B to be (∑(i=1 to n)Bi)^2  ∑(i=1 to n)Bi^2 and just divide the answer by during printing.
This question is marked "community wiki".
asked 01 Feb, 17:31
