FAKE BABA
Question link
https://www.codechef.com/COTY2019/problems/COTY01
Let’s consider an example for n = 5. Initially, the array was A:[1, 2, 3, 4, 5].
Let’s say after some number of bribes the array became A: [1, 5, 4, 2, 3].
The 5th person moved from it’s initial position to 2nd position. For that, he must have
bribed 3people, which are 2 ,3 and 4. Also,4th person moved from it’s initial position to
3rd position by bribing person 2 and person 3.
So the transformation goes something like this:
[1, 2, 3, 4, 5] -> [1, 2, 3, 5, 4] -> [1, 2, 5, 3, 4] -> [1, 5, 2, 3, 4] -> [1, 5, 2, 4, 3] -> [1, 5, 4, 2, 3]
Observation:
The number of people the ith person (for 1<i<n ) has bribed is equal to the number of people on
the right of that person with a value less than A1 (where array A represents the given array or
final state of the people).
To get to the current position, each person has to bribe all the people who are behind them and
have a smaller number. This is the same as counting inversions of an array.
So, if that number is greater than 2 for any index i we print Too chaotic else print the total sum of
bribes.
Brute Force Approach:
Run two loops, and for every integeri , we find the number of j’s such that Ai>Aj,
where i<=j<=n andi<j<=n .
Time complexity: O() but we can do better.
Optimised (Linear Time) Approach:
We start from the end of the array A. If Ai is not equal to i, where 1<=i<=n then we know that the
last element must have bribed and moved towards the left since it cannot move to the right being
the last element. Also, we know that it will be present either in position i-1 or i-2. This is because
if it is in the position left to i-2, he must have bribed more than 2 people. In that case, we just
print Too chaotic and terminate our program. Else if Ai is equal to A((i-1))subscript just swap the
two elements and increment the counter by 1. Else shift A((i-1))subscript toA((i-2))subscript
Ai ,A((i-1))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 i-1 or i-2 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
Question Link
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.
- Gain V[i] amount of value.
- Set the current energy to P[i].
Note that: - If the current energy is 0, we will be dead, since the world will be killed.
- 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 V-values 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
Question Link
https://www.codechef.com/COTY2019/problems/COTY03
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*(R-L+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(L-1,R)>=P(L,R) and P(L,R+1)>=P(L,R).
Let’s sort pi(i in the subscript) in non-decreasing 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 length-maximum 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 i-1 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 non-increasing order of xi(i in the subscript), and also sort the events in non-decreasing order of P(L,R).
When we handle the i-th 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
Question Link
https://www.codechef.com/COTY2019/problems/COTY05
The first step is to derive a “simple” formula for computing the value of an array B , defined as
∑BiBj ( i=1 ,j=1 , i<j to n)
Here, we require that i<j so that each pair is counted only once. (Also, i=j is disallowed. Why?)
Consider the similar sum:
∑BiBj ( i=1 ,j=1, i>j to n)
It turns out that the two sums above are equal! This is because multiplication is commutative, so it doesn’t matter if we take
the “larger index” first or last.
Thus, we have:
∑BiBj (i,j=1 to n) =∑BiBj ( i,j=1 i<j to n ) + ∑BiBj (I,j=1 i>j to n) +
∑BiBj (i,j=1 i=j to n) + 2∑BiBj (i,j=1 i<j to n) +∑Bi^2 (i=1 to n)
On the other hand, we also have:
∑BiBj (i,j=1 to n ) =∑(i=1 to n)∑(j=1 to n)BiBj
=∑(i=1 to n)Bi ∑(j=1 to n) Bj
=(∑(i=1 to n)Bi)(∑(j=1 to n)Bj)
=(∑(i=1 to n)Bi)^2
Equating the two and solving for the “value”, we get:
2∑(I,j=1 i<j to n)BiBj + ∑ (i=1 to n)Bi^2 = (∑(i=1 to n) Bi)^2
∑(I,j=1 i<j ) BiBj=1/2((∑(i=1 to n)Bi)^2 - ∑(i=1 to n)Bi^2)
Thus, the value of an array is simply half of the square of its sum of its elements minus the sum of the squares of its
elements.
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.