Questions Tagged With sntemplehttps://discuss.codechef.com/tags/sntemple/?type=rssquestions tagged <span class="tag">sntemple</span>enMon, 29 May 2017 08:01:26 +0530SNTEMPLE - Editorialhttps://discuss.codechef.com/questions/99456/sntemple-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/SNTEMPLE">Practice</a><br>
<a href="https://www.codechef.com/SNCKPA17/problems/SNTEMPLE">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/admin2">admin2</a><br>
<strong>Testers:</strong> <a href="https://www.codechef.com/users/kingofnumbers">Hasan Jaddouh</a><br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/pkacprzak">Pawel Kacprzak</a></p>
<h1>DIFFICULTY:</h1>
<p>Easy</p>
<h1>PREREQUISITES:</h1>
<p>Binary search, precomputation</p>
<h1>PROBLEM:</h1>
<p>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$.</p>
<p>Given an array of $h$ of $n$ <strong>positive</strong> 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$.</p>
<h1>EXPLANATION:</h1>
<p>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$.</p>
<p>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.</p>
<p>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.</p>
<p>Now, how for a fixed $m$ find out if a sequence $magic(m)$ can be formed in $h$, and do it in linear time?</p>
<p>One possible solution is to compute two boolean arrays of size $n$:</p>
<p>$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]$.</p>
<p>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$.</p>
<p>Let's take a closer look on how to compute array $L$. Computing array $R$ is based on the same idea.</p>
<p>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:</p>
<pre><code>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]
</code></pre>
<p>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$.</p>
<p>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))$.</p>
<p>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:</p>
<pre><code>k = 0
for i = 1 to n:
if h[i] >= k+1:
k += 1
else:
k = h[i]
L[i] = k
</code></pre>
<p>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])$</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><br>
Setter's solution can be found <a href="https://www.codechef.com/download/Solutions/SNCKPA17/Setter/SNTEMPLE.cpp">here</a>.<br>
Tester's solution can be found <a href="https://www.codechef.com/download/Solutions/SNCKPA17/Tester/SNTEMPLE.cpp">here</a>.<br>
Editorialistâ€™s solution can be found <a href="https://www.codechef.com/download/Solutions/SNCKPA17/Editorialist/SNTEMPLE.cpp">here</a>. </p>pkacprzakMon, 29 May 2017 08:01:26 +0530https://discuss.codechef.com/questions/99456/sntemple-editorialbinary-searcheditorialsequencesntempleeasyarraysnckpa17