TEMPLELA - Editorial

editorial
, , , , ,
1

PROBLEM LINK:

Contest

Practice

Author: Praveen Dhinwa

Primary Tester: Hasan Jaddouh

Editorialist: Aulene De

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Given an array A, check if it is valid based on the following conditions (taken directly from the problem statement) —

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

  2. Hi1 = 1

  3. The heights keep
    increasing by exactly 1, as you move
    from the leftmost part, to the
    centre part.

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

QUICK EXPLANATION:

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.

EXPLANATION:

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.

SOLUTIONS:

Editorialist’s solution - https://pastebin.com/rHJK1fTG

2

#include<stdio.h>
int main(){
int t;
scanf("%d",&t);
while(t–){
int n,j;
scanf("%d",&n);
int a[n],i;
for(i=0;i<n;i++){
scanf("%d",&a[i]);
}
if(n%2==0 || a[0]!=1||a[n-1]!=1){
printf(“no\n”);
}
else{
j=1;
for(i=0;i<n/2;i++){
if(a[i]==j){
j++;
}
else{
break;
}

				}
				j=j-1;
				for(i=n/2+1;i<n;i++){
					if(a[i]==j){
						j--;
					}
					else{
						break;
					}
					
				}
				if(i==n)
				printf("yes\n");
				else
				printf("no\n");
			}
}
return 0;

}

3

#include<stdio.h>
#include<conio.h>
int main()
{
int n,i,j=0,k,c,b[1000],l=0,count=0,a,q=0,r,w,d;
scanf("%d",&n);
for(i=0;i<n;i++)
{
count=0;
scanf("%d",&a);
for(j=0;j<a;j++)
{
scanf("%d",&b[j]);

	}
	


for(l=0;l<a/2;l++)
{
	
	if(b[l]==l+1)
	{
	
	count++;
	}
	
	}

for(w=((a/2));w<a-1;w++)
{
	

	if(b[w]-b[w+1]==1)
	{
		count++;
	}


}
if(count==a-1)
{
	printf("yes");

}
else
printf("no");

}

}

4

#include<stdio.h>
int main()
{
int s,t;
scanf("%d",&s);
for(t=1;t<=s;t++)
{
int h,i,flag=0,b[h];
scanf("%d",&h);
for(i=0;i<h;i++)
scanf("%d",&a[i]);
if(h%2==0)
{
flag=1;
break;
}
else
{
for(i=1;i<=h;i++)
{
int a;
a=(h/2)+1;
if(i<=a)
{
if(a[i]==i+1)
continue;
else
{
flag=1;
break;
}
}
else
{
if(a[i]==h-i)
continue;
else
{
flag=1;
break;
}
}
}
if(flag==1)
printf(“no\n”);
else
printf(“yes\n”);
}
}
return 0;
}

5

for odd number your have to print(“no”)
sequence should start from 1 .2 .3 4 5…n//2…n//2+1…n//2 …5 …4 3… 1
let p = n//2
sumation of first first p numbers should be = (p*(p+1))//2
sequence on both side is same so sumation becomes =(p*(p+1))
so value of array at (p + 1) position is p + 1
total sum of array is p*(p+1) + p+1 = (p+1)(p+1)
if sum of the given array is same as (p+1)(p+1) print yes else print n0