Questions Tagged With feketehttps://discuss.codechef.com/tags/fekete/?type=rssquestions tagged <span class="tag">fekete</span>enSun, 29 Jul 2018 00:45:16 +0530SPLST - Editorialhttps://discuss.codechef.com/questions/132596/splst-editorial<h1>Problem Link</h1>
<p><a href="https://www.codechef.com/problems/SPLST">Practice</a></p>
<p><a href="https://www.codechef.com/LTIME62B/problems/SPLST">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/fekete">Ivan Fekete</a></p>
<p><strong>Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a></p>
<p><strong>Editorialist:</strong> <a href="https://www.codechef.com/users/likecs">Bhuvnesh Jain</a></p>
<h1>Difficulty</h1>
<p>CAKEWALK</p>
<h1>Prerequisites</h1>
<p>None</p>
<h1>Problem</h1>
<p>You are 3 piles of stones containing $a, b, c$ stones respectively. You can chose one of the piles and split it into 2 parts (possibly empty) and put the stones for the first part in one pile and the second one in another. Is it possible to have 2 piles with $x, y$ stones?</p>
<h1>Explanation</h1>
<h3>Author's Solution</h3>
<p>Let us first sort the piles in increasing number of stones. So, $a <= b <= c$. Also, assume $x <= y$. The first condition which should be satisfied is that the number of stones in the beginning and the end should remain same as none of the stones is thrown away, they are just rearranged into different piles.</p>
<p><b>Condition 1: </b> a + b + c == x + y</p>
<p>Next thing is to observe is that the size of a pile can only increase and if it decreases it becomes 0 only. So, if the number of stones in the smallest pile, in the beginning, is more is than the number of stones in the smallest pile, in the end, we can't achieve our target.</p>
<p><b>Condition 2: </b> a <= x</p>
<p>Similar case applies to the second smallest pile as well.</p>
<p><b>Condition 3: </b> b <= y</p>
<p>The above 3 conditions are necessary for us to have a solution. But are they sufficient? Apparently yes, as we can always achieve our target as follow when the above 3 conditions hold:</p>
<p>Consider the third pile ($c$) as the pile with excess stones. Move the required number of stones to the first pile and the remaining stones to the second pile. As the total number of stones is same and the number of stones in both remaining piles can only increase, such a move will exist.</p>
<p>For more details, you can refer to the author's or tester's solution below.</p>
<h3>Editorialist Solution</h3>
<p>Since the constraints are small, we can simply simulate the above process, by trying to eliminate each pile and moving the required number of stones to the other 2 piles. Writing the cases for this can be tedious and some cases might not be handled as well if not implemented correctly. So, one idea is to try each possible pairing using permutations of the piles such that you always consider the last piles as the one with excess stones which would be removed by splitting stones into other piles. The conditions to check are simply:</p>
<ol>
<li>Find the number of stones required in the first and second pile.</li>
<li>Check if the required number of stones is non-negative or not.</li>
<li>Check if the sum of the number of required stones can be exactly satisfied by the excess pile.</li>
</ol>
<p>Once, you are clear with the above idea, you can see the editorialist implementation below for help.</p>
<p>Feel free to share your approach, if it was somewhat different.</p>
<h1>Time Complexity</h1>
<p>$O(1)$</p>
<h1>Space Complexity</h1>
<p>$O(1)$</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME62/setter/SPLST.cpp">here</a>.</p>
<p>Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME62/tester/SPLST.cpp">here</a>.</p>
<p>Editorialist's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME62/editorialist/SPLST.cpp">here</a>.</p>likecsSat, 28 Jul 2018 16:56:56 +0530https://discuss.codechef.com/questions/132596/splst-editorialfeketeltime62likecseditorialcakewalkMEXRNG - Editorialhttps://discuss.codechef.com/questions/132662/mexrng-editorial<h1>Problem Link</h1>
<p><a href="https://www.codechef.com/problems/MEXRNG">Practice</a></p>
<p><a href="https://www.codechef.com/LTIME62A/problems/MEXRNG">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/fekete">Ivan Fekete</a></p>
<p><strong>Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a></p>
<p><strong>Editorialist:</strong> <a href="https://www.codechef.com/users/likecs">Bhuvnesh Jain</a></p>
<h1>Difficulty</h1>
<p>MEDIUM-HARD</p>
<h1>Prerequisites</h1>
<p>Sqrt Decomposition, Mex</p>
<h1>Problem</h1>
<p>You are given an array $A$ of size $N$. You are also given $Q$ queries. For each query, given $L$ and $R$, find the mex (greater than 0) of the number of occurrences of all the numbers in the given range.</p>
<h1>Explanation</h1>
<p>The first thing to notice is that the size of frequency list of the subarrays can be the order of length of the subarray (as the numbers can be unique in the subarray). Thus, even building the frequency list even in order length of subarray would be costly per query. This will be sufficient for subtask 1 but not for the full problem.</p>
<p>The next thing to note that while finding the mex of an array, if the mex is $x$, it means all the numbers from $1$ to $(x-1)$ are present in the array. For our problem, this means there exists a number whose frequency in the given range lies between $1$ and $(x-1)$. This means the number of numbers in this range is at least $1 + 2 + \cdots + (x-1) = (x-1) * x/2$. Since the maximum size of a range can be $N$. Using this $2$ equations, we get that <b>maximum mex for frequency of numbers can be atmost $2 * sqrt(N)$</b>.</p>
<p>The last idea tells us that maintaining frequency greater than $2 * sqrt(N)$ is not useful and it will never contribute to our answer. This fact will be useful for our precomputation step and also help to reduce the amount of memory required. More of this will be clear towards the end of the editorial.</p>
<p>To efficiently calculate the above function, we will rely on the technique of sqrt decomposition. The basic idea of sqrt decomposition of arrays is to split the array into sqrt blocks, calculate the function of each sqrt block efficiently and iterate over the edges points (if they exist) in each query. But here the function we want to evaluate deals on the frequency of numbers which is difficult to update with each passing block as in normal sqrt decomposition.</p>
<p>The algorithm for the sqrt decomposition part will be as follows:</p>
<ol>
<li>Split the array into blocks of size K.</li>
<li>Calculate the frequency of each number inside each block.</li>
<li>For every block, we also maintain a table how many times does the frequency of an element occur i.e. frequency fo frequencies.</li>
<li>Here we also precompute the frequency of frequencies across 2 blocks as well for only the required elements (i.e. frequency up to $2 * sqrt(N)$. This means we have the frequency of frequency available from block $i$ to $j$.</li>
<li>For dealing with frequency, we store the total frequency of number starting from block "x" to some index in block "y", both in left to right and right to left order which would help us deal with queries later.</li>
<li>For every query, we apply brute force approach if the blocks are same or adjacent. Otherwise, we have the frequency of frequency table for complete blocks available. Only the corner elements in half blocks i.e. containing $L$ and $R$ is left. For this, we simply traverse the elements and update the frequency as well as the frequency of frequency count.</li>
<li>Now finally, for calculating the mex in the query we simply iterate from 1 to .... till we find the frequency of frequency for some "x" as 0. This step will take atmost $O(2 * sqrt(N))$ operations as the answer is bounded by this.</li>
</ol>
<p>Once, you are clear with the above idea, you can see the author implementation below for help. I have added comments to make the solution more readable and understandable on lines of the editorial. I request you to go through the solution and if anything is not clear and requires more understanding, please comment below.</p>
<p>The time complexity of the above approach is $O(N * (N/K) + Q * K)$. The first part is for pre-computation which is done for all blocks $(N/K)$ in number and for each, it takes $O(N)$ time. The next part is for answering the queries. Since we do not traverse the complete blocks and only iterate over elements in sub-complete blocks, it takes atmost $O(K)$, i.e. size of the block, for each query. This is true both for brute force and optimised query operation.</p>
<p>For, the optimal value of $K$.</p>
<p>$N * (N/K) == Q * K$</p>
<p>meaning $K = N / sqrt(Q)$. Though you can hard code it to some nearby value as well. The author chose the value as $600$ in his code.</p>
<p>The space complexity as seen from author's solution is $O((N/K) * (N/K) * sqrt(N))$. For optimal value of $K$, this is $O(Q * sqrt(N))$.</p>
<p>Feel free to share your approach, if it was somewhat different.</p>
<h1>Time Complexity</h1>
<p>$O(N * sqrt(Q))$</p>
<h1>Space Complexity</h1>
<p>$O(Q * sqrt(N))$</p>
<h2>Problem with similar ideas and tricks</h2>
<p><a href="https://www.codechef.com/problems/ISOARRAY">ISOARRAY</a></p>
<h1>AUTHOR'S SOLUTION:</h1>
<p>Author's solution can be found <a href="https://ideone.com/8sxhBR">here</a>.</p>likecsSun, 29 Jul 2018 00:45:16 +0530https://discuss.codechef.com/questions/132662/mexrng-editorialeditorialfeketeltime62sqrt-decomplikecsmedium-hardmexMKSTR - Editorialhttps://discuss.codechef.com/questions/132597/mkstr-editorial<h1>Problem Link</h1>
<p><a href="https://www.codechef.com/problems/MKSTR">Practice</a></p>
<p><a href="https://www.codechef.com/LTIME62A/problems/MKSTR">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/fekete">Ivan Fekete</a></p>
<p><strong>Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a></p>
<p><strong>Editorialist:</strong> <a href="https://www.codechef.com/users/likecs">Bhuvnesh Jain</a></p>
<h1>Difficulty</h1>
<p>MEDIUM</p>
<h1>Prerequisites</h1>
<p>Dynamic Programming, Tries, Hashing</p>
<h1>Problem</h1>
<p>You are given a empty string $S$ and a taget string $T$. Youa re also provided with $N$ patterns $p[i]$. You may perform any number of operations as follows:</p>
<ol>
<li>Insert character 'x' to the left of the string $L$. Cost: cl[x] * |L|</li>
<li>Insert character 'x' to the right of the string $L$. Cost: cr[x] * |L|</li>
<li>Insert string 'p[i]' to the left of the string $L$. Cost: kl[i] * |L|</li>
<li>Insert string 'p[i]' to the right of the string $L$. Cost: kr[i] * |L|</li>
</ol>
<p>Find the minimum cost to make string $T$ from $S$ using the above operations. Note that |L| denotes the current length of the string $L$, before the operation is performed.</p>
<h1>Explanation</h1>
<p>The problem statement clearly lists some transitions and cost related to it and we would like to minimise the overall cost. So, this hints towards a dynamic programming approach.</p>
<p>Let us define $dp[i][j]$ as the minimum cost to make the string $T[i..j]$ using the above operations. The transitions are exactly the same as given in the statement. Let $L = (j - i + 1)$.</p>
<ol>
<li>dp[i+1][j] + cl[T[i]] * (L - 1)</li>
<li>dp[i][j-1] + cr[T[j]] * (L - 1)</li>
<li>dp[i+x][j] + kl[y] * (L - x), where $x$ is length of any string $p[y]$ such that $T[i..(i+x-1)] = p[y]$.</li>
<li>dp[i][j-x] + kr[y] * (L - x), where $x$ is length of any string $p[y]$ such that $T[(j-x+1)..j] = p[y]$.</li>
</ol>
<p>$dp[i][j]$ is clearly the minimum over all possible transitions. The time complexity of the above logic is $O(|S| * |S| * N * |P[i]|)$. This is enough to pass the first subtask.</p>
<p>But there is a small caveat while implementing the above solution. The most general way to implement dp solution is as follows:</p>
<pre><code>
for i in [0, |S|-1]:
for j in [i, |S|-1]:
calculate dp[i][j] using all transitions
</code>
</pre>
<p>But the above implementation is wrong as the transitions for $dp[i][j]$ require us to have the correct values of all $dp[x][y]$ calculated where $i <= x <= y <= j$. So, we want to calculate the dp of smaller substrings first and then extend it to bigger substrings. A working pseudo-code for the first subtask is as follows:</p>
<pre><code>
for len in [1, |T|]:
# First find for subtrings of length 1, then 2 and so on.
for i in [0, |T|-len]:
j = i + len - 1
res = dp[i+1][j] + cl[T[i]] * (len - 1)
res = min(res, dp[i][j-1] + cr[T[j]] * (len - 1))
for y in [1, n]:
x = |p[y]|
if x > len:
continue
# attach left
match = 1
for l in [0, x-1]:
if p[y][l] != T[i+l]:
match = 0
if match:
res = min(res, dp[i+x][j] + kl[y] * (len - x))
match = 1
for l in [0, x-1]:
if p[y][l] != T[j-x+1+l]:
match = 0
if match:
res = min(res, dp[i][j-x] + kr[y] * (len - x))
dp[i][j] = res
print dp[0][|T|-1]
</code>
</pre>
<h2>Full Solution:</h2>
<p>Note that in the above solution, the only time consuming step is the transitions from all possible strings $p[y]$. Since we know that the maximum length of any string $p[y]$ is atmost 100, we see that $dp[i][j]$ would take atmost 102 transitions (2 for characters). If we can do each transition in $O(1)$ then we can completely solve the problem.</p>
<p>The first thing to observe is that we have atmost 100 different strings which could be appended to the left or right while calculating the cost of a substring. Instead of iterating over all possible patterns $p[y]$, we need to efficiently find the cost of making that substring (if possible) from the set of patterns. This requires efficient string matching from a set of patterns. Below are 2 different approaches to it:</p>
<h3>Author's solution</h3>
<p>Make $2$ tries of all the patterns, one for the left side transitions and another for the right side transitions. For each node in the trie also store the minimum cost of making that string. For all nodes, it is initially $INF$, some large value. Only for nodes where a pattern $p[y]$ ends, the cost is set to the minimum of $kl[y]$ or $kr[y]$ over all possible patterns ending there (Note that there can be multiple same patterns but with different cost). To efficiently search for the cost of the substring, we simply traverse the trie and after each transition update the $dp$ values.</p>
<p>The overall time complexity of the above solution is now $O(|S| * |S| * {max}*{i=1}^{i=N} |P[i]| + \sum*{i=1}^{i=N} |P[i]|)$, where the first part is for dynamic programming calculating and the second part is for building the trie. The space complexity of the solution is $O(|S| * |S| + |N| * |P| * 26)$, where the first part is for the dynamic programming table and second is for the trie of patterns.</p>
<p>Once, you are clear with the above idea, you can see the author implementation below for help.</p>
<h3>Editorialist's solution</h3>
<p>We can use hashing for string comparison as well. So, we hash all the patterns and store the cost of them in a map. We also store the hash of text $T$ as well. Now, we calculate the cost of every substring as follows:</p>
<pre><code>
# H[S] denotes the hash of stirng S.
# mp[H[P]] stores the cost for pattern P.
for i in [0, |S|-1]:
for j in [i, |S|-1]:
w = H[S[i..j]]
if w is present in mp:
cost_l[i][j] = mp[H[P]].first
cost_r[i][j] = mp[H[P]].second
else:
cost_l[i][j] = INF
cost_r[i][j] = INF
</code>
</pre>
<p>The time complexity for the above approach is $O(\sum_{i=1}^{i=N} P[i] + |S| + |S| * |S| * \log{N} + |S| * |S| * |P|)$, where the first $2$ parts are for building the hashes, the third for the above pseudo-code ($\log{N}$ for searching the map) and last part for dynammic programming approach. The space complexity of the approach is $O(|S| * |S|)$ which is required for storing the dynammic programming table and also the cost of every substring.</p>
<p><b> NOTE: </b> For the hash based solution the string lengths are small and also the number of strings to consider i.e. $N$ are large so there can be chances of collision. So, it is preferred to use double hashing in this problem. For details refer to <a href="http://codeforces.com/blog/entry/60445">this blog</a> on codeforces.</p>
<p>Once, you are clear with the above idea, you can see the editorialist implementation below for help.</p>
<p>Feel free to share your approach, if it was somewhat different.</p>
<h1>Time Complexity</h1>
<p>$O(|S| * |S| * {max}*{i=1}^{i=N} |P[i]| + \sum*{i=1}^{i=N} |P[i]|)$ or $O(\sum_{i=1}^{i=N} P[i] + |S| + |S| * |S| * \log{N} + |S| * |S| * |P|)$</p>
<h1>Space Complexity</h1>
<p>$O(|S| * |S| + |N| * |P| * 26)$ or $O(|S| * |S|)$</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME62/setter/MKSTR.cpp">here</a>.</p>
<p>Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME62/tester/MKSTR.cpp">here</a>.</p>
<p>Editorialist's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME62/editorialist/MKSTR.cpp">here</a>.</p>likecsSat, 28 Jul 2018 16:58:49 +0530https://discuss.codechef.com/questions/132597/mkstr-editorialmediumfeketeltime62dynamic-programmingtrieslikecseditorialstring-hashingPRMDIV - Editorialhttps://discuss.codechef.com/questions/132598/prmdiv-editorial<h1>Problem Link</h1>
<p><a href="https://www.codechef.com/problems/PRMDIV">Practice</a></p>
<p><a href="https://www.codechef.com/LTIME62A/problems/PRMDIV">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/fekete">Ivan Fekete</a></p>
<p><strong>Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a></p>
<p><strong>Editorialist:</strong> <a href="https://www.codechef.com/users/likecs">Bhuvnesh Jain</a></p>
<h1>Difficulty</h1>
<p>EASY</p>
<h1>Prerequisites</h1>
<p>Sieving Techniques</p>
<h1>Problem</h1>
<p>Let $S(x)$ denote the sum of distinct prime divisors of $x$. Find the number of pairs $(i, j)$ in array $A$ such that if $A[i]$ divides $A[j]$ then $S(A[i])$ also divides $S(A[j])$.</p>
<h1>Explanation</h1>
<p>Let us first calculate the function $S$ for all integers efficiently. This is a simple modification of the prime sieve where we add the contribution each prime divisor to the numbers as well.</p>
<pre><code>
S[1] = 0
for i in [2, 1000000]:
if S[i] == 0:
# number is prime
j = i
while j <= 1000000:
S[j] += i
j += i
</code>
</pre>
<p>The time complexity of the above approach will be $O(\sum_{p = prime} X/p) = O(X \log{\log{X}})$, where $X = 1000000$.</p>
<p>Let us also calculate the good pairs of numbers. Below is a pseudo-code for it:</p>
<pre><code>
# good[i] stores the "j" such that
# "i" and "S[i]" divide "j" and "S[j]" respectively.
for i in [2, 1000000]:
j = i
while j <= 1000000:
# Ensured that "i" divides "j". See the loop conditions.
if S[j] % S[i]:
good[i].append(j)
j += i
</code>
</pre>
<p>The time complexity of the above approach is $O(\sum_{i=2}^{i=N} X/i) = O(X \log{X})$, where $X = 1000000$. If you have any doubts regarding the above 2 precomputations, I suggest you to learn and read <a href="https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes">Sieve of Eratosthenes</a> and try to understand how the code is modified here.</p>
<p>Now, coming back to the problem. We need to find the number of pair of $(i, j)$ in array $A$ such that if $A[i]$ divides $A[j]$ then $S(A[i])$ also divides $S(A[j])$. For this, if we do it naively for every pair using the help of above pre-computation to check if $A[i]$ and $A[j]$ is good, then it will inefficient and only pass subtask 1.</p>
<p>The important thing to note that even if we iterate over all "good" arrays, the total size of all arrays is bounded by $O(X \log{X})$, considering all the numbers are appended. Actually, this bound is lower, but it doesn't matter.</p>
<p>So, let say if we have the frequency of all elements in the array $A$. When iterating over the "good" array, if $2$ numbers have frequency $x$ and $y$ then they contribute $(x * y)$ to the answer. The only caveat is that pair $(i, i)$ i.e. same pair of indices is also counted in it. So, we need to subtract $N$ from the final answer as well.</p>
<p>Thus, the below psuedo-code can easily solve our complete problem:</p>
<pre><code>
for i in [1, n]:
freq[a[i]] += 1
ans = 0
for i in [2, 1000000]:
if freq[i] > 0:
# Element is present
for j in good[i]:
ans += freq[i] * freq[j]
# Account for i == j
ans -= n
print ans
# Clear freq array for next test case.
for i in [1, n]:
freq[a[i]] -= 1
</code>
</pre>
<p>Once, you are clear with the above idea, you can see the editorialist implementation below for help.</p>
<p>Feel free to share your approach, if it was somewhat different.</p>
<h3>Some Thoughts</h3>
<p>There exist a linear sieve for prime numbers as well. Can you modify the first algorithm for pre-computation of $S$ to work in linear time? If yes, how? If no, what is your counter argument?</p>
<h1>Time Complexity</h1>
<p>$O(X \log{X} + N)$ per test case.</p>
<h1>Space Complexity</h1>
<p>$O(X \log{X})$</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME62/setter/PRMDIV.cpp">here</a>.</p>
<p>Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME62/tester/PRMDIV.cpp">here</a>.</p>
<p>Editorialist's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME62/editorialist/PRMDIV.cpp">here</a>.</p>likecsSat, 28 Jul 2018 17:31:36 +0530https://discuss.codechef.com/questions/132598/prmdiv-editorialeditorialfeketeltime62likecseasysieveGCDSUM - Editorialhttps://discuss.codechef.com/questions/132595/gcdsum-editorial<h1>Problem Link</h1>
<p><a href="https://www.codechef.com/problems/GCDSUM">Practice</a></p>
<p><a href="https://www.codechef.com/LTIME62A/problems/GCDSUM">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/fekete">Ivan Fekete</a></p>
<p><strong>Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a></p>
<p><strong>Editorialist:</strong> <a href="https://www.codechef.com/users/likecs">Bhuvnesh Jain</a></p>
<h1>Difficulty</h1>
<p>EASY-MEDIUM</p>
<h1>Prerequisites</h1>
<p>GCD, Inclusion-exclusion, Counting</p>
<h1>Problem</h1>
<p>Given a matrix of size $(N, M)$. Select $K$ rows in increasing order and then a cell from each selected row. Find the GCD of the selected numbers.</p>
<p>We need to find the sum of GCD of all possible ways of selecting rows and cells.</p>
<h1>Explanation</h1>
<p>We don't have any special property to GCD which helps us to extend the value when both adding or removing a particular number. Instead, we know that GCD of 2 numbers which divide both the numbers and also the divisors of GCD will also divide both the numbers. So, using this intuition, let us define $2$ arrays as follows:</p>
<p>$A[d]$ denotes the numbers of ways to get the GCD of selected numbers as divisible by $d$.</p>
<p>$B[d]$ denotes the numbers of ways to get the GCD of selected numbers as exactly $d$.</p>
<p>Suppose, we are able to efficiently calculate array $A$, then we can simply find array $B$ and the final answer using the below pseudo-code:</p>
<pre><code>
ans = 0
for d from 10^5 to 1:
v = A[d]
x = 2 * d
while x <= 10^5:
v -= B[x]
x += d
B[d] = v
ans += d * B[d]
print ans
</code>
</pre>
<p>The idea for the above pseudo-code is as follows:</p>
<ol>
<li>We iterate in reverse order. So, say we are at given $d$, then we have the correct value of $B[x]$ calculated for all $x > d$.</li>
<li>Since, $A[d]$ stores the number of ways when GCD is divisible by $d$, we just subtract that contribution of the divisors of $d$ using the array $B$. This is because $B[x]$ stores the number of ways when GCD is exactly $x$.</li>
<li>Since we know the number of ways to obtain a particular GCD, we can simply sum over the product of $d$ and $B[d]$ to get the final answer.</li>
</ol>
<p>The time complexity for this part is $O(X \log{X})$, where $X$ is the maximum element in the array i.e. ${10}^{5}$.</p>
<p>So, our task is now reduced to finding array $A$ efficiently.</p>
<p>Since we want the final GCD to be divisible by $d$, it means that all the numbers under consideration should be divisible by $d$. So, the task is to find the numbers of ways of selecting some rows and then cells from them such that each cell is divisible by $d$.</p>
<p>First, let us calculate the number of ways to select a number divisible by $d$ from a row. Doing this naively means to iterate over all divisors of a given number and adding it's contribution to the particular row. This will take $O(N * M * \sigma{(A[i][j])})$, where $\sigma{(A[i][j])}$ denotes the number of divisors of $A[i][j]$ which can be atmost 128 as all numbers as less than ${10}^5$. But this is slow. Instead, we can use the below pseudo-code to efficiently calculate this:</p>
<pre><code>
# freq[i][d] denotes frequency of numbers divisible by "d" in row "i"
for i in [1, n]:
for j in [1, m]:
freq[i][A[i][j]] += 1
for d in [1, 10^5]:
j = 2*d
while j <= 10^5:
freq[i][d] += freq[i][j]
j += d
</code>
</pre>
<p>The idea is simply to calculate the frequency of each number in a row and then simultaneouly update all the divisors than to individually update the row when scanning a cell. Using the above pseudo-code the complexity becomes $(N * M + N * (X/1 + X/2 + \cdots + 1))$ = $O(N * M + N * X * \log{X})$, where $X$ is the maximum element in the array i.e. ${10}^{5}$.</p>
<p>Now, we have the frequency of numbers divisible by $d$ in each row. We need to find the numbers of ways to select some rows first and some cells the rows. Let us assume we have 4 rows with the number of cells divisible by $d$ as $w, x, y, z$ respectively. The number of ways is:</p>
<ol>
<li>Selecting 2 rows: $wx + wy + wz + xy + xz + yz$.</li>
<li>Selecting 3 rows: $wxy + wxz + wyz + xyz$.</li>
<li>Selecting 4 rows: $wxyz$.</li>
</ol>
<p>This can be written as $w * (x * (y + z + yz) + y + z + yz + x) + x * (y * z + y + z) + y * z$. See how the terms can be derived from the successive terms as most of it is same. For example, The first term in the bracket for $w$ is the same as the successive terms and the other term is similar to the term in the bracket of $x$. This idea is used by the editorialist in his solution.</p>
<p>Other idea is to consider the product: $(1 + w) * (1 + x) * (1 + y) * (1 + z)$ and see how it relates to above terms we requires. The idea for choosing such term is as follows: Either we chose the term $w,x, y, z$ ways or we ignore it $1$ way. We can clearly see that the product only contains the extra terms of selecting exactly 1 row or none of the rows. So, in the above product, if we remove this contribution, we get our desired result. The author and tester have used this idea in their solution.</p>
<p>Thus, we are able to calculate array $A$ efficiently as well. The time complexity of the above approach for calculating array $A$ is $O(N * M + N * X * \log{X} + N * X)$ where the first $2$ terms are for calculating the frequencies and the last term is to calculate the array from the frequency table.</p>
<p>The overall time complexity of the solution is $O(N * M + N * X * \log{X} + N * X + X * \log{X})$. The space complexity is $O(N * M + N * X + X)$, where first term is for the matrix, the second term for the frequency table and the last terms for the arrays $A$ and $B$.</p>
<p>Once, you are clear with the above idea, you can see the author or editorialist implementation below for help.</p>
<p>Feel free to share your approach, if it was somewhat different.</p>
<h1>Time Complexity</h1>
<p>$O(N * M + N * X * \log{X} + N * X + X * \log{X})$</p>
<h1>Space Complexity</h1>
<p>$O(N * M + N * X + X)$</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME62/setter/GCDSUM.cpp">here</a>.</p>
<p>Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME62/tester/GCDSUM.cpp">here</a>.</p>
<p>Editorialist's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME62/editorialist/GCDSUM.cpp">here</a>.</p>likecsSat, 28 Jul 2018 16:55:47 +0530https://discuss.codechef.com/questions/132595/gcdsum-editorialinclusn-exclusngcdfeketeltime62likecseditorialcountingeasy-mediumFRCPRT - Editorialhttps://discuss.codechef.com/questions/132603/frcprt-editorial<h1>Problem Link</h1>
<p><a href="https://www.codechef.com/problems/FRCPRT">Practice</a></p>
<p><a href="https://www.codechef.com/LTIME62A/problems/FRCPRT">Contest</a></p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/fekete">Ivan Fekete</a></p>
<p><strong>Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a></p>
<p><strong>Editorialist:</strong> <a href="https://www.codechef.com/users/likecs">Bhuvnesh Jain</a></p>
<h1>Difficulty</h1>
<p>EASY-MEDIUM</p>
<h1>Prerequisites</h1>
<p>Looping Techniques, Observations</p>
<h1>Problem</h1>
<p>You are given a matrix $A$ of size $(N, M)$ consisting of $0$ and $1$. We apply forces on the matrix according to a given string $S$. On applying the force on left, right, up or down direction, the cells with $1$ move in the required direction till they either reach the end of the matrix or find another $1$ lying directly adjacent to them.</p>
<p>Find the final configuration of the matrix.</p>
<h1>Explanation</h1>
<p>For the first subtask, just applying the operations as mentioned in the statement will be enough. For applying force to right or left, we just need to find how many $1$ are present in a row and then shift them all right or left respectively. Similarly, for applying the force to up or down, we just need to find how many $1$ are present in a column and then shift them all up or down respectively.</p>
<p>The time complexity of this approach will be $O(N * M * |S|)$ per test case. For proceeding towards the final solution, let us make some observations.</p>
<p>Let us apply the first operation, i.e. $S[0]$. After this, all the cells shift to one side/corner of the matrix. It is clear that up and down operations affect cells in the column direction while left and right operations affect cells in the row direction. Thus, we can take a look at their properties together.</p>
<p>Now, let us consider sequences of operations consisting of up(U) and down(D) operations only. (The similar result applies to left and right moves as well).</p>
<ol>
<li>UUUU...... or DDDD.....: It is sufficient to apply the operation only once as the future operations have no effect on the configuration of the matrix.</li>
<li>UDUD.... or DUDU......: It is sufficient to apply the last operation only as it will affect the final configuration, the previous one has no effect as it will be overridden by future operations.</li>
</ol>
<p>Now, let us consider what happens when we apply both operations together. The first thing to note that the first operation is applied always. This is because now 2 adjacent cells in the row will move together and 2 adjacent cells in the column will move together. This is not the case if the first operation is not applied as the cell with $1$ can move arbitrary steps in either direction due to the presence of $0$ in adjacent cells.</p>
<p>When we apply a left or right operation after up or down operation, the number of cells in row shift towards columns. To understand this, consider the movement of cells in below matrix on applying down operation:</p>
<p></p><center><img height="100" src="https://discuss.codechef.com/upfiles/force1.png" width="250"></center><p></p>
<p></p><center><img height="100" src="https://discuss.codechef.com/upfiles/force2.png" width="250"></center><p></p>
<p>We can consider the above operation as transpose operation where for each row add $1$ to all column from $1$ to $row[i]$ where $row[i]$ denotes number of $1$ in it. Thus, instead of explicitly setting the cells to $0$ and $1$ as in brute force solution, we can just maintain the number of $1$ in each row and column.</p>
<p>Once, you get an idea of the above logic you can see editorialist solution below for more details. The complexity is now $O(|S| * (N + M))$. This is better than the previous solution but still not sufficient to pass full solution. (Note that in the solution the transpose_row or transpose_col does the addition in a range and calculating the final array.)</p>
<p>Now, once you see the solution above, you can clearly see that we apply transpose operations only one by one. Using this, we get the idea that again only the last operations for left/right and up/down matter as the transpose operation done $2$ times leads us to the same state.</p>
<p>So, the final solution is just to apply the first operation and then apply the last left/right operation and up/down operation in order. Thus, the length of the string $S$ can be effectively reduced to atmost $3$. Now we just apply the brute operations.</p>
<p>The complexity of the above algorithm is $O(|S| + N * M)$. The first one is for traversing the string |S| for determining the $3$ important operations and the last one is for applying the operations.</p>
<p>Once, you are clear with the above idea, you can see the author implementation below for help.</p>
<p>Feel free to share your approach, if it was somewhat different.</p>
<h1>Time Complexity</h1>
<p>$O(N * M + |S|)$ per test case.</p>
<h1>Space Complexity</h1>
<p>$O(N * M + |S|)$</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME62/setter/FRCPRT.cpp">here</a>.</p>
<p>Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME62/tester/FRCPRT.cpp">here</a>.</p>
<p>Editorialist's solution can be found <a href="https://ideone.com/cGWojA">here</a>. (Will give TLE for subtask 2)</p>likecsSat, 28 Jul 2018 21:18:26 +0530https://discuss.codechef.com/questions/132603/frcprt-editorialfeketeltime62observationseditoriallikecseasy-medium