HackwithInfy 2021 May 9

So the Question was given an array arr(of size n (1<=n=<10^5) )with values (0<=arr[i]<=10^9).
We had to find the sum of the maximum of each subarray multiplied by the length of that particular subarray and we had to do it for all possible subarrays.(modulo 10^9 + 7 as the total value would be large)
for ex

length 1= {1},{2},{3} sum+= (1x1)+(2x1)+(3x1)
length 2={1,2},{2,3} sum+=(2x2)+(3x2)
length 3={1,2,3} sum+=(3x3)
Approach :-
So i thought of using a deque to find max elements for all the subarrays for size k (O(n)) and did this for all k ranging from(1<=k<=n).
Now i only got 2 AC
while the other had runtime error(probably tle)

So is there any suggestion on how to do it in a cheaper way.?

Use prefix sum to retrieve the sum of any subarray in O(1) time.

I think I have a solution. The idea is to determine the contribution of each element to the final answer.

Note that we can get the range [l, r] for which a given element holds the maximum value using a stack in O(n) time (the idea is based on this). Now, the task which remains is to get the lengths of the subarrays.

Let’s denote the current element’s position in the array by pos and its value by val.

We have to determine the lengths of the subarrays [i, j] in the range [l, r] such that l <= i, j <= r and i <= pos <= j. Let’s denote x as the length [l, pos] and y as the length [pos, r].

Then, we can say that we need the sum of the lengths of the subarrays [pos, pos], [pos, pos+1], ..., [pos, r], [pos -1, pos], [pos -1, pos + 1], ..., [pos - 1, r], [pos - 2, pos], ..., [l, r].

Observe the pattern here… This sum can be expressed as (\sum_{i=1}^{x}i ) \times y + (\sum_{i=1}^{y-1}i ) \times x.
So, the contribution for the current element becomes val \times ((\sum_{i=1}^{x}i ) \times y + (\sum_{i=1}^{y-1}i ) \times x). Note that this value can be calculated in O(1). The final answer can be calculated by simply summing the contribution of each element. So, the final complexity is O(n).

arr = [1, 2, 3]

for 1 → x = 1 and y = 1 so its contribution = 1 \times ((\sum_{i=1}^{1}i ) \times 1 + (\sum_{i=0}^{0}i ) \times 1) = 1

for 2 → x = 2 and y = 1 so its contribution = 2 \times ((\sum_{i=1}^{2}i ) \times 1 + (\sum_{i=0}^{0}i ) \times 2) = 6

for 3 → x = 3 and y = 1 so its contribution = 3 \times ((\sum_{i=1}^{3}i ) \times 1 + (\sum_{i=0}^{0}i ) \times 3) = 18

So, the final answer = 1 + 6 + 18 = 25



Man this was neat .:+1:

1 Like

Was HackwithInfy problems hard, or I am the only one who is not able to solve even a single problem.

I want to know how you get that solution in your mind. I don’t even move pen in the notebook.

1 Like

Most of the problems were rated 1800+ on codeforces. So, don’t worry. It was hard.

Won’t the time complexity be O(N^2) , O(N) for calculating the maximum in each range , just consider the following example
[4,3,2,1,5] , Here 5 is the next greater element for each no. , So after calculating value that 5 is contributing we will have to again calculate it for the subarray of indices [1,4] which will again take O(N) . I think it is better to use segment tree or sparse table to find the maximum number in a range , as then the Time Complexity would be O(N Log N)

I have updated my comment by providing a link to the code.
Maybe that can help… :sweat_smile:

Okkk Thanks now I get it .

Will this code pass the constraint ? Link

No because you are checking all the N^2 arrays

hey can u tell me what was wrong in my code?
i tried test cases and it even worked for 15% but idk wht’s wrong with this…

using namespace std;

int main()
long long int n,temp=0,sum=0,var2=0,MOD=1000000007,var3=0;
long long int arr[n+1],var=1;
for(int i=1;i<=n;i++){
for(int i=1;i<=n;i++){
for(int j=0;j<n;j++){


1 Like

Ah…I’ll suggest you to reconsider the logic you have applied. For a start, consider this array - [1, 3, 2] and understand why your code fails for it. I hope this helps.

wht will be the output of your array [1,3,2] ?

It would be (1 x 1 + 3 x (1 + 2 + 2 + 3) + 2 * 1 =) 27.

Can you share the links to the problems…