Questions Tagged With ltime22https://discuss.codechef.com/tags/ltime22/?type=rssquestions tagged <span class="tag">ltime22</span>enThu, 26 Mar 2015 20:47:02 +0530PAINTBOX - editorialhttps://discuss.codechef.com/questions/66952/paintbox-editorial<p><b>PROBLEM LINK:</b><br>
<a href="http://www.codechef.com/problems/PAINTBOX">Practice</a><br>
<a href="http://www.codechef.com/LTIME22/problems/PAINTBOX">Contest</a><br></p>
<p><b>Author:</b> <a href="http://www.codechef.com/users/pankaj%20jindal">Pankaj Jindal</a>, <a href="http://www.codechef.com/users/piyushkumar">Piyush Kumar</a> <br>
<b>Tester: </b><a href="http://www.codechef.com/users/xcwgf666">Sergey Kulik</a> <br>
<b>Editorialist:</b> <a href="http://www.codechef.com/users/amanjain110893">Aman jain</a><br></p>
<h1>DIFFICULTY:</h1>
<p>Medium</p>
<h1>PREREQUISITES:</h1>
<p>Set, Segment Tree</p>
<h1>PROBLEM:</h1>
<p>Given a array $A$ of size N each filled with a color with value $A_i$. There are $Q$ queries, each query update color of box at position $Pos_i$ with color $Col_i$. For each query you need to find number of ways to select $W$ adjacent boxes of same color from total of $N$ boxes.</p>
<h1>QUICK EXPLANATION:</h1>
<p>Maintain a set of starting indices of color segments. Now on each query there are three possibilities, either we assign the same color, so no change to the array, or we have an update that breaks a continuous segment of colors, or an update that joins two continuous segments, each of which can be done in $O(log(N))$. Update your answer for the query and correspondingly update set of starting indices of color segments.</p>
<h1>EXPLANATION:</h1>
<p>Let's start with easy constraints. Let say you have a color segment of length $L$, then number of ways to select $W$ adjacent boxes from this segment would be $max(0,(L-W+1))$. Now if you have sequence of segments say, $s1s2s3s4$, then number of ways to select $W$ boxes would be sum of number of ways for each segment i.e. $\sum{max(0,L_i-W+1)}$. Complexity of this solution would be $O(N*Q)$, this works within time-limit for first sub-task but will fail on main task.<br><br>
To solve hard part efficiently, we can store the result of the query for the input string in $ans$ and maintain set that store starting indices of color segments. After each query operation we need to insert or erase indices from set accordingly.<br>
If you analyse closely you will find that each update operation looks like:<br>
a) if update operation, does not change the state of boxes from current state, then there will be no change in answer to this query. <br>
b) state change can be described as, $......s_a c1 s_b......$ to $......s_a c2 s_b......$, where $s_a$ is segment to the left and $s_b$ segment to the right of update position $pos_i$, with box color changed from $c1$ to $c2$.<br><br> Following cases possible (assuming 0 based indexing):<br>
1) $pos_i$ is 0 and $c1$ lies in $s_b$ i.e. same in color to $s_b$, after the operation splitting takes place and $ans = ans - ways(len(s_b)+1) + ways(len(1)) + ways(len(s_b))$, here ways(l) means number of ways to get $W$ adjacent boxes from segment of length $l$.<br>
2) $pos_i$ is 0 and $c1$ does not lies in $s_b$, after updation $c2$ lies in $s_b$, so merging takes place. $ans = ans - ways(1) - ways(len(s_b)) + ways(len(s_b)+1)$.<br>
3) $pos_i$ is 0 and $c1$ and $c2$ both does not lie in $s_b$, no change in answer.<br>
4) $pos_i$ is $N-1$ and $c1$ lies in $s_a$, after the operation splitting takes place and $ans = ans - ways(len(s_a)+1) + ways(len(1)) + ways(len(s_a)).$<br>
5) $pos_i$ is $N-1$ and $c1$ does not lies in $s_a$, after updation $c2$ lies in $s_a$, so merging takes place. $ans = ans - ways(1) - ways(len(s_a)) + ways(len(s_a)+1).$<br>
6) $pos_i$ is $N-1$ and $c1$ and $c2$ both does not lie in $s_a$, no change in answer.<br>
7) for rest of the cases $pos_i$ lies in between 0 and $N-1$, $s_a = s_b$, i.e. same in color and $c1$ lies in $s_a$, now splitting takes place, $ans = ans - ways(len(s_a)+1+len(s_b)) + ways(len(s_a)) + ways(1) + ways(len(s_b))$.<br>
8) $s_a = s_b$, $c1$ does not lies in $s_a$, $c2$ lies in $s_a$, $ans = ans - + ways(len(s_a)) - ways(1) - ways(len(s_b)) + ways(len(s_a)+1+len(s_b)).$<br>
9) $s_a = s_b$, $c1$ and $c2$ does not lies in $s_a$, no change in answer.<br>
10) $s_a != s_b$, $c1$ lies in $s_a$ and $c2$ lies in $s_b$, $ans = ans - ways(len(s_a)+1)+ways(len(s_a))-ways(len(s_b))+ways(len(s_b)+1)$.<br>
11) $s_a != s_b$, $c1$ lies in $s_a$ and $c2$ does not lie in both, $ans = ans - ways(len(s_a)+1) + ways(1) + ways((len(s_a))$.<br>
12) $s_a != s_b$, $c1$ lies in $s_b$ and $c2$ lies in $s_a$, $ans = ans - ways(len(s_b)+1)+ways(len(s_b))-ways(len(s_a))+ways(len(s_a)+1)$.<br>
13) $s_a != s_b$, $c1$ lies in $s_b$ and $c2$ does not lie in both, $ans = ans - ways(len(s_b)+1) + ways(1) + ways((len(s_b))$.<br>
14) $s_a != s_b$, $c1$ does not lies in both $s_a$ and $s_b$, $c2$ lies in $s_a$, $ans = ans - ways(1)-ways(len(s_a))+ways(len(s_a)+1)$.<br>
15) $s_a != s_b$, $c1$ does not lies in both $s_a$ and $s_b$, $c2$ lies in $s_b$, $ans = ans - ways(1)-ways(len(s_b))+ways(len(s_b)+1)$.<br>
16) $s_a != s_b$, $c1$ and $c2$ does not lies in both $s_a$ and $s_b$, no change in answer.<br></p>
<h1>COMPLEXITY:</h1>
<p>Each query operation requires insertion, deletion of elements from set and answer update, all can be done in $O(log(N))$. For $Q$ queries, overall complexity would be $O(Q*log(N))$.</p>
<h1>ALITER:</h1>
<p>Tester <a href="http://www.codechef.com/users/xcwgf666">Sergey</a> also suggested that above problem can be solved using Segment Tree, which would be much modular approach than handling many cases. <b>HINT:</b> For each node of segment tree stores length of color segment from left and length of color segment from right, color of left and right segment and ans for query for segment range. Update these values accordingly on each query operation.<br>
If you are not able to solve the problem using Segment Tree, go through <a href="http://www.codechef.com/users/xcwgf666">Sergey</a> code in refernces.<br>
</p><p>
<b>AUTHOR'S, TESTER'S and Editorialist's SOLUTIONS:</b>
<br><a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/LTIME22/Setter/PAINTBOX.cpp">author</a><br>
<a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/LTIME22/Tester/PAINTBOX.cpp">tester</a><br>
<a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/LTIME22/Editorialist/PAINTBOX.cpp">editorialist</a><br></p>amanjain110893Thu, 26 Mar 2015 20:47:02 +0530https://discuss.codechef.com/questions/66952/paintbox-editorialsegment-treeltime22mediumsetsASHIGIFT - editorialhttps://discuss.codechef.com/questions/66867/ashigift-editorial<p><b>PROBLEM LINK:</b><br>
<a href="http://www.codechef.com/problems/ASHIGIFT">Practice</a><br>
<a href="http://www.codechef.com/LTIME22/problems/ASHIGIFT">Contest</a><br></p>
<p><b>Author:</b> <a href="http://www.codechef.com/users/pankaj%20jindal">Pankaj Jindal</a>, <a href="http://www.codechef.com/users/piyushkumar">Piyush Kumar</a> <br>
<b>Tester: </b><a href="http://www.codechef.com/users/xcwgf666">Sergey Kulik</a> <br>
<b>Editorialist:</b> <a href="http://www.codechef.com/users/amanjain110893">Aman jain</a><br></p>
<h1>DIFFICULTY:</h1>
<p>Simple</p>
<h1>PREREQUISITES:</h1>
<p>Binary search</p>
<h1>PROBLEM:</h1>
<p>Poor Chef now wants to go to Byteland. On the way to Byteland he found $B$ tasty dishes, each dish requires $B_i$ people to complete, after eating the dish one can't move forward. He can ask support from $C$ tribal clans, found on the way, but on one condition by each clan that is, "they will join only if he approaches them with a group of size atleast $q_i$". Now chef wants to know with what minimum number of people including him he should start his journey to Byteland.
</p><p></p>
<h1>QUICK EXPLANATION:</h1>
<p>Binary search over the range of group size Chef can start with and check whether it is possible to reach Byteland with the group size.</p>
<h1>EXPLANATION:</h1>
<p>Its easy to observe that if there are no tribal clans in the path, then Chef has to start with $x$ = $1+\sum{B_i}$ people to reach Byteland, first sub-task can be solved using this. But how can he minimize number of people on start when help from tribal clans is available? </p>
<p>Basic idea that might struck to your mind would be to try all possible values in range and check what should be minimum size to reach Byteland, one can easily see that the ans would be in range $[1,x]$, since in the worst case no clan members joins you. Complexity of this solution would be $O(x*(B+C))$, where B is number of dishes and C is number of tribal clans, that's about $10^{13}$ computations which do not fit in our time limit.</p>
<p>If Chef start with $x$ people (including him) and can reach Byteland, then if he starts with more than $x$ people, then also he can reach Byteland.</p>
<p>Let $f(n)$: checks whether its possible to reach Byteland with $n$ people or not. You can do binary search over range $[1,x]$ to find out minimum $n$ such that $f(n)$ is true, as answer would lie in range $[1,x]$ only. For binary searching in a range, the idea is to check value of function in mid point of current range and decide to go to one half depending on its value. This will ensure that in $log(x)$ steps we will reach the optimal value.</p>
<p><strong>Pseudocode:</strong> <br>
</p><pre><code>
low = 1, high = x, ans = x
while(low <= high){
m = (low+high)/2
if(possible(m)){
ans = min(ans,m);
high = m-1;
}
else low = m+1;
}
possible(v){
// store dishes and clans in a vector, in increasing order of their distance from Chef's town
// pi,qi,ri are same convention described in problem
for each item in vector:
if item is a dish:
v-=pi
else if v >= qi: v+= ri
return (v>0)
}<p></p>
<p></p></code></pre><p></p>
<h1>COMPLEXITY:</h1>
<p>Binary search takes $O(log(x))$ <br>
Possible function takes $O(B+C)$ <br>
Total complexity should be $O(log(x)*(B+C))$ </p>
<p><b>AUTHOR'S, TESTER'S and Editorialist's SOLUTIONS:</b>
<br><a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/LTIME22/Setter/ASHIGIFT.cpp">author</a><br>
<a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/LTIME22/Tester/ASHIGIFT.cpp">tester</a><br>
<a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/LTIME22/Editorialist/ASHIGIFT.cpp">editorialist</a><br></p>amanjain110893Wed, 25 Mar 2015 16:47:11 +0530https://discuss.codechef.com/questions/66867/ashigift-editorialltime22binary-searchsimpleCHEFANUP - editorialhttps://discuss.codechef.com/questions/66894/chefanup-editorial<p><b>PROBLEM LINK:</b><br>
<a href="http://www.codechef.com/problems/CHEFANUP">Practice</a><br>
<a href="http://www.codechef.com/LTIME22/problems/CHEFANUP">Contest</a><br></p>
<p><b>Author:</b> <a href="http://www.codechef.com/users/pankaj%20jindal">Pankaj Jindal</a>, <a href="http://www.codechef.com/users/piyushkumar">Piyush Kumar</a> <br>
<b>Tester: </b><a href="http://www.codechef.com/users/xcwgf666">Sergey Kulik</a> <br>
<b>Editorialist:</b> <a href="http://www.codechef.com/users/amanjain110893">Aman jain</a><br></p>
<h1>DIFFICULTY:</h1>
<p>Cakewalk</p>
<h1>PREREQUISITES:</h1>
<p>Maths, conversion of number from base 10 to some another base</p>
<h1>PROBLEM:</h1>
<p>Given an array of size $N$, each element in the array can take values $1$ to $K$, find the lexicographically smallest Lth string.</p>
<h1>QUICK EXPLANATION:</h1>
<p>In rest of the solution, will assume 0-based indexing.<br>
$L^{th}$ lexicographically smallest dish would be $(L-1)^{th}$ number in base $K$.</p>
<h1>EXPLANATION:</h1>
<p>Firstly, one should know what is lexicographic ordering,<br>
Lexicographical order is alphabetical order preceded by a length comparison. That is to say, '$a$' string a is lexicographically smaller than a string '$b$', if the length of '$a$' is smaller than the length of '$b$', or else they are of the same length and '$a$' is alphabetically smaller than '$b$'.<br>
Similarly, two array of numbers of equal size can be lexicographically compared as, let<br>
$arr1 = a1,a2,....,an$<br>
$arr2 = b1,b2,....,bn$<br>
then find the first position $i$ from left, such $arr1[i]!=arr2[i]$, then if $arr1[i] > arr2[i]$ $arr1$ is lexicographically greater else $arr2$. </p>
<p>Before jumping to final solution, let's see how each sub-task can be solved: <br>
<b>First subtask</b> has $N <= 3$, each position can be filled with $K$ possibilities leading to $O(N^{K})$ solution. We can use three nested loops to assign value at each position and count each assignment, once total number of iterations reaches $L$ we can print current assigned values.<br><br>
<b>Second subtask</b>, we start from smallest lexicographic ordering i.e. $0,0...,0$. We can find next ordering by adding $1$ at the Least significant position, this addition is in $(mod K)$ space. Keep adding $1$ to LSB for $(L-1)$ times and we will get $L^{th}$ smallest lexicographically ordering. Complexity will be $O(N*L)$ </p>
<p><strong>Final solution</strong> <br>
When we write series of numbers $0,1,2,....m$ in base $K$ we will find that they are lexciographically sorted. For ex:<br>
0(base 10) = 000(base 2)<br>
1 = 001<br>
2 = 010<br>
3 = 011<br>
4 = 100<br>
5 = 101<br>
6 = 110<br>
7 = 111<br>
Series in base 2 is lexicographically sorted. This works for all bases.<br>
Now our problem wants us to find $L^{th}$ lexicographically smallest position, such that each position is filled by numbers from $0$ to $K-1$ i.e. base $K$. So our answer should be $(L-1)$ expressed in base $K$. [<b>NOTE</b>: $(L-1)$ not $L$ because its $0$ based indexing.]<br></p>
<p><strong>Pseudocode:</strong> <br>
<code>
ans[n] = {0}; // initialize an array of size n to 0
co = n-1;
while(L > 0){
ingredient = L%K;
ans[co] = ingredient;
--co;
L /= K;
}
// we assumed 0 based indexing but final answer expects 1 based
for i from 0 to n-1: ans[i] += 1;
</code></p>
<h1>COMPLEXITY:</h1>
<p>$L$ can have max value of $K^{n}$, so complexity of solution would be $O(log_K(L))$ i.e. $O(n)$</p>
<p><b>AUTHOR'S, TESTER'S and Editorialist's SOLUTIONS:</b>
<br><a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/LTIME22/Setter/CHEFANUP.cpp">author</a><br>
<a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/LTIME22/Tester/CHEFANUP.cpp">tester</a><br>
<a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/LTIME22/Editorialist/CHEFANUP.cpp">editorialist</a><br></p>amanjain110893Wed, 25 Mar 2015 20:26:20 +0530https://discuss.codechef.com/questions/66894/chefanup-editorialmathsltime22cakewalkUNPAIR - editorialhttps://discuss.codechef.com/questions/66903/unpair-editorial<p><b>PROBLEM LINK:</b><br>
<a href="http://www.codechef.com/problems/UNPAIR">Practice</a><br>
<a href="http://www.codechef.com/LTIME22/problems/UNPAIR">Contest</a><br></p>
<p><b>Author:</b> <a href="http://www.codechef.com/users/pankaj%20jindal">Pankaj Jindal</a>, <a href="http://www.codechef.com/users/piyushkumar">Piyush Kumar</a> <br>
<b>Tester: </b><a href="http://www.codechef.com/users/xcwgf666">Sergey Kulik</a> <br><b>Editorialist:</b> <a href="http://www.codechef.com/users/amanjain110893">Aman jain</a><br></p>
<h1>DIFFICULTY:</h1>
<p>medium-hard</p>
<h1>PREREQUISITES:</h1>
<p>Minimum Spanning Tree(MST), Matrix Exponentiation and its relation to count number of walks in a graph.<br>
You can learn about <a href="https://community.topcoder.com/tc?module=Static&d1=features&d2=010408">Matrix Exponentiation</a> and
<a href="http://www.geeksforgeeks.org/greedy-algorithms-set-2-kruskals-minimum-spanning-tree-mst/">MST</a> here.
<br></p>
<h1>PROBLEM:</h1>
<p>Given a $N*N$ symmetric matrix $M$ , construct a matrix $P$ such that $P$ is also symmetric, $P[i][j]$ equals to $M[i][j]$ or 0 and $SUM$ = $P^{1}+P^{2}+......+P^{S} > 0$ for some $S > 0$. You need to minimize the sum of all elements of $P$.</p>
<h1>QUICK EXPLANATION:</h1>
<p>Each value pair $(i,j)$ in matrix $M$ defines a edge of length $M[i][j]$. Then, $P$ should be a matrix that represents MST on matrix $M$.</p>
<h1>EXPLANATION:</h1>
<p>Our aim is to construct a matrix $P$ from $M$ such that sum of all elements of $P$ is minimum. <br>
Here matrix $SUM > 0$, means each and every element of $SUM$ matrix is greater than 0. <br>
Let each element $M(i,j)$ be a edge from node(i) to node(j) with weight $M[i][j]$ if $M[i][j] > 0$. Correspondingly, each positive $P(i,j)$ would represent edge with from node(i) to node(j) with weight $P[i][j]$.</p>
<p>According to theory of Matrix Exponentiation, each element in $P^{k}$, would represent number of walks of length $k$ from node(i) to node(j). $SUM[i][j] = 0$, would mean that number of walks of non zero length between node(i) and node(j) is zero. It means that node(i) and node(j) are not connected to each other. So the underlying graph for representing P should be connected. Otherwise there will be zero entries in $SUM$ matrix.</p>
<p>For the <b>first subtask</b>, $N <= 5$, which means number of elements in $M$ is atmost 25 and since matrix $M$ and $P$ are symmetric, we need to consider diagonal and upper-diagonal elements for making $P$ i.e. total of $N*(N+1)/2$ elements. We have two choices for $P[i][j]$ either $M[i][j]$ or $0$ i.e. atmost $2^{N*(N+1)/2}$ possibilities. From above discussion, we know that graph represented by $P$ has to be connected to make $SUM > 0$, so from all possibilities choose $P$ which is connected and has minimum sum, that would be our solution. Complexity should be $O(2^{N*(N+1)/2}*N*(N+1)/2)$, which is about $5*10^{7}$ computations that will run within limit for first sub-task but poorly performs on final task.</p>
<p>It is clear that optimal $P$ is connected graph with minimal total sum of its edges, if you see this is the definition of MST. Here you may think that why we are ditching self-loops and how $SUM[i][i] > 0$, if we neglect self loops i.e. $P[i][i]=0$, this is because every even walk of length $l$, would make $P^l[i][i] > 0$. For ex: a->b->a is walk of length 2, so $P^2[i][i] > 0$, correspondingly $SUM[i][i] > 0$ for $S >= 2$.</p>
<p>Since matrix $P$ is symmetric, sum of all its elements would be twice the sum of edges in MST.</p>
<h1>COMPLEXITY:</h1>
<p>Number of Edges(E) in our graph is $N^{2}$, constructed from $M$. <br>
Number of Vertices(V) in our graph is $N$. <br>
Complexity of constructing MST is $O(Elog(E) + Elog(V))$ i.e. $O(N^{2}log(N))$, which is the overall complexity of our solution. </p>
<p>
<b>AUTHOR'S, TESTER'S SOLUTIONS:</b>
<br><a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/LTIME22/Setter/UNPAIR.cpp">author</a><br>
<a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/LTIME22/Tester/UNPAIR.cpp">tester</a><br></p>amanjain110893Wed, 25 Mar 2015 22:09:56 +0530https://discuss.codechef.com/questions/66903/unpair-editorialltime22mstmedium-hardgraph-theory