Author: Praveen Dhinwa
Primary Tester: Hasan Jaddouh
Editorialist: Aulene De
Given an array A, check if it is valid based on the following conditions (taken directly from the problem statement) —
There should be an unique ‘centre’
part. This is where the actual
temple will be built. By centre, we
mean that there should be an equal
number of parts to the left of this
part, and to the right of this part.
Hi1 = 1
The heights keep
increasing by exactly 1, as you move
from the leftmost part, to the
The heights should
keep decreasing by exactly 1, as you
move from the centre part to the
rightmost part. Note that this means
that HiNi should also be 1.
Given an array A consisting of N numbers, check if the array increases from 1 until n/2+1 (with increments of 1) and then decreases to 1 (in decrements of 1). If this is false anywhere, the array is invalid. Otherwise, the answer is valid.
Let’s break down each condition one-by-one. The first condition states that we must have a unique ‘centre’ part, where the number of elements to the left of this part are equal to those on the right.
Hmm? See, here at CodeChef, we pride ourselves into making simple stuff sound scary, because we’re cool like that. What is a unique ‘centre’ part in a number like, say, 2?
There is no unique centre part. What about 3? Well, we could choose to build our temple at point 2, thus having equal elements to the left and the right. What about 4? No dice. We don’t have a unique ‘centre’ part again.
In simple terms, if N is even, we don’t have a point where the number of elements to the left is equal to those on the right. However, if N is odd, we do have a point where we can build our temple! Now, what would this point be?
The point where we’ll be building our temple will be the upper bound of N/2 or simply, N/2+1.
Alright: second condition. A_1 = 1. Okay, cool. Nothing to see here, move along.
Let’s look at the third and fourth condition now: our heights have to increase by exactly 1 until we hit the point where we are building our temple. After that, they have to decrement by exactly 1 until H[N] is also equal to 1.
So we start from the left. We traverse the mountain that is the Great Wall of Array A, checking if every element is 1 greater than the previous, until we reach N/2+1. After that, we move down this mountain, checking if every single number is 1 lower than the previous. If, at any point, this is false, our answer will be invalid.
Editorialist’s solution - https://pastebin.com/rHJK1fTG