How do I do this question?

Click here for problem statement

Not able to understand the editorial.

Thanks in advance.

How do I do this question?

Click here for problem statement

Not able to understand the editorial.

Thanks in advance.

1 Like

For any position i in the array, for what length â€świndowâ€ť can that number act as strength ?

for example, the array is

`3 1 4 2 3 0`

Clearly, the 2 at 3rd position (0th based indexing) will act as strength for the windows of length 1,2 and 3 only. This is because,if you expand the window on either side, we have the number 1 ( <2 ) and number 0 ( <2) .

So, for each index i we need to find the largest index j < i such that a[j] < a[i]. Letâ€™s store it in l[i].

For each index i, we need to find the largest index j > i such that a[j] < a[i]. Letâ€™s store it in r[i].

Clearly, the maximum window which you can get is from l[i] + 1 to r[i] - 1, which has a length of r[i] - l[i] - 1. Therefore, each element can act as strength for window size from 1 to r[i] - l[i] - 1.

You can calculate arrays l and r using a stack and then solve the problem.

http://codeforces.com/contest/547/submission/19434836

3 Likes

There is one **very simple method**. You can easily find the answer for x = 1. Initialize the array, a[200005][200005]. Therefore, a[1][1] = a1, a[1][2] = a2, â€¦, a[1][i] = ai, â€¦, a[1][n] = an. In the loop you can store maximum strength in tempmax while assigning values to the array. print - tempmax

tempmax = 0

Now for x = 2. a[2][2] = min(a[1][1], a[1][2]), a[2][3] = min(a[1][2], a[1][3]), â€¦, a[2][i] = min(a[1][i-1], a[1][i]), â€¦, a[2][n] = min(a[1][n-1], a[1][n]). print - tempmax

â€¦

tempmax = 0

For x = i. a[x][x] = min(a[x-1][x-1], a[x-1][x]), a[x][x+1] = min(a[x-1][x], a[x-1][x+1]), â€¦, a[x][x+i] = min(a[x-1][x+i-1], a[x-1][x+i]), â€¦, a[x][n] = min(a[x-1][n-1], a[x-1][n]). print - tempmax

â€¦

tempmax = 0

For x = n a[n][n] = min(a[n-1][n-1], a[n-1][n]) if(a[n][n] > tempmax) tempmax = a[n][n]. printf - tempmax

Now comes the question that logic is perfectly fine, but **we canâ€™t declare such a huge array**. Again, there is a simple solution for that. The **method to implement it using 1D array** is as follows:

declare array a[200005]

tempmax = 0;

x = 1:

for(i=n to 1){

a[i] = ai;

if(a[i]>tempmax) tempmax = a[i];

}

printf("%d ", tempmax);

tempmax = 0;

x = 2:

for(i=n to 2){

a[i] = min(a[i], a[i-1]);

if(a[i]>tempmax) tempmax = a[i];

}

printf("%d ", tempmax);

â€¦

tempmax = 0;

x = j:

for(i=n to j){

a[i] = min(a[i], a[i-1]);

if(a[i]>tempmax) tempmax = a[i];

}

printf("%d ", tempmax);

â€¦

tempmax = 0;

x = n:

for(i=n to n){

a[i] = min(a[i], a[i-1]);

if(a[i]>tempmax) tempmax = a[i];

}

printf("%d ", tempmax);

Now I guess you got the notion about how to approach the question. The **final code** which you can implement is as follows:

//min function

int n, a[200005], tempmax, i, j;

//read the inputs

tempmax = 0;

for(i=1;i<=n;i++){

```
a[i] = ai;
if(a[i] > tempmax)
tempmax = a[i];
```

}

printf("%d ", tempmax);

for(j=2;j<=n;j++){

```
tempmax=0;
for(i=n;i>=j;i--){
a[i] = min(a[i-1], a[i]);
if(a[i] > tempmax)
tempmax = a[i];
}
printf("tempmax ");
```

}

But this method isnâ€™t sufficient as it will give TLE. Please implement it using BIT.