You are not logged in. Please login at www.codechef.com to post your questions!

×

TEMPLELA - Editorial

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

This question is marked "community wiki".

asked 24 May '17, 17:53

aulene's gravatar image

5★aulene
313
accept rate: 0%

edited 05 Jul '17, 21:46

admin's gravatar image

0★admin ♦♦
19.8k350498541


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;

}

link

answered 27 Sep '18, 10:19

avi14297's gravatar image

2★avi14297
1
accept rate: 0%

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");

}

}

link

answered 05 Oct '18, 17:04

sreesree123's gravatar image

2★sreesree123
1
accept rate: 0%

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; }

link

answered 05 Oct '18, 17:06

charan369's gravatar image

2★charan369
1
accept rate: 0%

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

link

answered 27 Oct '18, 11:15

anshusharmath's gravatar image

2★anshusharmath
1
accept rate: 0%

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×15,851
×1,688
×861
×281
×41
×2

question asked: 24 May '17, 17:53

question was seen: 1,309 times

last updated: 27 Oct '18, 11:15