Questions asked by amitpandeykgphttps://discuss.codechef.com/questions/asked-by/6594/amitpandeykgp/?type=rssQuestions asked by <a href="/users/6594/amitpandeykgp" >amitpandeykgp</a>enSat, 20 Jun 2015 18:18:12 +0530AMR14C -Editorialhttps://discuss.codechef.com/questions/61687/amr14c-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/AMR14C">Practice</a><br>
<a href="http://www.codechef.com/AMR14ROS/problems/AMR14C">Contest</a></p>
<h1>DIFFICULTY:</h1>
<p>EASY.</p>
<h1>PREREQUISITES:</h1>
<p>Hashing</p>
<h1>PROBLEM:</h1>
<p>Given an array, find out pair of numbers such their sum modulo <strong>M</strong> is less than or equal to <strong>X</strong>.</p>
<h1>QUICK EXPLANATION:</h1>
<p>As the naive solution will have time complexity of <strong>O(n<sup>2</sup>)</strong> which will not pass, So we can make a count array A, where A[p] = count of numbers whose value modulo <strong>M</strong> is <strong>p</strong> and we can check if first number module <strong>M</strong> is <strong>p</strong>, then in how many ways we can select another number. The time complexity of above solution will be <strong>O(M+N)</strong>.</p>
<h1>EXPLANATION:</h1>
<p>Array <strong>A</strong> contains economy rates of the bowlers.<br><br>
The naive solution will look like:<br> </p>
<pre><code> long long int answer = 0;
for(int i =0 ; i < N ; i++)
for(int j = 0 ; i< N ; j++)
if( (A[i] + A[j] <= x)
answer++;
cout<<answer<<endl;
</code></pre>
<p>But the given solution has time complexity O(n<sup>2</sup>) which will not pass in the given time limit.<br></p>
<p>As you can notice that, the value of <strong>M</strong> is not large and a solution having time complexity of <strong>O(M)</strong> will pass.<br></p>
<p><strong> An O(M<sup>2</sup>) approach: </strong></p>
<p>Make an array <strong>B</strong>. where<br></p>
<p>B[k] = count of numbers in array <strong>A</strong> which has value of <strong>k</strong> on taking modulo <strong>M</strong>.</p>
<p>Now another naive approach can be written in following manenr having time-complexity of <strong>O(M<sup>2</sup>)</strong>.</p>
<pre><code> long long int answer = 0;
for(int i = 0 ; i< M ; i++)
for(int j = 0 ; j< M ; j++)
if( (i+j)%M <= x)
answer += B[i]*B[j];
cout<<answer<<endl;
</code></pre>
<p>In this approach, we are taking all such number, whole modulo <strong>M</strong> value <strong>i</strong> or <strong>j</strong> and if their sum modulo <strong>M</strong> is less than or equal to <strong>x</strong>, then they will contribute to the answer.</p>
<p>The above solution will also not pass, as time complexity of given solution is <strong>O(M<sup>2</sup>)</strong>.</p>
<p>Now we will try to optimize the solution to <strong>O(M)</strong>.</p>
<p>as we can observe that if we want <strong>((i+j)%M) <=x</strong>, and we have fix the value of i. then j can take only few contiguous values.</p>
<p>There will be two cases.</p>
<p><img alt="Image" src="https://codechef_shared.s3.amazonaws.com/download/AMR14ROS/AMR14B_1.gif"></p>
<p>So, for the case I where i<=x:</p>
<pre><code>for(int i=0 ; i<= x; i++)
answer += B[i]*(B[0] + B[1] + ....+ B[x-i])
</code></pre>
<p>As we can see that the values which we are multiplying will B[i], their indices are contiguous in nature, so we can use the idea of prefix sum to get the value of the range sum in O(1) time.</p>
<p>Define Pre[i] = B[0] + B[1] + ... + B[i]
then B[i] + .... + B[x-i] = Pre[x-i] - Pre[i-1]</p>
<p>So modified code will look like :</p>
<pre><code> for(int i=0 ; i<= x; i++)
answer += B[i]*(Pre[x-i] - Pre[i-1]);
</code></pre>
<p>Similarly we can handle the second case when <strong> i>=x </strong> . Time complexity of the above solution will be <strong>O(M+N)</strong>, which will easily pass in given time limit.</p>
<h1>Editorialist's Solution:</h1>
<p>Editorialist's solution can be found <a href="http://www.codechef.com/viewplaintext/5907904">here</a>.</p>amitpandeykgpWed, 14 Jan 2015 23:05:29 +0530https://discuss.codechef.com/questions/61687/amr14c-editorialamr14roseasyhashingTRISQ - Editorialhttps://discuss.codechef.com/questions/64151/trisq-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/TRISQ">Practice</a> <br>
<a href="http://www.codechef.com/COOK55/problems/TRISQ">Contest</a></p>
<p>Author: <a href="http://www.codechef.com/users/devuy11">Devendra Agarwal</a> <br>
Tester: <a href="http://www.codechef.com/users/anudeep2011">Anudeep Nekkanti</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 geometry, recursion.</p>
<h1>PROBLEM:</h1>
<p>Find the maximum number of squares of size $2\times2$ that can be fitted in a right angled isosceles triangle of base $B$. All sides of the square must be parallel to both base and height of the isosceles triangle.</p>
<h1>QUICK EXPLANATION:</h1>
<p>As $B<=1000$, we can pre-compute the output for all the test cases, and report the answer in $O(1)$ time for each of the query.</p>
<h1>EXPLANATION:</h1>
<p>First consider the right angle triangle $\Delta XYZ$, where $YZ$ is the base of triangle. Suppose length of the base is $B$. If we consider the position of first square with the vertex $Y$, we will have $(B/2 - 1)$ squares in the base, and we will be left with another isosceles right angle triangle having base length $(B-2)$.<br><br></p>
<p>Let $f(B)$ = Number of squares which can be fitted in triangle having base length $B$.<br><br></p>
<p>$f(B) = (\frac{B}{2} -1) + f(B-2)$</p>
<p>The given time limit is sufficient even if we calculate $f(B$) using the given recursion, and use memoization. Later we can answer each query in $O(1)$ time. We can do it for even and odd numbers separately with the base case $f(1) = f(2) = f(3) = 0$.</p>
<p>The given recursion can be solved in following manner.<br><br>
$$ f(B) = \frac{B-2}{2} + F(B-2) \\\
= \frac{B-2}{2} + \frac{B-4}{2} + F(B-4) \\\
= \frac{B-2}{2}+ \frac{B-4}{2} + \frac{B-6}{2} + F(B-6) $$</p>
<p>With conditions, $f(1) = f(2) = 0$</p>
<p>$f(B) = \frac{B}{2} + (\frac{B}{2} - 1) + (\frac{B}{2} -2) + \cdots + 1$.</p>
<p>$f(B)$ = Sum of first $\frac{B}{2}$ natural numbers.</p>
<p>Lets call $M = \frac{B}{2}$<br>
$f(B) = \frac {M \times (M-1)}{2}$</p>
<p>You can notice that answer for $2N$ and $ 2N+1$ will be the same.</p>
<h1>Solution:</h1>
<p>Setter's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK55/Setter/TRISQ.cpp">here</a> <br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK55/Tester/TRISQ.cpp">here</a></p>amitpandeykgpMon, 09 Feb 2015 19:55:50 +0530https://discuss.codechef.com/questions/64151/trisq-editorialgeometrycook55trisqrecursioncakewalkWORLDCUP - Editorialhttps://discuss.codechef.com/questions/64156/worldcup-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/WORLDCUP">Practice</a><br>
<a href="http://www.codechef.com/COOK55/problems/WORLDCUP">Contest</a></p>
<p><strong>Author</strong>: <a href="http://www.codechef.com/users/devuy11">Devendra Agarwal</a> <br>
<strong>Tester</strong>: <a href="http://www.codechef.com/users/anudeep2011">Anudeep Nekkanti</a> <br>
<strong>Editorialist</strong>: <a href="http://www.codechef.com/users/amitpandeykgp">Amit Pandey</a></p>
<h1>DIFFICULTY:</h1>
<p>Simple.</p>
<h1>PREREQUISITES:</h1>
<p>Dynamic programming or combinatorics.</p>
<h1>PROBLEM:</h1>
<p>Dehatti wonders how many ways can his team score exactly $R$ runs in $B$ balls with $L$ wickets. Given that each ball can result in $4, 6, 0$ runs or a wicket(wicket won't add anything to score).</p>
<h1>QUICK EXPLANATION:</h1>
<p>Suppose we want to make $R$ runs in $B$ balls, having $X$ number of $4$'s, $Y$ number of $6$'s, ($W \le L$) number of wickets and $Z$ number of $0$'s. So there will be $4X + 6Y = R$ and $X+Y+W+Z = B$. If $(x,y,z,w)$ is a particular solution to given equations, then number of ways of arrangement will be $\frac {B!}{(x!)(y!)(w!)(z!)}$. We have to add all such cases, and the given time limit is sufficient for it.</p>
<h1>EXPLANATION:</h1>
<p>First of all, pre-calculate the value of $ ^n C_{r}$ which can be done using a simple dynamic programming approach. You may refer this <a href="http://zobayer.blogspot.in/2009/08/calculate-ncr-using-dp.html">link</a> for the more details.</p>
<p>As batsman has to make $R$ runs in $B$ balls, if $R > 6B$, there will not be any way of doing it.</p>
<p>Suppose he makes $R$ runs in $B$ balls, with at-max $L$ wickets. So, we will have the following equations. </p>
<p>$4 \times \text{fours} + 6 \times \text{sixes} = R \\
\text{fours} + \text{sixes} + \text{wickets}(\le L) + \text{zeros} = B$</p>
<p>There will be many solutions to the given equations for particular values of $R$,$B$ and $L$. We have to consider each one of them.</p>
<p>Let us consider that a particular solution of the equation is fours = $X$, sixes = $Y$, wickets = $W$ and zeros = $Z$, or $(X,Y,Z,W)$ is a solution to the given equations.</p>
<p>So, number of ways of arranging $X \hspace{2 mm}4's$, $Y \hspace{2 mm}6's$, $W$ wickets ans $Z \hspace{2 mm}0's$ can be calculated easily using the formula.</p>
<p>$\text{Ways} = \frac {B!}{(X!)(Y!)(Z!)(W!)} \\
={B \choose X} {B-X \choose Y} {B-X-Y \choose W}$ </p>
<p>Values can be used from initially calculated ${n \choose r}$ values . Take care of modulus as well.</p>
<p>T only thing remains is to produce all the triplets $(X,Y,Z,W)$.</p>
<p>We can run a loop on number of sixes varying from 0 to min(B,R/6),number of fours will be fixed i.e.</p>
<pre><code>Number of fours = (R -6*sixes)/4 if ((R - 6*sixes) % 4 == 0)
</code></pre>
<p>And we can loop over number of wickets from 0 to L.</p>
<pre><code>Number of zeros = B-sixes-fours-wickets
</code></pre>
<p>The following piece of self explanatory code will do all the calculations.</p>
<pre><code>for(int six=0; six*6 <= r && six <= b; six++) {
int other = r - six*6;
if(other % 4 == 0) {
int four = other/4;
for(int wicket=0; wicket <= l; wicket++) {
if(six + four + wicket <= b) {
long long cur = C[b][six];
( cur *= C[b-six][four] ) %= 1000000007;
( cur *= C[b-six-four][wicket] ) %= 1000000007;
ways += cur;
}
}
ways %= 1000000007;
}
}
</code></pre>
<h1>Solutions:</h1>
<p>Setter's solution can be found <a href="https://codechef_shared.s3.amazonaws.com/download/Solutions/COOK55/Setter/WORLDCUP_logic1.cpp">here </a>.<br>
Setter's another solution can be found <a href="https://codechef_shared.s3.amazonaws.com/download/Solutions/COOK55/Setter/WORLDCUP_logic2.cpp">here </a>.<br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK55/Tester/WORLDCUP.cpp">here</a>.</p>amitpandeykgpMon, 09 Feb 2015 19:58:07 +0530https://discuss.codechef.com/questions/64156/worldcup-editorialworldcupdynamic-programmingcook55combinatoricsmathssimpleFOMBRO - Editorialhttps://discuss.codechef.com/questions/64188/fombro-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/FOMBRO">Practice</a><br>
<a href="http://www.codechef.com/COOK55/problems/FOMBRO">Contest</a></p>
<p><strong>Author</strong>: <a href="http://www.codechef.com/users/devuy11">Devendra Agarwal</a> <br>
<strong>Tester</strong>: <a href="http://www.codechef.com/users/anudeep2011">Anudeep Nekkanti</a> <br>
<strong>Editorialist</strong>: <a href="http://www.codechef.com/users/amitpandeykgp">Amit Pandey</a></p>
<h1>DIFFICULTY:</h1>
<p>Simple.</p>
<h1>PREREQUISITES:</h1>
<p>Dynamic programming and basic mathematics.</p>
<h1>PROBLEM:</h1>
<p>You are given a function f which is defined as:
$$f(N) = 1^N 2^{N-1}.....N^1$$
Find $$\frac {f(N)}{f(r)f(N-r)} \mod M$$</p>
<h1>QUICK EXPLANATION:</h1>
<p>Let $r = \min(r,N-r)$. There will be three cases: $x \le r$, $r < x \le N-r$ and
$N-r < x \le N$. Calculate power of $x$ in each of the case and multiply them taking modulo $M$. </p>
<h1>EXPLANATION:</h1>
<p>The give problem can be solved using simple dynamic programming approach. </p>
<p>Let $r = \min(r,N-r)$ and call $ F(N,r) = \frac {f(N)}{f(r)f(N-r)} $. </p>
<p><strong>Case 1</strong>$(x \le r)$: </p>
<p>Power of $x$ in $f(N)$= $N
-x+1$. <br>
Power of $x$ in $f(r)$= $r-x+1$.<br>
Power of $x$ in $f(N-r)$= $(N-r)-x+1$. <br>
Hence, Power of $x(\le r)$ in $F(N,r)$= $(N-x+1) - (r-x+1) - ((N-r)-x+1) = x-1$.</p>
<p><strong>Case 2</strong>$(r < x \le N-r)$: </p>
<p>Power of $x$ in $f(N)$= $N-x+1$. <br>
Power of $x$ in $f(r)$= $0$. as $(x > r)$ <br>
Power of $x$ in $f(N-r)$= $(N-r)-x+1$. <br>
Hence, Power of $x$ in $F(N,r)$= $(N-x+1) - ((N-r)-x+1) = r $.</p>
<p><strong>Case 3</strong>$(N-r < x \le N)$: </p>
<p>Power of $x$ in $f(N)$= $N-x+1$. <br>
There will not be any term corresponding to denominator.
Hence, Power of $x$ in $F(N,r)$= $(N-x+1)$.</p>
<p>As, there can be large number of queries. We need to do some pre-processing to give results.
As, results to first and third case doesn't depend on the value of $r$, we can pre-process them and store. </p>
<pre><code> //Case I : For the given value of r, fordp[r] will store multiplication
of all x corresponding to the first case.
for(int i=1;i<=N/2;i++)
fordp[i] = (fordp[i-1]*binpow(i,i-1,M))%M;
</code></pre>
<p>In case 2, it can be noticed that power of $x$ depends on $r$ and the distance of $r$ and $N-r$ from $N/2$ will be the same. So, we can store multiplication of terms which are equi-distance from center in an array. So, that we can get value of $Midr = \prod_{r+1}^{N-r} x$ in constant time.</p>
<pre><code> //Case 2 : You can get Midr in O(1) time.
if(N&1)
betdp[N/2] = N/2 +1;
else
betdp[N/2]=1;
for(ll i=N/2-1;i>=1;i--)
betdp[i] = ((ll)((betdp[i+1]*(i+1))%M)*(ll)(N-i))%M;
</code></pre>
<p>Case 3 will not depend on the value of $r$, so we can do it similar to case 1.</p>
<pre><code> //Case III
for(ll i=1;i<=N/2;i++)
backdp[i]= (backdp[i-1]*binpow(N-i+1,i,M))%M;
</code></pre>
<p>Finally you can calculate the output easily. See Setter's <a href="http://www.codechef.com/download/Solutions/COOK55/Setter/FOMBRO.cpp">code</a> for the detailed implementation.</p>
<p>Second case i.e. calculating $\prod_{r+1}^{N-r} x % M$ can also be done using the segment tree. In the segment tree, a node will store the multiplication of both of the children mod $M$. Refer this wonderful <a href="http://letuskode.blogspot.in/2013/01/segtrees.html">tutorials</a> for the more details on segment tree. See <a href="http://www.codechef.com/download/Solutions/COOK55/Tester/FOMBRO.cpp">tester's code</a> for the implementation of this approach.</p>
<h1>Solutions:</h1>
<p>Setter's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK55/Setter/FOMBRO.cpp">here</a>.<br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK55/Tester/FOMBRO.cpp">here</a>.</p>amitpandeykgpTue, 10 Feb 2015 00:35:56 +0530https://discuss.codechef.com/questions/64188/fombro-editorialcook55mathematicsfombrosimpledynamic-programmingSUBARRAY - Editorialhttps://discuss.codechef.com/questions/64196/subarray-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/SUBARRAY">Practice</a> <br>
<a href="http://www.codechef.com/COOK55/problems/SUBARRAY">Contest</a></p>
<p><strong>Author</strong>: <a href="http://www.codechef.com/users/devuy11">Devendra Agarwal</a> <br>
<strong>Tester</strong>: <a href="http://www.codechef.com/users/anudeep2011">Anudeep Nekkanti</a> <br>
<strong>Editorialist</strong>: <a href="http://www.codechef.com/users/amitpandeykgp">Amit Pandey</a></p>
<h1>DIFFICULTY:</h1>
<p>Medium.</p>
<h1>PREREQUISITES:</h1>
<p>Dynamic programming and Data Structure(stack).</p>
<h1>PROBLEM:</h1>
<p>You are given a character parenthesis ( having $[,],{,},<,>,(,) $) array and an integer array.
You need to find the maximum sum sub-array in the integer array such that the corresponding sub-array in the character array has balanced parenthesis. </p>
<h1>QUICK EXPLANATION:</h1>
<p>The given problem can be solved using a dynamic programming approach quite similar to <a href="http://en.wikipedia.org/wiki/Maximum_subarray_problem">maximum subarray problem</a>.
We need to take care of balanced parenthesis, which can be done using a <a href="http://stackoverflow.com/questions/2711032/basic-recursion-check-balanced-parenthesis">classical approach</a>. </p>
<h1>EXPLANATION:</h1>
<p><strong>First Problem:</strong> <br>
How to solve maximum sum sub array problem using <a href="http://en.wikipedia.org/wiki/Maximum_subarray_problem">Kadane ALgorithm</a>, which is a classical dynamic programming problem.</p>
<pre>def max_subarray(A):
max_ending_here = max_so_far = 0
for x in A:
max_ending_here = max(0, max_ending_here + x)
max_so_far = max(max_so_far, max_ending_here)
return max_so_far
</pre>
<p><strong>Second problem:</strong> <br>
Given a character parenthesis array, check if it is balanced or not. </p>
<p>1) Declare a character stack $S$. <br>
2) Now traverse the expression string expression. </p>
<ul>
<li>If the current character is a starting bracket then push it to stack. </li>
<li>If the current character is a closing bracket, then pop from stack and if the popped character is the matching starting bracket then fine else parenthesis are not balanced. </li>
</ul>
<p>3) After complete traversal, if there is some starting bracket left in stack then “not balanced”. </p>
<p><strong>Original Problem:</strong> <br>
Now back to original problem. Traverse the character array and if there is a closing brace at position $i$, determine the largest index($j < i$) such that $[j,i]$ is balanced. We can this in one pass of the character array using a stack. The approach is similar to the second problem given above.</p>
<pre>for(int i=0;i<=N+1;i++)
hsh[i] = 0; // This array will store j for each i.
stack<int> st;
st.push(0);
for (int i = 1; i <= n; i++) {
if (!st.empty()) {
// check if top of stack is opposite of current parenthesis.
if (closingBracket(s[i]) && s[st.top()] == opposite(s[i])) {
hsh[i] = st.top(); // We found j for the i.
st.pop();
} else {
st.push(i);
}
} else {
st.push(i);
}
}
</pre>
<p>When we are at index $i$, we may consider what we have solved problem upto index $i-1$, and we have created an array $DP[ \hspace{1 mm}]$. Where, $DP[j]$ stored the maximum sum ending at index $j$.</p>
<p>Dynamic Programming recurrence:</p>
<p>Let us call a sub-array valid, if its corresponding character array is balanced. Let dp[i] denotes maximum sum valid sub-array
ending at position $i$.
So recurrence for $DP$ will be as follows. </p>
<p>$DP[i] = max$ $(DP[i], dp[hsh[i] - 1] + sum(hsh[i], i))$<br><br>
$hsh[i] \text{ is the largest j (j < i) such that segment} [j,i] \text{ is the balanced.} $</p>
<p>The given recurrence is using the simple fact if expressions $E_{1}$ and $E_{2}$ are balanced, expression $E_{1}E_{2}$ is balanced.</p>
<p>For finding out overall maximum sum sub-array we can iterate over each $i$ and take maximum of $DP[i]$.</p>
<h1>Solutions:</h1>
<p>Setter's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK55/Setter/SUBARRAY.cpp">here</a>.<br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK55/Tester/SUBARRAY.cpp">here</a>.</p>amitpandeykgpTue, 10 Feb 2015 01:52:32 +0530https://discuss.codechef.com/questions/64196/subarray-editorialcook55subarraydata-structuremediumdynamic-programmingSPSHORT - Editorialhttps://discuss.codechef.com/questions/64224/spshort-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/SPSHORT">Practice</a><br>
<a href="http://www.codechef.com/COOK55/problems/SPSHORT">Contest</a></p>
<p><strong>Author</strong>: <a href="http://www.codechef.com/users/devuy11">Devendra Agarwal</a> <br>
<strong>Tester</strong>: <a href="http://www.codechef.com/users/anudeep2011">Anudeep Nekkanti</a> <br>
<strong>Editorialist</strong>: <a href="http://www.codechef.com/users/amitpandeykgp">Amit Pandey</a></p>
<h1>DIFFICULTY:</h1>
<p>Medium-Hard.</p>
<h1>PREREQUISITES:</h1>
<p>Dijkstra Algorithm, STL uses.</p>
<h1>PROBLEM:</h1>
<p>You are given a graph, you need to find the shortest walk in the graph from src to snk which satisfies the following property:
Let the shortest path from src to snk goes from edges $E_{1} -> E_{2} -> \cdots -> E_{k}$ , then $Weight(E_{1}) > Weight(E_{2}) < Weight(E_{3}) > Weight(E_{4}) \cdots$ and so on. </p>
<h1>QUICK EXPLANATION:</h1>
<p>The given problem can be solved using few modification in <a href="http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm">Dijkstra Algorithm</a>.</p>
<h1>EXPLANATION:</h1>
<p><strong>First Subproblem:</strong></p>
<p>Given a graph, You need to find the shortest path in the graph from $\text{src}$ to $\text{snk}$, without any condition. This problem can be solved using <a href="http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm">Dijkstra Algorithm</a>. In Dijkstra Algorithm, We initialize distance of the $\text{src}$ with $0$, and distance of other vertices as $ \infty$ and add $\text{src}$ into a priority queue, and we do it in following manner. </p>
<pre><code> while Q is not empty:
u ← vertex in Q with min dist[u] // Source node in first case
remove u from Q
for each neighbor v of u: // where v has not yet been removed from Q.
alt ← dist[u] + length(u, v)
if alt < dist[v]: // A shorter path to v has been found
dist[v] ← alt
prev[v] ← u
end if
end for
end while
</code></pre>
<p>The given pseudo-code calculates the shortest path for each of the vertex. The shortest path for the $\text{snk}$ can be reported easily. Implementation of the Dijkstra Algorithm can be looked <a href="http://zobayer.blogspot.in/2009/12/dijkstras-algorithm-in-c.html">here</a>.</p>
<p><br><strong>Second Subproblem:</strong></p>
<p>You are given a graph, you need to find the shortest wak in the graph from src to snk which satisfies the following property:
Let the shortest path from src to snk goes from edges $E_{1} -> E_{2} -> \cdots -> E_{k}$ , then $Weight(E_{1}) < Weight(E_{2}) < Weight(E_{3}) < Weight(E_{4}) \cdots$ and so on. </p>
<p>In sub-problem 1, we kept a visited array. Once a node has been visited, we get the shortest path for that particular node and there is no need to visit the same vertex again. We can do it in a different manner, at the moment we are exploring vertex $v$, and pushing all neighbour of $v$ in the priority queue, we can delete all neighbouring edges of vertex $v$ just after pushing them in priority queue.</p>
<p>So, for solving subproblem 2, Consider we have arrived at vertex $V$ by an edge having weight $W$. when removing the vertex $V$ from the priority queue, push all neighbour $X$ of $V$ if $ W_{VX} > W$, and delete all those edges from the edge-list . This algorithm guarantees that each edge is processed at most once. hence, algorithm will terminate. We may visit a vertex more than once. </p>
<p>The proof of correctness of the given algorithm can be understood in following way. If we arrived at vertex $V$ with cost $C_{1}$, and later we arrived at same vertex with cost $C_{2}$, then $C_{1} < C_{2}$, cost of last explored edge in both cases are the same .</p>
<p><strong>Implementation details:</strong></p>
<p>Preprocess the graph by sorting outgoing edges from each node (by weight). Keep a pointer at each vertex, which will tell edges having higher weight should not be considered. </p>
<p><strong>Original Problem:</strong></p>
<p>To solve the original problem, where edge length is increasing and decreasing alternatively. We need to make a few changes in second subproblem. We will keep two copies of the graph in as the edge list, Call them $GL$ and $GS$. A $ \text{counter}$ should be kept, $ \text{even counter}$ will denote that we are looking for a smaller edge and $ \text{odd counter}$ will tell that we are looking for a larger edge than previous one.While we are looking for a larger edges we will delete those larger edges after pushing them in the priority queue.<strong>This deletion will happen only in larger copy of the graph</strong> which is edge-list $GL$, and similarly in other case.</p>
<p>The reason for keeping two copies of graph is that if edge $E$ has been taken and it is larger than last one, then later it can considered again(as shorter than last one).</p>
<p><img src="https://www.codechef.com/download/COOK55/a.PNG"></p>
<p>Now see the reason of keeping two copies of graph, edge having length $10$ is being considered twice. During execution of the algorithm, first it will be deleted from the smaller copy of the graph i.e. $GS$(while traversing from length $200$ to $10$)and later it will be deleted from the larger copy of the graph i.e. $GL$(while traversing for length $8$ to $10$). </p>
<p>As the deletion can be costly or can have linear complexity, we can keep counters which will tell range in which edge list need to be considered. Time Complexity of the above approach will be $O(ElogE + ElogV)$, $O(ElogE)$ will appear due to sorting edge list, and $O(ElogV)$ due to Dijkstra. </p>
<h1>Solutions:</h1>
<p>Setter's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK55/Setter/SPSHORT.cpp">here</a>.<br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK55/Tester/SPSHORT.cpp">here</a>.</p>amitpandeykgpWed, 11 Feb 2015 00:50:20 +0530https://discuss.codechef.com/questions/64224/spshort-editorialshortest-pathgraphcook55dijkstramedium-hardpaths-in-graphspshortDIVGOLD - Editorialhttps://discuss.codechef.com/questions/66402/divgold-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/DIVGOLD">Practice</a> <br>
<a href="http://www.codechef.com/COOK56/problems/DIVGOLD/">Contest</a></p>
<p>Author: <a href="http://www.codechef.com/users/witua">Vitaliy Herasymiv</a> <br>
Tester: <a href="http://www.codechef.com/users/iscsi">Istvan Nagy</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>Simulation of brute force algorithm.</p>
<h1>PROBLEM:</h1>
<p>You have a string $S$ which consists of $N$ uppercase English letters. You are allowed to at most once do the following process: Choose any position in the string, remove the character at this position and insert the same character back in any other place.</p>
<p>Find the lexicographically smallest string you can achive. </p>
<h1>QUICK EXPLANATION:</h1>
<p>Generate all possible strings, and keep track of the lexicographically smallest string. </p>
<h1>EXPLANATION:</h1>
<p>We can create all possible strings by removing a character at some position and adding it to other position. We will have one string for each removed and inserted positions. So overall there will be total $O(n^2)$ such possible strings. We can implement the process of removal and additions of character at some position in $O(n)$ time. Overall it will take $O(n^2 * n) = O(n^3)$ time.</p>
<p>We just need to write a function <em>Modify()</em>, which will take input two integers $i$ and $j$, and delete the $j^{th}$ character of the given string and insert it between $i^{th}$ and $(i+1)^{th}$ character. <em>Modify()</em> function will generate a new string which we can get by performing the given process at most once. We can run <em>Modify()</em> function on all possible values of $i$ and $j$, and report the minimum one. </p>
<p>Peseudo code can be given as below:</p>
<pre><code>string lex_minimum = given_string;
for(int i = 0 ; i< given_string.length() ; i ++)
{
for(int j =0 ; j < given_string.length() ; j++)
{
temp_string = Modify(i,j);
lex_minimum = min(temp_string,lex_minimum);
}
}
print lex_minimum
</code></pre>
<p>Solving the given problem with better complexity is an interesting task, please comment if you find such solution. </p>
<h1>Solution:</h1>
<p>Setter's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK56/Setter/DIVGOLD.cpp">here</a> <br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK56/Tester/DIVGOLD.cpp">here</a></p>amitpandeykgpFri, 20 Mar 2015 18:16:29 +0530https://discuss.codechef.com/questions/66402/divgold-editorialsimulationcook56divgoldsortingcakewalkSTRAB - Editorialhttps://discuss.codechef.com/questions/66424/strab-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/STRAB/">Practice</a> <br>
<a href="http://www.codechef.com/COOK56/problems/STRAB/">Contest</a></p>
<p>Author: <a href="http://www.codechef.com/users/witua">Vitaliy Herasymiv</a> <br>
Tester: <a href="http://www.codechef.com/users/iscsi">Istvan Nagy</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>Counting, Dynamic Programming, Recursion.</p>
<h1>PROBLEM:</h1>
<p>Given strings $X$ and $Y$, count the number of strings of length $n$ which do not contain string $S (X \leq S \leq Y)$ of length $m(\leq n)$ as a substring.</p>
<h1>EXPLANATION:</h1>
<p>In this problem it is asked to count the number of strings of length $n$ which do not contain string $S (X \leq S \leq Y)$ of length $m(\leq n)$ as a substring. Let $H$ be a set of strings which are lexicographically in between $X$ and $Y$ inclusively that is $H = \{S : |S| = m \wedge X\leq S \leq Y \}$. Now define $\text{dp}[i]$ as the number of strings of length exactly equal to $i$ which do not contain string(s) which belong(s) to $H$ as a substring. It is clear that if $i < m$ then $\text{dp}[i] = 26^i$. </p>
<p>For $i \geq m$, define a recursive function $f(S, n, i)$ which takes input string s, ending index $n$ and index $i$ which is to be filled. This function returns the number of valid strings( which are not hated ) whose last $n-i$ letter are already fixed as $S$. For example $f(AB, 5, 3)$ will return number of valid strings of length 6(assuming zero indexing and $n=5$) whose last 2 letters are fixed as "AB". Also define a function $V(S, len)$ which return 1 if string $S$ of length $len$ is valid else it returns 0. Note that if $len < m$ then the string is trivially valid else we have to check $X \leq S \leq Y$. Further $len$ will always be less than or equal to $m$ by virtue of following definition of $f(S, n, i)$ where a value greater than $m$ is never passed to $V(S, len)$</p>
<p>Now $f(S, n, i) = 24\text{dp}[i] + f(AS, n, i-1)\times \text{V}(AS, \min(m, \text{len}(AS)) + f(BS, n, i-1)\times \text{V}(BS, \min(m, \text{len}(BS))$ because the ith index can be C-Z, in which case we are left with string of length $i$ (index $0$ to $i-1$) thats why the term $24\text{dp}[i]$; or ith index can be 'A' in that case we have to check whether the string from ith index to min(i+m-1, n) is valid or not thats why the term $f(AS, n, i-1)\times \text{V}(AS, \min(m, \text{len}(AS))$ and similar expression when ith index is 'B'. Base case will be when $i=-1$ in that case return 1.</p>
<p>Now, for $i \geq m$, $\text{dp}[i] = f(\text{empty string} , i-1, i-1)$. So, the final answer to the question will be $\text{dp}[n]$. Refer to the editorialist code in the solution section for more detail. The worst case time complexity of this algorithm is $\mathcal{O}(n 2^n)$.</p>
<h1>Solution:</h1>
<p>Setter's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK56/Setter/STRAB.cpp">here</a> <br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK56/Tester/STRAB.cpp">here</a> <br>
Editorialist's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK56/Editorialist/STRAB.cpp">here</a></p>amitpandeykgpSat, 21 Mar 2015 01:37:30 +0530https://discuss.codechef.com/questions/66424/strab-editorialdynamic-programmingrecursioncook56easy-mediumstrabSTRBIT - Editorialhttps://discuss.codechef.com/questions/66425/strbit-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/STRBIT">Practice</a> <br>
<a href="http://www.codechef.com/COOK56/problems/STRBIT/">Contest</a></p>
<p>Author: <a href="http://www.codechef.com/users/witua">Vitaliy Herasymiv</a> <br>
Tester: <a href="http://www.codechef.com/users/iscsi">Istvan Nagy</a> <br>
Editorialist: <a href="http://www.codechef.com/users/amitpandeykgp">Amit Pandey</a> </p>
<h1>DIFFICULTY:</h1>
<p>Easy.</p>
<h1>PREREQUISITES:</h1>
<p>BIT, segment tree.</p>
<h1>PROBLEM:</h1>
<p>Determine minimum amount of minutes required to paint a fence consisting of $N$ parts, in green color. Each part is initially painted either red or green. We can chose an index $X$, and flip colors in range $[X,\min(X+K,N-1)]$ in one minute. </p>
<h1>QUICK EXPLANATION:</h1>
<p>Consider the index where first red is occurring as $T$, flip the colors in range $[T,\min(N,T+K-1)]$. Keep repeating this step until each part is colored green. </p>
<h1>EXPLANATION:</h1>
<p>First lets see how to solve the problem, later we can see the proof of correctness. <br></p>
<p>Consider the index at which first red is occurring and call it $T$, flip the colors in range $[T+\min(N,T+K-1)]$. Keep repeating the given procedure unless whole array is green. After each iteration value of $T$ will be increasing, so the given algorithm will terminate in less than or equal to $N$ steps.<br><br></p>
<p>Each iteration may take $O(N)$ amount of time, hence the given algorithm will be taking $O(N^2)$ time. As the $N$ can be $10^5$ in the given problem, we need to optimize our solution.</p>
<p>We can solve the problem in $O(N\log N)$ time. Range flip can be seen as adding $1$ to the range and value of color can be obtain using sum at that particular index modulo $2$. If the $\text{sum} \%2$ is $0$, then color at that index will be same as the initial one or flipped otherwise. The range updates and queries can be done in $O(\log N)$ time using <a href="https://www.topcoder.com/community/data-science/data-science-tutorials/binary-indexed-trees/">BIT</a> or <a href="http://letuskode.blogspot.in/2013/01/segtrees.html">segment tree</a>. </p>
<p><strong>O(N) Solution:</strong></p>
<p>It can be done in $O(N)$ as well. Adding $1$ to range $[L,R]$ can be seen as adding $1$ to index $L$ and adding $-1$ to index $(R+1)$. When we want to retrieve the value at specific index, we need to take the prefix sum upto that index. See sub problem 1 of this <a href="http://discuss.codechef.com/questions/51457/updtree-editorial">editorial</a> for more details.</p>
<p><strong>Proof:</strong></p>
<p>The given procedure can be proved correct using the following lemmas. </p>
<ol>
<li>Order of the updates doesn't matter.</li>
<li>Starting index of any 2 updates will be different, as 2 updates at same starting position will cancel each other. </li>
<li>If we sort the minimum update sequence and suppose first update happens at index $i$, then at each index in range $[0,i-1]$ color must be green and at index $i$, color must be red. </li>
</ol>
<h1>Solution:</h1>
<p>Setter's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK56/Setter/STRBIT.cpp">here</a> <br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK56/Tester/STRBIT.cpp">here</a></p>amitpandeykgpSat, 21 Mar 2015 02:10:19 +0530https://discuss.codechef.com/questions/66425/strbit-editorialsegment-treestrbitbitcook56easyKINT - Editorialhttps://discuss.codechef.com/questions/66426/kint-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/KINT">Practice</a> <br>
<a href="http://www.codechef.com/COOK56/problems/KINT/">Contest</a></p>
<p>Author: <a href="http://www.codechef.com/users/witua">Vitaliy Herasymiv</a> <br>
Tester: <a href="http://www.codechef.com/users/iscsi">Istvan Nagy</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>Dynamic Programming</p>
<h1>PROBLEM:</h1>
<p>Given a set of integers $\{0, 1, 2, ..., n\}$, find the number of ways of choosing a subset of $k$ integers such that the xor of all chosen integers has exactly $B$ set bits(in the binary representation).</p>
<h1>EXPLANATION:</h1>
<p>In this problem, our approach will be to generate(smartly) all possible $k$ integers bit by bit from MSB in a particular order. At any step $i$ we will assume that we have generated $k$ integers upto ith bit following a order and extend it to i+1th bit( taking care of the ordering as well) and in the process, counting all possible ways of extension of $k$ integer. Now to smartly count all the ways we will use dynamic programming approach.</p>
<p>Define a 3-D dp matrix $\text{dp[i][b][mask]}$ which stores the number of ways of choosing $k$ integers of $i$ bits such that their xor has $b$ set bits and the $k$ integers follow a specific order according to the mask. Important idea to note here is that the $k$ integers chosen follow a specific order defined by mask as follows :-</p>
<p>0th bit of mask is 1/0 iff 1st chosen integer is strictly less/equal than n upto i bits from MSB.<br>
1st bit of mask is 1/0 iff 2nd chosen integer is strictly less/equal than 1st chosen integer upto i bits from MSB.<br>
2nd bit of mask is 1/0 iff 3rd chosen integer is strictly less/equal than 2nd chosen integer upto i bits from MSB.<br>
.<br>
.<br>
.<br>
k-1 th bit of mask is 1/0 iff kth chosen integer is strictly less/equal than k-1 th chosen integer upto i bits from MSB. </p>
<p>This means that the $k$ integers are considered in decreasing order. Since the ordering doesn't matter in set, there is no harm in generating $k$ integer in decreasing order. Lets say the first $i$ bits of $k$ integers are already generated according to mask. Now these $k$ integers can be extended to $i+1$th bit(from MSB) in $2^k - 1$ ways, that is the value of pred( it is a $k$ bit number such that $j$th bit of pred is $i+1$th bit of $j$th chosen number, refer to the figure below for more detail) can take $2^k - 1$ value. And for each value of pred and old mask the ordering of $k$ integer ( also the mask ) will change. Note that the newmask (which denotes the ordering among k chosen number) may be invalid because there may be some pair(s) of numbers which are not in decreasing order, in that case the newmask will be invalid. Now lets consider each possible scenario case by case.</p>
<p><img alt="image" src="https://s3.amazonaws.com/codechef_shared/download/COOK56/kint2.jpg"></p>
<p>First initalize newmask with mask. The first condition involves the number $n$ and the 1st chosen number. </p>
<p>If 0th bit of mask is 0 which implies 1st number is equal to n upto i bits from MSB then<br>
Case 1.1: If i+1th bit of n is 1 and i+1th bit of 1st number is 0 then 0th bit of newmask will be 1 as 1st number is now smaller than n.<br>
Case 1.2: If i+1th bit of n is 1 and i+1th bit of 1st number is 1 then no change in newmask.<br>
Case 1.3: If i+1th bit of n is 0 and i+1th bit of 1st number is 0 then no change in newmask.<br>
Case 1.4: If i+1th bit of n is 0 and i+1th bit of 1st number is 1 then in this case newmask will be invalid. </p>
<p>The following condition involves j+1th and jth chosen number where j varies from 1 to k-1.<br>
If jth bit of mask is 1 that means j+1th number is strictly smaller than jth number upto ith bit and even if i+1st bit is 0 or 1 this order will not change hence in this case newmask will not change.<br>
Else If jth bit of mask is 0, this means j+1th number is equal to jth number and depending upon the i+1th bit of those two number newmask will change.<br>
Case 2.1: If i+1th bit of jth number is 1 and j+1th bit of 1st number is 0 then jth bit of newmask will be 1 as j+1th number is now smaller than jth number.<br>
Case 2.2: If i+1th bit of jth number is 1 and j+1th bit of 1st number is 1 then no change in newmask.<br>
Case 2.3: If i+1th bit of jth number is 0 and j+1th bit of 1st number is 0 then no change in newmask.<br>
Case 2.4: If i+1th bit of jth number is 0 and j+1th bit of 1st number is 1 then in this case newmask will be invalid. </p>
<p>After the computation of newmask and it validity update the dp state dp[i+1][b+setBits(pred)%2][newmask] += dp[i][b][mask] if newmask is valid. Base case will be dp[0][0][0] = 1. Below is basic structure of the code for more clarity.</p>
<pre><code>for(i = 0 to 31) for(b = 0 to B) for(mask = 0 to 2^k - 1) :
for(pred = 0 to 2^k - 1) :
(newmask, validity) = generateNewMask(mask, pred);
//this function generates newmask according to the above rules
if(validity) dp[i+1][b+setBits(pred)%2][newmask] += dp[i][b][mask];
//setBits(x) return number of set bits in x
</code></pre>
<p>Now the final answer will be dp[31][B][2^k - 1] + dp[31][B][2^k - 2] corresponding to the case when 1st number is equal to n and when 1st number is strictly less than n. Refer to the tester's code for more details. The time complexity of the algorithm is $\mathcal{O}(B\log n2^k)$. </p>
<h1>Solution:</h1>
<p>Setter's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK56/Setter/KINT.cpp">here</a> <br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK56/Tester/KINT.cpp">here</a></p>amitpandeykgpSat, 21 Mar 2015 02:14:52 +0530https://discuss.codechef.com/questions/66426/kint-editorialdynamic-programmingkintmediumcook56VISITALL - Editorialhttps://discuss.codechef.com/questions/66472/visitall-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/VISITALL">Practice</a> <br>
<a href="http://www.codechef.com/COOK56/problems/VISITALL/">Contest</a></p>
<p>Author: <a href="http://www.codechef.com/users/witua">Vitaliy Herasymiv</a> <br>
Tester: <a href="http://www.codechef.com/users/iscsi">Istvan Nagy</a> <br>
Editorialist: <a href="http://www.codechef.com/users/amitpandeykgp">Amit Pandey</a> </p>
<h1>DIFFICULTY:</h1>
<p>Easy.</p>
<h1>PREREQUISITES:</h1>
<p>Simulation.</p>
<h1>PROBLEM:</h1>
<p>Given a robot and $N\times N$ grid, find any valid sequence of moves starting from $(1,1)$ such that there are no more than three consecutive turns that moved the robot in the same direction and robot covers each cell at-least once.</p>
<h1>QUICK EXPLANATION:</h1>
<p>Start at $(1,1)$ and at each step, consider two consecutive rows and visit in pattern $DRURDRU$(D=Down, R=Right, U=Up). Once both rows are done, jump to another pair of rows. Take care of hurdles using some specific technique. See explanation for details.</p>
<h1>EXPLANATION:</h1>
<p>There might be many possible solutions to the problem, lets discuss one of them. We need to derive an strategy which will be covering all of the cells using minimum number of steps and later we have to increase the steps to stop ourselves to go to forbidden cells. </p>
<p>Start at co-ordinate $(1,1)$, Consider two rows at a time. visit in the pattern $DRURDRU$.
<img alt="img" src="https://s3.amazonaws.com/codechef_shared/download/COOK56/visitall3.jpg"></p>
<p>If in any row, we found a forbidden cell then it will fall in one of these two cases.</p>
<ol>
<li>We are visiting in pattern $DRURDRU$. Suppose while we are going up after going right and get to a cell which is forbidden, then we may continue in right direction and then go up(the pattern $DRUR$ becomes $DRRU..$). See the first one in the image.</li>
<li>We get a forbidden cell while we are going into right and previous one was the up. In this case, we may go down again, go right twice and then go up($DRURDR$ becomes $DRUDRUR..$).
<img alt="Drawing" src="https://s3.amazonaws.com/codechef_shared/download/COOK56/visitall.jpg"></li>
</ol>
<p>In second case, we are visiting a cell more than once but we are skipping a cell as well. So, number of steps will not exceed number of cells. So, if $N$ is even then in worst case we are using $O(N^2)$ number of steps. If $N$ is odd, we are using $(N-1)^{th}$ row twice so, we using $N(N+1)$ number of step in worst case.</p>
<p>While connecting the row pair ending we will be using at most $5$ steps while there is some forbidden cell, which can be shown using the following image. If there is no forbidden cell, we can do it in lesser number of steps. </p>
<p><img alt="Drawing" src="https://s3.amazonaws.com/codechef_shared/download/COOK56/visitall2.PNG">
<br><br>
Maximum number of step would be $\le N(N+1) + 5(\frac{N}{2}) = N(N+\frac{7}{2})$<br></p>
<p>It is easy to see we are never taking three steps in same direction in any of the case. In first two cases, we are taking at most two steps in the same direction. While we are switching the pair of rows, we are taking three steps in one direction in the same direction and later changing the direction just after third step. </p>
<h1>Solution:</h1>
<p>Setter's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK56/Setter/VISITALL.cpp">here</a> <br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK56/Tester/VISITALL.cpp">here</a></p>amitpandeykgpSat, 21 Mar 2015 19:11:58 +0530https://discuss.codechef.com/questions/66472/visitall-editorialvisitallcook56easysimulationANKGAME - 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-mediumcountingcook59ankgameUTMOPR - 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-progsimulationcook59utmoprcakewalkANKNIM2 - 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-hardANKPAREN - 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-progcook59stackANKMARKS - 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-expo