See this
1
10
1 2 3 4 4 1 1 3 1 1
correct output : 12
ur output : 5.
2 Likes
What was the correct approach to solve this problem?
1
5
3 1 7 9 10
Your output:21
Answer:26
Answer is for this final configration: 0 1 2 1 0
2 Likes
this test case :
1
5
2 1 1 1 2
your answer- 3
correct answer - 6
1 Like
make the arrays so they can follow these constrain A[i] < A[i+1] then ( A[i] = A[i+1] + 1 ) and A[i] > A[i+1] then A[i] + 1 = A[i+1] so…after that by simply observation find the answer the maximum height of temple that can be formed after that compute answer in O(1)
2 Likes
This was probably the hardest problem for me, or maybe the second hardest, after consecutive snakes. I saw that many people have solved it but i just couldn’t figure it out. Then it clicked :).
The idea is this:
Go from left to right and try to ‘grow’ the longest possible temple side. For example if the array is [1,3,3,4,5,4…] you can build
[0,1,2,3,4,X…]. This new array tells you for each index, if you build a temple at that index what is the largest left side you can get. For example the 4 in the new array means that if i build an array at that index my temple might look like:
----*
---*
--*
-*
*
I say might, because i am still not sure for the right side.
As you can see i put an ‘X’ in one place in the array. This is because i cant keep increasing that side. This means that the value at that index in the original array is lower than the what it needs to be to grow the previous castle. The largest value for X is the value of the original array -1. So with X resolved, the new array would look like:
[0,1,2,3,4,3…].
Now we countinue counting from 3.
We do the same but going right to left this time to find out for each index, the largest right side of temple possible.
After that we iterate all possible positions for a temple and take the minimum of the left and right sides. That is the size of our temple.
3 Likes
@aditya730: Create left and right arrays,
left[i] = min(left[i-1] +1, arr[i])
right[i] = min(right[i+1]+1, arr[i])
Then find maxtemp => maxtemp = max(maxtemp,min(left[i],right[i]) for all i from 1 to n. Answer is totalsum - (maxt^2)
2 Likes
I am getting right answer for all testcases. Can anyone tell in my cod eany testcase where it fails ?
#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
#define eps 1e-9
#define inf 1e18
#define PI 3.14159265
#define mset(A,num,n); memset(A,num,n);
#define nl cout << endl
const int MOD = 1e9+7;
const int N = 1e6+5;
typedef long long int ll;
ll POWER[65];
void precompute() {
POWER[0]=1;
for(int i=1;i<63;i++) POWER[i]=POWER[i-1]<<1LL;
}
int main()
{
ll T;
cin>>T;
//string str[4],str1[4];
ll cnt;
while(T–)
{
ll n;
cin>>n;
ll A[n];
for (int i=0;i<n;i++)
cin>>A[i];
ll left,right,i,j;
left =0;right =n-1;
i=0;j=n-1;cnt=1;
while(left<right)
{
if(A[i]>=cnt&&A[j]>=cnt)
{
cnt++;
i++;
j--;
//continue;
//cout<<334;
}
else if(A[i]<cnt&&A[j]<cnt)
{
if(A[i]>=A[j])
{
right=j+A[j]-1;
i=left;
j=right;
cnt=1;
}
else
{
left=i-A[i]+1;
i=left;
j=right;
cnt=1;
}
}
else if(A[i]<cnt)
{
left=i-A[i]+1;
i=left;
j=right;
cnt=1;
}
else if(A[j]<cnt)
{
right=j+A[j]-1;
i=left;
j=right;
cnt=1;
}
// cout<<343;
if(i>j)
{
break;
}
}
//cout<<cnt<<endl;
ll sum1=0,sum=0;
sum1=2*((cnt*(cnt-1))/2);
//sum=sum+1;
sum1=sum1-(cnt-1);
for (ll i=0;i<n;i++)
sum=sum+A[i];
//cout<<cnt-1<<endl;//<<sum1<<endl<<sum-sum1<<endl;
cout<<sum-sum1<<endl;
}
}
Could someone explain what is wrong with my code? It passes every test case provided above. Best regards.
https://www.codechef.com/viewsolution/13890268
what will be the answer for
1
10
1 2 3 1 4 4 1 3 1 1
according to me it should be 17
'only possible way is 1 2 1
A[i] + 1 = A[i+1] is it even a valid assignment?or did you mean
A[i+1]= A[i]+1 ?
I am getting a very basic idea of what you are trying to do but the terminology you have used is very confusing.I bet you are very active on Codeforces. Looks very similar to the editorials and comments i’ve seen there .All super human beings there who can understand anything and everything however complex either the answer or solution is 
1 Like
How are you dealing with cases where two temples have same length? Meaning you find two spots where temple can be constructed, both with same maximum side?
@adlitya730 
you made me laugh :). No i do not compete on codeforces and sorry for confusing you.
Have a look at my code, it is pretty clear: CodeChef: Practical coding for everyone
Draw the array on paper and try to simulate what i explained. You will see what i mean.
1 Like
@vijju123 You choose any of the maximal temples to build. The point is to use as many ‘land’ as you can which is the same as deleting the least ‘land’.
add some extra new lines, it might help
i am taking about idea…yes I mean A[i+1] = A[i] + 1
Thanks got it . Marked as accepted
Yeah fixed
Ok will keep in mind .