Questions Tagged With qabchttps://discuss.codechef.com/tags/qabc/?type=rssquestions tagged <span class="tag">qabc</span>enSun, 14 Oct 2018 14:02:11 +0530Need help on the question QABC of Snackdownhttps://discuss.codechef.com/questions/137274/need-help-on-the-question-qabc-of-snackdown<p>I need help on how to start the operation on any location of array. Just a hint would work.</p>koulick424Sun, 14 Oct 2018 14:02:11 +0530https://discuss.codechef.com/questions/137274/need-help-on-the-question-qabc-of-snackdownproblemqabchelpforQABC - EDITORIALhttps://discuss.codechef.com/questions/137173/qabc-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/QABC">Practice</a> <br>
<a href="https://www.codechef.com/SNCKQL19/problems/QABC">Contest</a></p>
<p><strong>Setter:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/kingofnumbers">Hasan Jaddouh</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/taran_1407">Taranpreet Singh</a> </p>
<h1>DIFFICULTY:</h1>
<p>Simple</p>
<h1>PREREQUISITES:</h1>
<p>Observations and simple Invariant would do the trick. Just a creative or experienced mind is sufficient. :D</p>
<h1>PROBLEM:</h1>
<p>Given two sequence $A$ and $B$ of length $N$ each, we need to apply operation on array $A$ to make it same as array $B$. The operation is decsribed as
<em> Choose any position $i$ in range $[1, N-2]$.
</em> Do $A[i] += 1$, $A[i+1]+=2$ and $A[i+2]+=3$. (Called as applying operation on position $i$.)</p>
<h1>SUPER QUICK EXPLANATION</h1>
<ul>
<li>Perform operations from left to right. If $A[i] > B[i]$ at any point, answer is $-1$. Also, If after applying operations till position position $N-2$, If last two elements differ in both arrays, answer is again impossible.</li>
<li>If $A[i] == B[i]$, we can directly move to next position without applying operation. If $A[i] < B[i]$, we apply operation $B[i]-A[i]$ times at position $i$ and move to next position.</li>
</ul>
<h1>EXPLANATION</h1>
<p>This problem require certain observations, which are stated below.</p>
<p>If $A[i]>B[i]$ after any number of operations (including zero), answer is impossible since we can never reduce $A[i]$ or increase $B[i]$, hence achieving $A[i]==B[i]$ is impossible now.</p>
<p>Second crucial thing is, that the order of applying operations is irrelevant. That is, Suppose we apply operation at position 2 first, followed by operation at position 1. It will give same results as applying operation at position 1 followed by operation at position 2.</p>
<p>Second observation allow us to apply operations from left to right, because, if a valid sequence of operations exist, there will also exist a perumtation of those operations which are arranged from left to right.</p>
<p>But you might be wondering why should we apply operations from left to right. So, here we go.</p>
<p>Since we know, that $A[i]$ can only be altered by operations applied at position $i$, $i-1$ and $i-2$. But, $A[1]$ can only be altered by operation at position 1. So, we have to apply operation at position 1 $B[i]-A[i]$ times. Now, We face same problem again. $A[2]$ can be altered by operation at position $1$ and $2$. But we cannot apply operation at position 1 anymore, since it will also increase $A[1]$ leading to impossible case.</p>
<p>Here, we have the <strong>invariant</strong>, that once we reach position i, we have made $A[j] == B[j] \forall j < i$, thus, we have to apply operation $B[i]-A[i]$ times, so that We achieve $A[i]==B[i]$. After applying operations, we can no longer apply operation at any position j, $j \leq i$. This continues till we reach $N-2$ position.</p>
<p>At the end, If after appling operation for all positions in range $[1, N-2]$, if elements at last two positions in both arrays do not match, we can never make array $A$ same as array $B$, thus, answer becomes impossible in this case too.</p>
<p>PS: A new term for today is <strong>Invariant</strong>, useful in proving correctness of an algorithm or process, which can be read about <a href="https://en.wikipedia.org/wiki/Invariant_(computer_science)">here</a>.</p>
<h1>Time Complexity</h1>
<p>Since we iterate from left to right across whole range, Time complexity is $O(N)$.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><a href="http://www.codechef.com/download/Solutions/SNCKQL19/setter/QABC.cpp">Setter's solution</a><br>
<a href="http://www.codechef.com/download/Solutions/SNCKQL19/tester/QABC.cpp">Tester's solution</a> <br>
<a href="http://www.codechef.com/download/Solutions/SNCKQL19/editorialist/QABC.java">Editorialist's solution</a> </p>
<p>Feel free to Share your approach, If it differs. Suggestions are always welcomed. :)</p>taran_1407Sat, 13 Oct 2018 13:03:57 +0530https://discuss.codechef.com/questions/137173/qabc-editorialsimpletaran_1407qabcsnckql19observations