Questions Tagged With cook59https://discuss.codechef.com/tags/cook59/?type=rssquestions tagged <span class="tag">cook59</span>enSat, 20 Jun 2015 18:18:12 +0530ANKPAREN - Editorialhttps://discuss.codechef.com/questions/71904/ankparen-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/ANKPAREN">Practice</a> <br>
<a href="http://www.codechef.com/COOK59/problems/ANKPAREN/">Contest</a></p>
<p>Author: <a href="http://www.codechef.com/users/code_master01">Ankit Srivastava</a> and <a href="http://www.codechef.com/users/code_note">Uttam Kanodia</a><br>
Tester: <a href="http://www.codechef.com/users/rubanenko">Roman Rubanenko</a> <br>
Editorialist: <a href="http://www.codechef.com/users/amitpandeykgp">Amit Pandey</a> </p>
<h1>DIFFICULTY:</h1>
<p>Easy-Medium</p>
<h1>PREREQUISITES:</h1>
<p>Basic programming</p>
<h1>PROBLEM:</h1>
<p>Given a string containing '(' and ')' only. Find the longest such subsequence of the given string that is non-regular. Amongst all such distinct answers, output the lexicographically $K^{th}$ amongst them.</p>
<h1>QUICK EXPLANATION:</h1>
<p>If the given string in not balanced, then the string itself is the largest non-regular(unbalanced) pattern. On the contrary, if the given string is regular(balanced), then all subsequnces having length $(N-1)$ will be non-regular and there is a pattern in their lexicographic ordering.</p>
<h1>EXPLANATION:</h1>
<p>The problem can be broadly classified into two cases:</p>
<p><strong>Case I:</strong> Given parenthesis string is not balanced, which can be checked using stack data structure described <a href="http://www.ardendertat.com/2011/11/08/programming-interview-questions-14-check-balanced-parentheses/">here</a>. In this case, the largest unbalanced sub-sequence will be then the given string itself. So if $K=1$, then the answer will be the given string, $-1$ otherwise.</p>
<p><strong>Case II:</strong> Given parenthesis string is the balanced one. Consider that $L$ is the length of the given string, then there will $L$ sub-sequences of length $(L-1)$, and each of them will be unbalanced. This is because, in any sub-sequence, number of opening and closing parenthesis will not be the same.</p>
<p><strong>How to find the number of distinct unbalanced sub sequences?</strong></p>
<p>Consider a string $S$ = "(())", what will be number of distinct unbalanced sub-sequences? it can be easily claimed that if we delete $S[0]$ or $S[1]$, we will get same string i.e. "())". So, it can be seen easily that if we delete any character from a contiguous chunk of the characters, we will get same unbalanced sub-sequence. It can be formally written as follows:</p>
<p>Consider the any contiguous chunk of same characters in the given string, Suppose $S[i] = S[i+1] = S[i+2] =\ ....\ = S[j] =\ '('$ or $')'$. If we delete any character between $i^{th}$ and $j^{th}$ positions (both inclusive), it will produce the same sub-sequence, because deleting any of them will replace $(j-i)+1$ number of same characters by $(j-i)$ number of same characters. So number of distinct sub-sequences of length $(L-1)$ will be number of different contiguous chunks of same characters. For example, string $(())((()))$ will have $4$ distinct sub-sequence of length $9$, and each of them will be unbalanced. </p>
<p><strong>How to do lexicographic ordering of those sub-sequences?</strong></p>
<p>Suppose that the string which we generate by deleting a character from the $i^{th}$ chunk (0-indexed) is $L_i$. As our given string is balanced, it will consist of one or more opening parentheses and one or more closing parentheses alternatively (starting with opening). So, to produce $L_{2n}$ we need to delete an opening parenthesis, and to produce $L_{2n+1}$, we need to delete a closing parenthesis. Now, let me claim that the lexicographic ordering:</p>
<p>$$L_{2i+1} < L_{2j+1}, \hspace{2 mm} L_{2i} > L_{2j} \hspace{2 mm} for \hspace{2 mm} (i < j) $$
$$L_{2i+1} < L_{2j} \hspace{2 mm} \text{for all} \hspace{2 mm}(i,j) $$</p>
<p>So for string $S = ''(())()((()))(())"$, the lexicographic order will be $L_1 < L_3 < L_5 < L_7 < L_6 < L_4 < L_2 < L_0$. To produce lexicographically $3^{rd}$ string we need to produce $L_5$ by deleting any of the bold characters : "(())()(((<strong>)))</strong>(())".</p>
<p><strong>Proof:</strong>
Consider the proof $L_{2i+1} < L_{2j+1},\hspace{2 mm} \forall \hspace{2 mm} (i < j)$. Others can be proved in the same manner.</p>
<p>Consider that the $i^{th}$ chunk has $A_i$ number of characters. Now consider the $(A_1 + A_2 + .... A_{2i+1})^{th}$ character in $L_{2i+1}$ and $L_{2j+1}$, it will be ')' in $L_{2j+1}$, as $i < j$, and it will remain the same as in the original string, but it will be '(' in $L_{2i+1}$ and all previous characters will be the same in both of the strings. As opening parenthesis is lexicographically smaller than closing parenthesis, hence $L_{2i+1} < L_{2j+1}$.</p>
<h1>Solution:</h1>
<p>Setter's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK59/Setter/ANKPAREN.cpp">here</a> <br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK59/Tester/ANKPAREN.cpp">here</a></p>amitpandeykgpFri, 19 Jun 2015 16:38:13 +0530https://discuss.codechef.com/questions/71904/ankparen-editorialpatterneasy-mediumankparenbasic-progcook59stackANKGAME - Editorialhttps://discuss.codechef.com/questions/71815/ankgame-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/ANKGAME">Practice</a> <br>
<a href="http://www.codechef.com/COOK59/problems/ANKGAME/">Contest</a></p>
<p>Author: <a href="http://www.codechef.com/users/code_master01">Ankit Srivastava</a> and <a href="http://www.codechef.com/users/code_note">Uttam Kanodia</a><br>
Tester: <a href="http://www.codechef.com/users/rubanenko">Roman Rubanenko</a> <br>
Editorialist: <a href="http://www.codechef.com/users/amitpandeykgp">Amit Pandey</a> </p>
<h1>DIFFICULTY:</h1>
<p>Easy-Medium.</p>
<h1>PREREQUISITES:</h1>
<p>Game theory and Combinatorics.</p>
<h1>PROBLEM:</h1>
<p>A game is played with the rule that a non-zero number of the stones must be removed from the first non-empty pile. Find the number of permutations of the piles, in which the first player has a winning strategy. </p>
<h1>QUICK EXPLANATION:</h1>
<p>Find a way to check if a given permutation is the winning permutation, followed by finding the number of permutations which satisfy the given condition. </p>
<h1>EXPLANATION:</h1>
<p>The problem can be solved using various claims.</p>
<p><strong>Claim 1: If each pile contains exactly $1$ stone. Now, if number of piles is even, then second player will win. Otherwise, first player will win.</strong></p>
<p><strong>Reason:</strong> The reason being that each player will have exactly one way of making a move, i.e. emptying the current pile.</p>
<p><strong>Claim 2: If the first pile contains more than one stone, then first player will always win.</strong></p>
<p><strong>Reason:</strong> Suppose that piles are numbered as $1,2,3...N$. Number of stones in piles are given as $A_1,A_2,....A_N$ with the condition $A_1 \ge 2$. </p>
<p><strong>Case 1:</strong> Suppose in piles $A_2,A_3,...A_N$, first player has winning strategy, then first player will remove $A_1-1$ number of stones from the first pile and second player will be enforced to remove remaining $1$ stone. First player will have winning strategy on remaining piles.</p>
<p><strong>Case 2:</strong> Suppose in piles $A_2,A_3,...A_N$, first player doesn't have winning strategy, then first player will empty first pile in single move. So, when game will arrive as pile $2$, second player will not have the winning strategy, hence first player will have winning strategy. </p>
<p><strong>Claim 3:</strong> Now we can claim very easily that first player will win if permutation is in such a way that $A_1 = 1, A_2 = 1,... A_x = 1, A_{x+1} != 1$, and $x$ is an even number, because when the game will arrive at pile number $(x+1)$, first player will be making first move and he will win according the points given above.</p>
<p><b>How to count number of permutations such that number of 1's in the beginning is even? </b></p>
<p>Suppose count of $1$'s in the array $A$ is $M$. Each distinct number of array $A$(except 1) is in array $B$, i.e., $B_1, B_2,...B_K$, and count of $B_i$ in array $A$ is $cnt[B_i]$.</p>
<p>Now count the number of permutations in which number of 1's in the beginning is <b>at least</b> $x$. To do that, keep $x$ $1's$ in the beginning and permute rest of the numbers.</p>
<p>$$W(x) = \frac{(N-x)!}{(M-x)!\ cnt[B_1]!\ cnt[B_2]!\ ....\ cnt[B_K]!} $$</p>
<p>$$\text{Consider } K = \frac{1}{cnt[B_1]!\ cnt[B_2]!\ ....\ cnt[B_K]!} $$</p>
<p>$$So, W(x) = \frac{K\times(N-x)!}{(M-x)!} $$</p>
<p>Number of permutations in which number of $1's$ in the beginning is exactly $2r$.</p>
<p>$$ Ways(2r) = W(2r) - W(2r+1)$$</p>
<p>So, number of permutations in which numbers of 1's in the beginning is even:</p>
<p>$$ \text{Number of permutations} = \sum_{r=0}^{2r+1 \le M} Ways(2r) $$</p>
<p>$K$ is a constant which can be calculated in $O(N)$ time, and we can calculate it in the beginning. So, Number of permutations can also be calculated in $O(N)$ time. </p>
<h1>Solution:</h1>
<p>Setter's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK59/Setter/ANKGAME.cpp">here</a> <br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK59/Tester/ANKGAME.cpp">here</a></p>amitpandeykgpWed, 17 Jun 2015 10:24:29 +0530https://discuss.codechef.com/questions/71815/ankgame-editorialcombinatoricsgame-theoryeasy-mediumcountingcook59ankgameANKNIM2 - Editorialshttps://discuss.codechef.com/questions/71876/anknim2-editorials<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/ANKNIM2/">Practice</a> <br>
<a href="http://www.codechef.com/COOK59/problems/ANKNIM2/">Contest</a></p>
<p>Author: <a href="http://www.codechef.com/users/code_master01">Ankit Srivastava</a> and <a href="http://www.codechef.com/users/code_note">Uttam Kanodia</a><br>
Tester: <a href="http://www.codechef.com/users/rubanenko">Roman Rubanenko</a> <br>
Editorialist: <a href="http://www.codechef.com/users/amitpandeykgp">Amit Pandey</a> </p>
<h1>DIFFICULTY:</h1>
<p>Medium</p>
<h1>PREREQUISITES:</h1>
<p>Fast Fourier Transform. </p>
<h1>PROBLEM:</h1>
<p>Given an array of $N$ integers. You have to find count of all subarrays of size $m$, such that if a <a href="https://en.wikipedia.org/?title=Nim">Nim Game</a> is played on the subarray, second player will win. Do it for all possible values of $m$, $1 \le m \le N$.</p>
<h1>EXPLANATION:</h1>
<p>It can be claimed using <a href="https://en.wikipedia.org/?title=Nim">Nim Game</a> theory that second player will win the game if $XOR$ of the selected subarray is $0$. We can find XOR of any subarray in $O(1)$ time by creating a prefix XOR array.</p>
<p>$$ preXOR[0] = 0 \hspace{3 mm}\& \hspace{3 mm}preXOR[i] = A[0] \oplus A[1] \oplus \cdots \oplus A[i-1]$$</p>
<p>$$ A[i] \oplus A[i+1] \oplus \cdots A[j] = preXOR[i-1] \oplus preXOR[j]$$.</p>
<p>Now, let me present an $O(N^2)$ solution for the problem. </p>
<pre><code>answer[n] = 0;
for i in range(0,n):
for j in range(i+1,n):
if preXOR[i] == preXOR[j]: //subarray having size (j-i) has XOR 0.
answer[j-i]++;
</code></pre>
<p>Consider a number $k$. If it appears $l$ times in the $preXOR$ array, then there will be $^lC_2$ subarrays in array $A$ whose XOR is zero. We can create an array corresponding to indices of $k$ in $preXOR$ array, and call it $S$. It means $preXOR[S[i]] = k$ for all $i < l$. </p>
<pre><code> for i = 0 to l-1:
for j= i+1 to l-1:
ans[j-i]++; // there is a subarray of size (j-i) having XOR 0.
</code></pre>
<p>It can be explained further,Consider that preXOR array is $[1,2,3,1,1,4,1]$, then the array $S$ for $k=1$ will be $[0,3,4,6] \text{(0 based indexing)}$.</p>
<p>The above solution can take up to $O(N^2)$ time in the worst case, as size of $S$ can be $O(N)$. To improve it, we can do the following modifications:</p>
<p>1) If size of the array $S$ is lesser than $\sqrt{N}$, then we can use brute force as given above.</p>
<p>2) If size of the array $S$ is greater than $\sqrt{N}$, then the above solution will take more time. So, we can use the FFT to optimize the solution to time $Nlog(N)$.</p>
<p>Number of sub-arrays of size $K$ having XOR $0$, will be coefficient of $x^K$ in following polynomial:</p>
<p>$$(x^{S[0]} + x^{S[1]} + \cdots + x^{S[L-1]}) (x^{-S[0]} + x^{-S[1]} + \cdots + x^{-S[L-1]})$$</p>
<p>The powers of $x$ in the above polynomial are negative as well, therefore we do a small modification in above polynomial to make all the powers positive. It will be equivalent to the coefficient of $x^{N+K}$ in the following polynomial:</p>
<p>$$(x^{S[0]} + x^{S[1]} + \cdots + x^{S[L-1]}) (x^{N-S[0]} + x^{N-S[1]} + \cdots + x^{N-S[L-1]})$$</p>
<p>Which can be done in $O(Nlog(N))$ time using Fast Fourier transform. The FFT will give answer corresponding to all possible value of $m$ altogether. </p>
<p>We can repeat the above procedure for each distinct element $k$ of $preXOR$ array. The total count of subarrays corresponding to each value of $m$ will be the count of subarrays of size $m$ for each distinct value of $k$. </p>
<p>Worst case complexity of the above procedure will be $O(N \sqrt{N} \log{(N)})$.</p>
<p><b>Problems to solve:</b></p>
<ol>
<li><a href="http://www.codechef.com/problems/FARASA">FARASA</a></li>
</ol>
<h1>Solution:</h1>
<p>Setter's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK59/Setter/ANKNIM2.cpp">here</a> <br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK59/Tester/ANKNIM2.cpp">here</a></p>amitpandeykgpThu, 18 Jun 2015 15:19:26 +0530https://discuss.codechef.com/questions/71876/anknim2-editorialsgame-theoryfftcook59anknim2medium-hardANKMARKS - Editorialshttps://discuss.codechef.com/questions/71951/ankmarks-editorials<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/ANKMARKS">Practice</a> <br>
<a href="http://www.codechef.com/COOK59/problems/ANKMARKS/">Contest</a></p>
<p>Author: <a href="http://www.codechef.com/users/code_master01">Ankit Srivastava</a> and <a href="http://www.codechef.com/users/code_note">Uttam Kanodia</a><br>
Tester: <a href="http://www.codechef.com/users/rubanenko">Roman Rubanenko</a> <br>
Editorialist: <a href="http://www.codechef.com/users/amitpandeykgp">Amit Pandey</a> </p>
<h1>DIFFICULTY:</h1>
<p>Medium</p>
<h1>PREREQUISITES:</h1>
<p>Matrix Exponentiation</p>
<h1>PROBLEM:</h1>
<p>There are $N$ students and the marks awarded to any student should be linear combination of the elements of a given set, while satisfying other constraints as well. Find the minimum average of the marks which can be allotted to the students. In other words, find the minimum possible class average.</p>
<h1>EXPLANATION:</h1>
<p>There are various steps in solving the given problem. Let's go through them one by one.</p>
<p>Let us call the given set of marks as $S$. First of all, let's make a function $check(x)$ which will tell if a given number $x$ can be awarded as a score to any of the students. Since the score is a linear combination of the elements of $S$, a score $x$ can be allotted iff any of the marks among $x-S[0], x-S[1], .... , x-S[k-1]$ can be allotted, or if $x=0$, the base case. Thus, $\forall x>0$,</p>
<p>$$check(x) = check(x-S[0]) \hspace{2 mm}or\hspace{2 mm} check(x-S[1]) \hspace{2 mm}or\hspace{2 mm} ... \hspace{2 mm}or \hspace{2 mm}check(x-S[k-1]) $$</p>
<p>It is given that the answer to the problem will be at most $2^{52}$, so we need to check up to $2^{52} \times 1000 \approx 2^{62}$, which is a very large number and can be checked using <a href="http://zobayer.blogspot.in/2010/11/matrix-exponentiation.html">matrix exponentiation</a> technique. This method will take $O(50^3 \times \log{x})$ time. There is another excellent way of computing $check(x)$, which uses <a href="https://en.wikipedia.org/?title=Dijkstra%27s_algorithm">Dijkstra's Algorithm</a>. It has been described <a href="https://www.hackerrank.com/contests/csindia14-er1/challenges/fill-the-tank/editorial">here</a> in a nice way. See <a href="http://www.codechef.com/download/Solutions/COOK59/Tester/ANKMARKS.cpp">tester's code</a> for this approach. </p>
<p>Now, for any given score, we can check if it can be allotted to a student, or not. So, let's make a list which contains all the scores which can be allotted. As we have to find the minimum average, we will try to allot minimum possible marks to each of the students. Minimum marks which can be allotted is $0$. Second minimum marks which can be allotted is the minimum element of the set $S$. Now, suppose someone has received $x$ marks, the guy which is located next to him should be allotted more than $2x$ marks. So, we will keep checking if $2x+1,2x+2,...$ can be allotted and allot the minimum possible marks. Now, we can make a allotment list $L$, which is the list of marks to be allotted to all the students in the class. $L[i]$ can be calculated as follows:</p>
<p>$$L[0] = 0, \hspace{2 mm} L[1] = min(S), \hspace{2 mm}L[i] = min(x) \hspace{2 mm} \text{such that} \hspace{2 mm} x \ge 2L[i-1] +1 \hspace{2 mm} \& \hspace{2 mm} check(x) = true .$$</p>
<p>Now, final part of the solutions is the calculation of the exact score allotted to each student: </p>
<p>Pick each of the local minimum elements of the favorite array one by one. For each local minimum, allot the corresponding student $0$ marks. Keep going to the right of it as long as the favorability is increasing, and keep allotting the next element of the list $L$. Repeat the process in the left of the local minimum. Now, there will be multiple allotments at the same position corresponding to the each of the local minimum. To satisfy all conditions, every student will receive maximum marks among all the marks allotted corresponding to each local minimum of the array. </p>
<p>Once every student has received their marks, average calculation is easy.</p>
<h1>Solution:</h1>
<p>Setter's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK59/Setter/ANKMARKS.cpp">here</a> <br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK59/Tester/ANKMARKS.cpp">here</a></p>amitpandeykgpSat, 20 Jun 2015 18:18:12 +0530https://discuss.codechef.com/questions/71951/ankmarks-editorialscook59ankmarksmedium-hardmatrix-expoUTMOPR - Editorialhttps://discuss.codechef.com/questions/71854/utmopr-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/UTMOPR">Practice</a> <br>
<a href="http://www.codechef.com/COOK59/problems/UTMOPR/">Contest</a></p>
<p>Author: <a href="http://www.codechef.com/users/code_master01">Ankit Srivastava</a> and <a href="http://www.codechef.com/users/code_note">Uttam Kanodia</a><br>
Tester: <a href="http://www.codechef.com/users/rubanenko">Roman Rubanenko</a> <br>
Editorialist: <a href="http://www.codechef.com/users/amitpandeykgp">Amit Pandey</a> </p>
<h1>DIFFICULTY:</h1>
<p>Cakewalk</p>
<h1>PREREQUISITES:</h1>
<p>Basic programming</p>
<h1>PROBLEM:</h1>
<p>Given an array of $n$ integers, you have to do the following operation $K$ times: Insert a number in the array which is strictly greater than current sum of the array. You have to find whether the last number inserted is even or odd.</p>
<h1>QUICK EXPLANATION:</h1>
<p>As the value of $K$ is small, we can keep inserting smallest possible numbers at each step and print the $K^{th}$ number modulo $2$. </p>
<h1>EXPLANATION:</h1>
<p>This problem can be solved by simulating the operation given in the problem.</p>
<p>First find the sum of the given array($A$) . This can be done in $O(N)$ time using a single loop. As we have to print the $K^{th}$ element to be inserted (modulo $2$), we can replace $S$ by $S\ \% \ 2$.</p>
<pre>S = 0;
for(int i=0; i< n; i++)
S = S + A[i];
S = S%2;
</pre>
<p>Now make an array $B$ of size $(K+1)$, $B_i$ will denote the $i^{th}$ element to be inserted, and $B_K$ will be our required answer. At any step, if parity of the sum of the elements of array is "even", parity of inserted element will be "odd".</p>
<pre>B[1] = (S + 1) % 2 ; // we will insert the smallest possible number at each step
total_sum = 0;
for(int i=2 ; i< K ; i++)
{
total_sum = (total_sum + B[i-1]);
B[i] = (total_sum + 1) % 2; // insert a number greater than current sum of the array.
}
</pre>
<p>Finally we can output $B_K$. The time complexity of the whole code will be $\mathcal{O}(N + K)$. </p>
<p><strong>Another solution</strong><br>
Let us say that sum of the array $A$ is even. The next inserted element will be odd, now sum of array will be odd, so next inserted element will be even, now sum of array becomes odd, so we will insert an even number, and so on. So we can generalize that if sum of array is even, then for $K = 1$, last inserted number will be odd, otherwise it will be even.</p>
<p>Now, we will consider the case in which sum of the array $A$ is odd. The next inserted element will be even, now sum of array will become odd, so next inserted element will be even, now sum of array will be odd, we will add another even number, and so on. So we can generalize that last inserted number is always even in this case.</p>
<p>So finally, we can obtain the following simple solution.
</p><pre>Compute sum of array.
If K = 1:
if sum is even:
print "odd"
else:
print "even"
else:
print "even"
</pre><p></p>
<h1>Solution:</h1>
<p>Setter's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK59/Setter/UTMOPR.cpp">here</a> <br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK59/Tester/UTMOPR.cpp">here</a></p>amitpandeykgpWed, 17 Jun 2015 22:56:21 +0530https://discuss.codechef.com/questions/71854/utmopr-editorialbasic-progutmoprcook59cakewalksimulation