PROBLEM A-OLIVER
It will look something like
1 2 2 3 3 3…r r r(r times) r+1 r+1 (some x times)
so 1+2+3+…r<=n
as r will be less than sqrt(1e9) you can linearly search it
Answer will be equal to 11+22+…+ rr+x(r+1)=r*(r+1)(2r+1)/6+x*(r+1)
x= n-r*(r+1)/2
Solution
PROBLEM B- MONEY HEIST
I solved it using priority queue .
We can create a priority_queue<pair<int,int>>pq to store the pair (a[i],-i)
where i is the index of the element.
We will also need an array to count the number of times we have used current index (cnt[n]).
each day we will take the front element of priority_queue as it will have maximum element with minimum index and we will take ceil(a[i]/3) and add it to the answer and subtract it from a[i] and also remove it from pq.
increase cnt[i] by 1.
Now reinsert the element into the priority queue if and only if it is nonzero and its cnt[i]<b.
Stop if size of pq becomes zero.
PROBLEM C- NOBITA AND BOXES
All placed cuboids should have their faces of similar color parallel to each other and all faces should be parallel to cube faces means
See according to L c/L cubes can be used parallel to that side, according to B c/B can be put parallel to that side and according to H c/H can be put parallel to that side.
if which means at most c * c * c/(l * b * h) can be placed and this should be greater or equal to n so we is c should ceil(pow(n * l * b * h ,1.0/3)).
https://www.codechef.com/viewsolution/42141229
PROBLEM D- Good Pairs
We can make some observation
CASE 1 i<j
Let’s say i,j is a good pair and a[i] > a[j] , Will (i,j+1) be a good pair? No it will not be because a[j]<a[i]
so for any i there can be at most 1 good pair (i, index of the first smaller number than a[i] to the right of i)
CASE 2 i>j
Let’s say i,j is a good pair and a[i]>a[j], Will (j-1,i) be a good pair? No it will not be a good pair because a[j]<a[i].
so for any i there can be at most 1 good pair (i,index of the first smaller number than a[i] to the left of i)
We have reduced our problem from some weird statements to finding the index of first smaller a[j] to the left and right. You can find it using the concept of monotonic stack.
PROBLEM E- Special Permutation
This is a Range Query problem.
For some i in [1,n], we can consider only those subarrays that will have i at the start and apply it once for the given array and once for the reversed array.
Let say a[i]=a[j] for some i,k i<k
Let
x= maximum among the next indexes of all elements less than a[i]
y= minimum among the next indexes of all elements greater than a[i]
j=next index of a[i]
if(x<j && y>x)
Then we have a special permutation for a[i].
x and y can be found using segment tree.