SNTEMPLE - Editorial

editorial
, , , , , ,
10

@pkacprzak Can you please explain why we have to perform s−m⋅(m+1)−m operations? How did that factor came?

11

@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
12

Yup me tooo y s-m.m+1-m

13

@meooow Can you please elaborate your solution approach? , I am new to this CP field , please bear with me

14

@chari407

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²

15

@pkacprzak

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

16

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??

17

@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.

18

can someone please explain the L and R boolean array part??

19

@pkacprzak can’t able to open the editorials…“Access denied error”

20

Yup. O(N) solution.

21

Nice, the same idea as mine, but with better complexity avoiding binsearch at all

3 Likes
22

Don’t worry, they’ll be added soon. I don’t have access to add them by myself.

23

Thanks mate.

24

@genius007 , bhambhu on fire.

1 Like
25

How are we finding m using binary search ? Please explain ?

26

it can take such inputs

28

Great !!!

29

Can you explain why you subtracted (minLength)*(minLength) from totalSum?
What made you reach this conclusion?

30

I am not sure if I am missing something but where is it given that in the problem statement or constraints that the input will have only one peak? The solutions explained are based on this assumptions if I am not wrong.

For example if we take an input such as -
1 2 1 4 3 2 1
then the defined solution gives wrong answer.