Questions Tagged With popc2018https://discuss.codechef.com/tags/popc2018/?type=rssquestions tagged <span class="tag">popc2018</span>enSun, 21 Jan 2018 17:32:04 +0530PALINREP - Editorialhttps://discuss.codechef.com/questions/121762/palinrep-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/PALINREP">Practice</a></p>
<p><a href="https://www.codechef.com/POPC2018/problems/PALINREP">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/akshayvenkat97">Akshay Venkataramani</a></p>
<p><strong>Tester:</strong> <a href="https://www.codechef.com/users/accelmage">Timothy</a></p>
<h1>DIFFICULTY:</h1>
<p>CAKEWALK</p>
<h1>EXPLANATION:</h1>
<p>All palindromes of length greater than 1 have characters that are repeated more than once. Hence, for all n > 1 the answer is -1. For n=1, the lexicographically smallest string of length 1 is 'a'. </p>
<h1>AUTHOR'S SOLUTION:</h1>
<p>Author's solution can be found <a href="https://ideone.com/lvbHvG">here</a>.</p>accelmageSun, 21 Jan 2018 17:29:03 +0530https://discuss.codechef.com/questions/121762/palinrep-editorialpalindromepopc2018editorialcakewalkMULARR - Editorialhttps://discuss.codechef.com/questions/121733/mularr-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/MULARR">Practice</a></p>
<p><a href="https://www.codechef.com/POPC2018/problems/MULARR">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/akshayvenkat97">Akshay Venkataramani</a></p>
<p><strong>Tester:</strong> <a href="https://www.codechef.com/users/accelmage">Timothy Jeyadoss</a></p>
<h1>DIFFICULTY:</h1>
<p>Cakewalk</p>
<h1>PREREQUISITES:</h1>
<p>Arrays</p>
<h1>EXPLANATION:</h1>
<p>Simply find the product of the array. <strong>NOTE</strong>: Use long long int for all calculations. Integer variables are 32 bit, and can only calculate values precisely upto 10^9. Post that, long long int needs to be used(64 bit) for all calculations.</p>
<p>The constraints were N<=10 and A[i]<=15, resulting in a maximum possible product of 15^10, which is greater than 10^12.</p>
<h1>AUTHOR'S SOLUTION:</h1>
<p>Author's solution can be found <a href="https://ideone.com/uxAlrZ">here</a></p>akshayvenkat97Sun, 21 Jan 2018 12:27:57 +0530https://discuss.codechef.com/questions/121733/mularr-editorialmularrarraypopc2018editorialcakewalkGPTRIPLE - Editorialhttps://discuss.codechef.com/questions/121758/gptriple-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/GPTRIPLE">Practice</a></p>
<p><a href="https://www.codechef.com/POPC2018/problems/GPTRIPLE">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/akshayvenkat97">Akshay Venkataramani</a></p>
<p><strong>Tester:</strong> <a href="https://www.codechef.com/users/accelmage">Timothy Jeyadoss</a></p>
<h1>DIFFICULTY:</h1>
<p>Easy-Medium</p>
<h1>PREREQUISITES:</h1>
<p>Dynamic Programming, STL, Geometric Progression basics</p>
<h1>EXPLANATION:</h1>
<p>First up, we have corner case when k=1. For this, we simply have to store each element in a map, and if number of occurences of any value is >=3 , let the no. of occurences be n. We have nC3 (recall combinations formula? ) possible ways to choose our triplet. nC3 = (n<em>(n-1)</em>(n-2))/6. </p>
<p>Otherwise, we need to incorporate dynamic programming into our solution.</p>
<p>Let us have 3 maps, m1, m2 , m3 , each storing the number of possible ways for a value to be the first term of our GP, second term of our GP, and third term of our GP respectively. </p>
<p>For example, if input is N=6, K=2, and the input array A=[1,1,2,2,4,8] </p>
<h1> m1 </h1>
<p>m1 will be equal to {1,2} , {2,2} , {4,1} , {8,1} . i.e., each term along with the number of ways in which it can be the first term of our GP. Each of these pair of values are present inside m1. {1,2} denotes that 1 can be the first term of our GP in 2 distinct ways. {2,2} denotes that 2 can be the first term of our GP in 2 distinct ways. Similarly, 4 and 8 can be the first term of our GP respectively. For this step, m1[a[i]]++ would do the job. </p>
<h1> m2 </h1>
<p>m2 will be equal to {2,4} , {4,2}, {8,1} <b> IMPORTANT STEP : This is because, 2 can be the second term of our GP in the following ways->choosing first 1, first 2; choosing first 1, second 2; choosing second 1,first 2; Choosing second 1, second 2; Hence, we have the pair {2,4} inside m2.</b></p><b>
<p>Similarly, we can perform the same steps for first term of our GP being 2 and second term being 4. There are 2 ways in which 4 can be the second term of our GP-> choosing first 2, and 4; choosing second 2, and 4; Hence, we have the pair {4,2} inside m2. </p>
</b><p><b>For 8 being the second term in our GP, we have one way -> choosing the only 4 and only 8. Hence we have a pair {8,1} in m2. </b></p>
<p>This step, can be performed in our code simply by checking if a[i]%k equates to 0. If this is possible, it means a[i] can be the second member of our GP (recall that, if the three terms of our GP are gp[1] , gp[2] and gp[3] , then gp[2]/gp[1] = k and gp[3]/gp[2] = k). Therefore, <strong>if a[i]%k is 0, we can have a[i] as the 2nd term of our GP for every a[i]/k being the first term of our GP.</strong> </p>
<h1> m3 </h1>
<p>m3 will be equal to {4,4} , {8,2}. This is because, we have 4 ways in which 4 can be the third and final term of our GP , i.e., each combination of {1,2} mentioned in previous step appended with a 4.
Similary, 8 can be the third term of our GP in 2 ways , i.e., each combination of {2,4} mentioned in previous step appended with an 8. </p>
<p>This step can again be performed code wise, by checking if (a[i]%(k<sup>2</sup>)) is 0. If this is the case, we can have a[i] as the third term of our GP, for every a[i]/k being the second term of our GP. This is where dynamic programming comes into picture. </p>
<p>Hence, in the end, we traverse m3 (Since we need a triplet of GP terms) , and add the value to the answer. </p>
<p><b> Corner case!! </b> When m3 has a value 0, there's a chance that it would have considered the same 0 as first, second and third term of the GP. We need to subtract those possibilities from the overall answer carefully. For example, if our array had only one zero present in the input, there would still be an entry {0,1} in m3. This needs to be taken care of properly. [refer author's solution!] </p>
<h1>AUTHOR'S SOLUTION:</h1>
<p>Author's solution can be found <a href="https://ideone.com/KATUoz">here</a>.</p>akshayvenkat97Sun, 21 Jan 2018 17:23:11 +0530https://discuss.codechef.com/questions/121758/gptriple-editorialdynamic-programmingstleasy-mediumeditorialgptriplepopc2018TREEEE - Editorialhttps://discuss.codechef.com/questions/121760/treeee-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/TREEEE">Practice</a></p>
<p><a href="https://www.codechef.com/POPC2018/problems/TREEEE">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/akshayvenkat97">Akshay Venkataramani</a></p>
<p><strong>Tester:</strong> <a href="https://www.codechef.com/users/accelmage">Timothy Jeyadoss</a></p>
<h1>DIFFICULTY:</h1>
<p>Easy-Medium</p>
<h1>PREREQUISITES:</h1>
<p>XOR Property, Graphs, BFS/DFS</p>
<h1>EXPLANATION:</h1>
<p>The optimal answer can be reached, only if we perform the operation starting from the root till the leaf. Any other sequence of operations will affect previously produced answer, and hence this observation is crucial.</p>
<p>Hence we perform a depth-first-traversal (also known as depth-first-search (DFS)) on the tree, and if we find that a node has a value different from its target, we increment our overall answer. </p>
<p>We need to maintain two variables - each for odd and even heights respectively. Let us store it an array of 2 variables(named as parity in Author's solution). Both parity[0] and parity[1] are initialized to zero. </p>
<p>This is essential due to the following reason : </p>
<p><i> Consider a tree with root 1 , and 3 being its <b> granchild </b>. In this tree, if both 1 and 3 have initialValues not equal to targetValues, performing the operation once(on node 1) is enough for node 3 to also have its value flipped(i.e., to the target value). </i></p>
<p>In the author's solution, the height of root is set at 1 and the remaining nodes' heights are set appropriately. </p>
<p>Hence, during the dfs, we check for two things :- </p>
<p><b> 1) Let x be the height of the current node. if parity[x%2] == 0, it means that the current node has no effective flips in it, i.e., its current value is equal to its initial value. If initialValue[currentNode] is not equal to target[currentNode] , we incremement overall answer, and do parity[x%2]=(parity[x%2]+1)%2 . Try to understand why this step is done by yourself, using pen or paper and by constructing various trees, before moving to the next part. </b></p><b>
</b><p><b>2) The next part should be simple, if you understood the first part well. If parity[x%2]==1, it means there's an effective flip waiting in the currentNode. Hence, if initialValue[currentNode]==target[currentNode], the effective flip waiting to be performed on the current node is done. When we perform it, the value is no longer equal to target. Hence, we need to increment overall answer and also do
parity[x%2]=(parity[x%2]+1)%2. </b></p>
<p>Third case -> parity[x%2] == 0 and initialValue[currentNode] == target[currentNode]. Here, we needn't do anything and leave it as such. </p>
<p>Fourth Case -> parity[x%2] == 1 and initialValue[currentNode] != target[currentNode]. Here, we needn't do anything again and leave it as such. This is because, the effective flip remaining in the node, when performed, makes the values equal. </p>
<h1>AUTHOR'S SOLUTION:</h1>
<p>Author's solution can be found <a href="https://ideone.com/u8BBRa">here</a>.</p>
<h1>TESTER'S SOLUTION:</h1>
<p>Tester's solution can be found <a href="https://ideone.com/JUAwnP">here</a>.</p>akshayvenkat97Sun, 21 Jan 2018 17:26:57 +0530https://discuss.codechef.com/questions/121760/treeee-editorialxordfstreeeeeasy-mediumeditorialpopc2018HACKS - Editorialhttps://discuss.codechef.com/questions/121757/hacks-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/HACKS">Practice</a></p>
<p><a href="https://www.codechef.com/POPC2018/problems/HACKS">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/accelmage">Timothy</a></p>
<p><strong>Tester:</strong> <a href="https://www.codechef.com/users/akshayvenkat97">Akshay Venkataramani</a></p>
<h1>DIFFICULTY:</h1>
<p>EASY</p>
<h1>PREREQUISITES:</h1>
<p>Math, GCD, Fibonacci</p>
<h1>EXPLANATION:</h1>
<p><em>The smallest number that can be obtained by substituting arbitrary values for <strong>x</strong> and <strong>y</strong>, in the equation <strong>ax+by=c</strong> is the GCD of <strong>a</strong> and <strong>b</strong>.</em></p>
<p>The GCD can be calculated using Euclidean Algorithm or by using c++'s inbuilt function <strong>__gcd()</strong>.</p>
<p>But this isn't enough to solve the problem. This is because of the constraint <strong>0 ≤ i,j ≤ 10<sup>5</sup></strong>. It is not possible to store any Fibonacci number after the 92<sup>nd</sup> one. This is where another property comes into play. </p>
<p><em>The GCD of <strong>i<sup>th</sup></strong> and <strong>j<sup>th</sup></strong> Fibonacci numbers is the Fibonacci number whose position is the GCD of <strong>i</strong> and <strong>j</strong>.</em> </p>
<p><strong>GCD(Fib(i),Fib(j)) = Fib(GCD(i,j))</strong></p>
<p>This property holds only if Fibonacci series is 0-indexed.</p>
<h1>AUTHOR'S SOLUTION:</h1>
<p>Author's solution can be found <a href="https://ideone.com/mwabUX">here</a>.</p>accelmageSun, 21 Jan 2018 17:23:09 +0530https://discuss.codechef.com/questions/121757/hacks-editorialgcdeasyhacksfibonaccieditorialpopc2018HRACE - Editorialhttps://discuss.codechef.com/questions/121759/hrace-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/HRACE">Practice</a></p>
<p><a href="https://www.codechef.com/POPC2018/problems/HRACE">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/accelmage">Timothy</a></p>
<p><strong>Tester:</strong> <a href="https://www.codechef.com/users/akshayvenkat97">Akshay Venkataramani</a></p>
<h1>DIFFICULTY:</h1>
<p>EASY-MEDIUM</p>
<h1>PREREQUISITES:</h1>
<p>Graph, BFS, Shortest Path Algorithms</p>
<h1>EXPLANATION:</h1>
<p>The question requires a reversal of perspective. Trying to find the shortest distance to the finish line(node <strong>N</strong>) from each of the starting points(nodes <strong>1 to S</strong>) gives a TLE. Instead, we can find the shortest distance from node <strong>N</strong> to nodes <strong>1 to S</strong>. </p>
<p>This can be done using shortest path algorithms like Dijkstra's or by using a BFS, which is <strong>O(N)</strong>, since the graph is unweighted. </p>
<p>Once the shortest distances to all nodes are found, it is just a matter of finding the count of the maximum distances.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="https://ideone.com/qQTlg8">here</a>.</p>
<p>Tester's solution can be found <a href="https://ideone.com/VR70BP">here</a>.</p>accelmageSun, 21 Jan 2018 17:26:26 +0530https://discuss.codechef.com/questions/121759/hrace-editorialbfsgrapheasy-mediumeditorialpopc2018SMALLSQ - Editorialhttps://discuss.codechef.com/questions/121763/smallsq-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/SMALLSQ">Practice</a></p>
<p><a href="https://www.codechef.com/POPC2018/problems/SMALLSQ">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/akshayvenkat97">Akshay Venkataramani</a></p>
<p><strong>Tester:</strong> <a href="https://www.codechef.com/users/accelmage">Timothy</a></p>
<h1>DIFFICULTY:</h1>
<p>EASY-MEDIUM</p>
<h1>PREREQUISITES:</h1>
<p>Math, Sieve of Eratosthenes, Prime Factorization</p>
<h1>EXPLANATION:</h1>
<p>Let's look at the solution using an example. Suppose the input is 60. The prime factorization is:</p>
<p><strong>60 = 2<sup>2</sup> * 3 * 5</strong></p>
<p>Looking at this might've given you a hint to the solution. The factors in the prime factorization of a square number have even powers. Hence, we just need to find the factors that have odd powers.</p>
<p>3 and 5 are the factors that have odd powers in the prime factorization of 60. Multiplying 60 by 15 (3*5) gives 900, which is a square number whose prime factorization is:</p>
<p><strong>900 = 2<sup>2</sup> * 3<sup>2</sup> * 5<sup>2</sup></strong></p>
<p>To find the prime factorization of a number, we slightly modify the Sieve of Eratosthenes to calculate and store the smallest prime factor for all numbers. This precalculation allows us to find the prime factorization extremely fast. The following routine is used to find the prime factorization:</p>
<pre><code>map<ll,ll> factors;
while(n!=1)
{
factors[smallestPrime[n]]++;
n=n/smallestPrime[n];
}
return factors;
</code></pre>
<p>More info about this method can be found <a href="https://www.geeksforgeeks.org/prime-factorization-using-sieve-olog-n-multiple-queries/">here</a>. This method takes <strong>O(logn)</strong> to factorize a number.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTION:</h1>
<p>Author's solution can be found <a href="https://ideone.com/pZEdSE">here</a>.</p>
<p>Tester's solution can be found <a href="https://ideone.com/SRY4Gg">here</a>.</p>accelmageSun, 21 Jan 2018 17:32:04 +0530https://discuss.codechef.com/questions/121763/smallsq-editorialsieveprime-factoreasy-mediumeditorialpopc2018ADDBIT - Editorialhttps://discuss.codechef.com/questions/121756/addbit-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/ADDBIT">Practice</a></p>
<p><a href="https://www.codechef.com/POPC2018/problems/ADDBIT">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/akshayvenkat97">Akshay Venkataramani</a></p>
<p><strong>Tester:</strong> <a href="https://www.codechef.com/users/accelmage">Timothy Jeyadoss</a></p>
<h1>DIFFICULTY:</h1>
<p>Cakewalk</p>
<h1>PREREQUISITES:</h1>
<p>Strings</p>
<h1>EXPLANATION:</h1>
<p>Simply traverse the string from left to right, and when you find a 0, break from the loop. Until then, keep adding to the answer. </p>
<p>This is the basic idea behind binary addition of 1 to any binary number(ofcourse, with the slight modification that if all bits are 1, append a extra 1 at the beginning).</p>
<p>This problem can be solved easily using "string" datatype that is available in C++, Java, Python etc. It is a little tedious to solve this problem in C, but simple nevertheless when you make note of the constraints properly.</p>
<h1>TESTER'S SOLUTION:</h1>
<p>Tester's solution can be found <a href="https://ideone.com/Y56JzG">here</a>.</p>akshayvenkat97Sun, 21 Jan 2018 17:20:34 +0530https://discuss.codechef.com/questions/121756/addbit-editorialpopc2018addbitstringseditorialcakewalkPOPB - Editorialhttps://discuss.codechef.com/questions/121761/popb-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/POPB">Practice</a></p>
<p><a href="https://www.codechef.com/POPC2018/problems/POPB">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/akshayvenkat97">Akshay Venkataramani</a></p>
<p><strong>Tester:</strong> <a href="https://www.codechef.com/users/accelmage">Timothy Jeyadoss</a></p>
<h1>DIFFICULTY:</h1>
<p>Easy</p>
<h1>PREREQUISITES:</h1>
<p>Simple Math</p>
<h1>EXPLANATION:</h1>
<p>Length wise, we could have produced a maximum of floor(N/K) squares and width wise, we could have produced a maximum of floor(M/K) squares. Multiply these two for the answer. </p>
<p>(N*M)/(K*K) might seem like a solution, but consider this : N=5,M=7,K=4. (7 * 5)/(4 * 4) is 2, but we can only produce one square from this rectangle(You can work it out by paper on why that's the case!) </p>
<h1>AUTHOR'S SOLUTION:</h1>
<p>Author's solution can be found <a href="https://ideone.com/3lMDD0">here</a>.</p>akshayvenkat97Sun, 21 Jan 2018 17:28:53 +0530https://discuss.codechef.com/questions/121761/popb-editorialpopbeasypopc2018simple-matheditorial