Answers to: DEVPERF - Editorialhttps://discuss.codechef.com/questions/78116/devperf-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/DEVPERF">Practice</a><br>
<a href="http://www.codechef.com/JAN16/problems/DEVPERF">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/sereja">Praveen Dhindwa</a><br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/antoniuk1">Antoniuk Vasyl</a> and <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a><br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/pushkarmishra">Pushkar Mishra</a> </p>
<h1>DIFFICULTY:</h1>
<p>Cakewalk</p>
<h1>PREREQUISITES:</h1>
<p>None</p>
<h1>PROBLEM:</h1>
<p>Given a grid filled with '*' and '.', find the cell in the grid from where the distance to the farthest '*' marked cell is travelled in least time. Report that time.</p>
<h1>EXPLANATION:</h1>
<p><strong> Subtask 1 </strong><br>
For each row in the given grid, let us maintain two variables: $max\_left$ and $max\_right$. The first one stores the column number of the left-most '*' marked cell in the row. Similarly, the other variable stores the column number of the right-most '*' marked cell in the row. Once we have processed the grid for these $2N$ values, all we need to do is iterate over all cells in the grid and check the time it will take the perfume to reach these $2N$ preprocessed cells. The cell which minimizes the maximum of times taken to reach the $2N$ cells is the answer. </p>
<p>How do we calculate this time? Let us say the perfume is released at cell $(x_1,\,\, y_1)$ and reaches cell $(x_2,\,\, y_2)$. How much time will it take given the movement constraints? The answer is $max(x_2 - x_1,\,\, y_2-y_1) + 1$. </p>
<p>How did we get this? Let us assume without loss of generality that $x_2 - x_1$ $<$ $y_2 - y_1$. Since, diagonal movement is allowed, both x-coordinate and y-coordinate can be incremented by 1 simultaneously in the required direction of movement. Once the required row or column has been reached, the remaining distance along other dimension can be travelled in a straight line. Hence, $max(x_2 - x_1,\,\, y_2-y_1)$. The extra plus 1 is because it takes 1 second for the perfume to act on the cell it is released in. </p>
<p>The proof of why we only need to consider the $2N$ points is trivial and left to the reader to work out. The complexity of this approach is $\mathcal{O}(TN^2M)$ which is sufficient for the constraints of this subtask.</p>
<p><strong> Subtask 2 </strong><br>
We need to drop a factor of $N$ from the complexity some how. Let us at the $2N$ deeper points we processed. Do we need to take into account all of them to find the answer? Some amount of thinking tells us we just need to consider four '*' marked cells in the grid: the one with max column number, the one with min column number, the one with max row number, and the one with min row number. </p>
<p>Then the answer we are looking for is $\frac{max(max\_col-min\_col,\,\, max\_row-min\_row)}{2} + 1$. Why are we taking the averages of the min and max column and row numbers? This is because it is optimal to release the perfume at the mean point. If the perfume is released at any other point, the time taken to reach at least one of the extremes will be more than in the case when it is released at the mean. The time is calculated by the same logic as given in the subtask 1 solution. This solution is $\mathcal{O}(TNM)$.</p>
<h1>OPTIMAL COMPLEXITY:</h1>
<p>$\mathcal{O}(NM)$ per test case.</p>
<h1>SAMPLE SOLUTIONS:</h1>
<p><a href="http://www.codechef.com/download/Solutions/JAN16/Setter/DEVPERF.cpp">Author</a><br>
<a href="http://www.codechef.com/download/Solutions/JAN16/Tester/DEVPERF.cpp">Tester</a><br>
<a href="http://www.codechef.com/download/Solutions/JAN16/Editorialist/DEVPERF.cpp">Editorialist</a></p>enSat, 27 Feb 2016 15:39:28 +0530Answer by esemzvhttps://discuss.codechef.com/questions/78116/devperf-editorial/79653<p>Link to all 3 sample solutions are broken. Can you please verify ONCE after posting that these links work?? Or else post some link to a reliable site like ideone.</p>esemzvSat, 27 Feb 2016 15:39:28 +0530https://discuss.codechef.com/questions/78116/devperf-editorial/79653Answer by yvetal_1https://discuss.codechef.com/questions/78116/devperf-editorial/78619<p>in short we just find the top bottom left right houses and then calculate the time from the maximum of(bottom-top) and (right-left)</p>yvetal_1Sat, 16 Jan 2016 11:25:22 +0530https://discuss.codechef.com/questions/78116/devperf-editorial/78619Answer by debugger2017https://discuss.codechef.com/questions/78116/devperf-editorial/78457<p>Can anyone please point out the mistake in following code like I've used bfs to find largest distance from any point to the other and took the median of that distance.And I've got 60 points for 2nd subtask.</p>
<p>Link to my submission is
<a href="https://www.codechef.com/viewsolution/9118654">https://www.codechef.com/viewsolution/9118654</a> </p>debugger2017Mon, 11 Jan 2016 15:59:08 +0530https://discuss.codechef.com/questions/78116/devperf-editorial/78457