There is some error with the links, please fix them.
Not able to access editorial
access denied for links of the solution
we can also do it in O(n) by maintaining left and right array and then calculating the answer.
solution link
2 Likes
Here is a simple \mathcal{O}(n) solution. As mentioned in the editorial, the problem can be restated as simply finding the largest temple possible. Imagine breaking the temple into two triangles, with the centre overlapping. For example, temple [1, 2, 3, 2, 1] becomes triangle [1, 2, 3] and [3, 2, 1]. Now, for each index i calculate the maximum height of a left-triangle whose highest point is i. Let this be L[i], then L[i+1] is simply min(L[i]+1, h[i+1]). Hence L[i] can be computed for all indices in linear time. Do the same for the right-triangles, using another array R, where R[i-1] will similarly be min(R[i]+1, h[i-1]). Then for each index i, the largest temple that has its peak at i is min(L[i], R[i]). The maximum of this value among all indices will give you the largest temple possible in whole array. The number of operations needed to obtain this temple is just the total number of blocks in the temple subtracted from the sum of the array h.
Here is my
[1] for reference.
[1]: https://www.codechef.com/viewsolution/13885246
26 Likes
Can someone explain o(n) sol in detail with comments
Would be a great help
Appreciate it.
Thanks in advance.
Hey we(my team) came up with a very easy solution also of complexity O(n),
What we did first checked the first and last element of h[n] should be equal to zero or one only, in case it is larger than it , make h[i] equal to 1, then start the iteration from second to last element while taking input and in case h[i]>h[i-1]+1 => h[i]=h[i-1]+1 because in case this strip is used its length must be h[i-1]+1 or less than it, otherwise h[i]= original input , just continue this process to whole input but meanwhile sum up all the original input in a variable S which is total number of blocks in mountain .
But process doesn’t ends there do this in same manner in reverse direction, but first do the process for h[n-1](last element ) same as we did for h[0] then do the whole process in opposite direction i.e. iterate the array h[N] in opposite direction if h[i]>h[i+1]+1, then again h[i]=h[i+1]+1.
What all this process will do that it will trim the mountain in which each peak leads to the formation of a mountain i.e. all the possible mountains could be found their and each block could be used to create a mountain.
Then find the highest peak height which also could be find while second iteration or separately.
Then find the number of blocks in this mountain with that highest height i.e. (maximum height)^2 =>(more clearly ((m.h.+1) * m.h)/2 + ((m.h.-1) * m.h)/2 ).
Now just subtract it from that sum S .
Here is my solution ++> CodeChef: Practical coding for everyone click heret
Remove the comments in this code and run this in codechef Id you can easily understand the whole magic.
@pkacprzak Can you please explain why we have to perform s−m⋅(m+1)−m operations? How did that factor came?
@chari407 sum of magic(m)= m * m ,lets see how , sum of [1…m]=m * (m+1)/2 ,as sum[magic(m)]=2 * sum[i…m]-m (you can see m gets added twice in 2 * sum[1…m] ,so a subtaction of m is needed that’s why m is substracted)
so sum[magic(m)]=m * m+ m-m=m * m so required operations= s - m * m;
1 Like
Yup me tooo y s-m.m+1-m
@meooow Can you please elaborate your solution approach? , I am new to this CP field , please bear with me
The sum of heights of the left side of a pyramid of height m is m(m-1)/2 and its same for the right portion. So they sum up to make m(m-1). Then just add the top most block to get m(m-1)+m=m²
Now if we had the sum of previous heights s, and final sum height m<=s, number of operations is definitely s-m²
We have to perform s−m⋅(m+1)−m=s−m2s−m⋅(m+1)−m=s−m2 operations
I think it should be s-m(m-1)-m
Does this Solution takes the following input? - 1 2 5 5 1 - 1 2 5 4 7 - If not, why don’t they explicitly mention that there will be one largest number in the given array??
@chari407 for the order of m, we need to have 1, 2, 3, 4 …m and then m-1, m-2, m-3, m-4, …3, 2, 1
for 1 to m, (m*(m+1))/2 and for m -1 to 1 ((m-1)*m)/2 and u need to add both to get the answer which is m^2.
can someone please explain the L and R boolean array part??
Yup. O(N) solution.
Nice, the same idea as mine, but with better complexity avoiding binsearch at all
3 Likes