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

×

SNTEMPLE - Editorial

2
3

PROBLEM LINK:

Practice
Contest

Author: admin2
Testers: Hasan Jaddouh
Editorialist: Pawel Kacprzak

DIFFICULTY:

Easy

PREREQUISITES:

Binary search, precomputation

PROBLEM:

Let a magic sequence of order $m$, denoted also by $magic(m)$, be a sequence of a integers starting from $1$ and increasing by $1$ up to $m$ and then decreasing from $m$ to $1$. For example, the magic sequence of order $5$ is: $1, 2, 3, 4, 5, 4, 3, 2, 1$. Notice that $magic(m)$ has length $2 \cdot m - 1$.

Given an array of $h$ of $n$ positive integers, denoting consecutive blocks, you want to perform the smallest number operations of reducing the high of a selected block by $1$ in such a way that after all operations are performed, there exists exactly one magic sequence in $h$ and all elements of $h$ not included in the magic sequence are $0$.

EXPLANATION:

The problem can be reformulated as follows: find the largest possible integer $m$, such that there can be formed a magic sequence of order $m$ in $h$. You might wonder why this problem is equivalent to the one asked in the original statement. Well, let $s$ be the sum of all integers in $h$. In order to form the resulting sequence $magic(m)$ in $h$ and set all elements in $h$ not included in this sequence to $0$, we have to perform $s - m \cdot (m+1) - m = s - m^2$ operations, because the sum of heights in $magic(m)$ is $m^2$. Since we want to minimize the number of performed operations, we want to maximize $m$.

The second crucial observation is that if we can form a sequence $magic(m)$ in $h$, then for each $k < m$, we can also for a sequence $magic(k)$ in $h$. This follows from the fact that in order to transform sequence $magic(m)$ to $magic(m-1)$, the only thing to do is to subtract one from each of its elements and remove the left-most and the right-most elements.

Based on the above two observations, we can use binary search to find the largest $m$, such that sequence $magic(m)$ can be formed in $h$. The lower bound for binary search should be set to $1$, and the upper bound can be set to for example $n$, but one can also compute the more exact upper bound, although it doesn't matter much.

Now, how for a fixed $m$ find out if a sequence $magic(m)$ can be formed in $h$, and do it in linear time?

One possible solution is to compute two boolean arrays of size $n$:

$L[i] := true$ if and only if the sequence $1, 2, \ldots, m$ can be formed in $h[i-m+1], h[i-m+2], \ldots, h[i]$. $R[i] := true$ if and only if the sequence $m, m-1, \ldots, 1$ can be formed in $h[i], h[i+1], \ldots, h[i+m-1]$.

Then, sequence $magic(m)$ can be formed in $h$ if and only if there exists $i$, $1 \leq i \leq n$, such that both $L[i]$ and $R[i]$ are $true$. Thus the problem is reduced to computing arrays $L$ and $R$.

Let's take a closer look on how to compute array $L$. Computing array $R$ is based on the same idea.

First of all, let's set all entries in $L$ to $false$. The idea is to iterate over $h$ from left to right (right to left if you want to compute $R$) while updating variable $k$ denoting the length of the longest sequence $1, 2, 3, \ldots, k$ ending in the current element, where $k$ is at most $m$. The below pseudocode illustrates the approach:

k = 0
for i = 1 to n:
    if h[i] >= k+1:
        k += 1
        if k == m:
            L[i] = true
            k -= 1
    else:
        k = h[i]

The above idea is based on the fact that if we have a sequence $1, 2, \ldots, k$ ending in $i-1$, then if $h[i]$ is at least $k+1$ we can extend the sequence by one, and if $h[i]$ is at most $k$, then the best we can do is to set $k$ to $h[i]$, because a sequence $1, 2, \ldots, k$ ending at index $i-1$ can be transformed to a non-longer sequence $1, 2, \ldots, h[i]$ ending at index $i$ if $h[i] \leq k$.

Since the computing of arrays $L$ and $R$ takes $O(n)$ time, and the range over we perform binary search has length $O(n)$, the total time complexity is $O(n \cdot \log(n))$.

As it was pointed out with the comments, the above method can be improved to $O(n)$ solution by avoiding binary search. The idea is to compute arrays $L$ and $R$ at the beginning, without specifying $m$. We define $L[i]$ (and similarly $R[i]$) as the maximum length of sequence $1, 2, \ldots$ ending in $i$, and compute it as follows:

k = 0
for i = 1 to n:
    if h[i] >= k+1:
        k += 1
    else:
        k = h[i]
    L[i] = k

Then, after computing arrays $L$ and $R$, we know that the maximum $m$ for which magic sequence of order $m$ exists is $\max\limits_{1 \leq i \leq n} \min(L[i], R[i])$

AUTHOR'S AND TESTER'S SOLUTIONS:


Setter's solution can be found here.
Tester's solution can be found here.
Editorialist’s solution can be found here.

This question is marked "community wiki".

asked 29 May, 08:01

pkacprzak's gravatar image

6★pkacprzak ♦♦
71483787
accept rate: 12%

edited 30 May, 12:19

admin's gravatar image

0★admin ♦♦
15.9k347484508

@pkacprzak can't able to open the editorials.."Access denied error"

(29 May, 09:34) agrocks233★

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

(29 May, 11:57) pkacprzak ♦♦6★

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

(29 May, 23:44) siddharthp5383★

21

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 code for reference.

link

answered 29 May, 10:54

meooow's gravatar image

6★meooow ♦
5.0k49
accept rate: 47%

edited 29 May, 11:58

3

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

(29 May, 11:18) pkacprzak ♦♦6★

Solution in python3.4 : SNTEMPLE

link

answered 29 May, 11:48

inishchith's gravatar image

3★inishchith
312
accept rate: 0%

we can also do it in O(n) by maintaining left and right array and then calculating the answer. solution link

link

answered 29 May, 10:47

zyloc's gravatar image

3★zyloc
11
accept rate: 0%

Yup. O(N) solution.

(29 May, 10:55) omjego4★

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

link

answered 29 May, 21:16

genius007's gravatar image

3★genius007
313
accept rate: 0%

edited 29 May, 22:17

Thanks mate.

(29 May, 22:24) chari4073★

@genius007 , bhambhu on fire.

(29 May, 22:56) swamicoder4★

There is some error with the links, please fix them.

link

answered 29 May, 09:24

horowest's gravatar image

2★horowest
1
accept rate: 0%

Not able to access editorial

link

answered 29 May, 09:34

aadeshrathore's gravatar image

4★aadeshrathore
311
accept rate: 0%

access denied for links of the solution

link

answered 29 May, 10:03

sonu_628's gravatar image

4★sonu_628
1928
accept rate: 9%

Can someone explain o(n) sol in detail with comments

Would be a great help Appreciate it. Thanks in advance.

link

answered 29 May, 14:07

kunwarpreet281's gravatar image

2★kunwarpreet281
1
accept rate: 0%

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 hn-1 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 ++> https://www.codechef.com/viewsolution/13847942 click heret Remove the comments in this code and run this in codechef Id you can easily understand the whole magic.

link

answered 29 May, 14:09

shubhamdhama12's gravatar image

3★shubhamdhama12
1
accept rate: 0%

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

link

answered 29 May, 19:02

chari407's gravatar image

3★chari407
42316
accept rate: 0%

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

link

answered 30 May, 08:53

kunwarpreet281's gravatar image

2★kunwarpreet281
1
accept rate: 0%

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

link

answered 30 May, 14:20

sandynigs's gravatar image

2★sandynigs
1
accept rate: 0%

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

link

answered 30 May, 15:11

theintel's gravatar image

2★theintel
276
accept rate: 0%

@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

link

answered 30 May, 15:14

theintel's gravatar image

2★theintel
276
accept rate: 0%

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

link

answered 31 May, 11:09

sathyacse67's gravatar image

2★sathyacse67
1
accept rate: 0%

it can take such inputs

(06 Jul, 14:53) soham12345★

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

link

answered 02 Jun, 18:52

tni_md's gravatar image

4★tni_md
111
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:

×11,590
×2,610
×594
×528
×27
×13
×7

question asked: 29 May, 08:01

question was seen: 3,526 times

last updated: 06 Jul, 14:53