Questions Tagged With ltime14https://discuss.codechef.com/tags/ltime14/?type=rssquestions tagged <span class="tag">ltime14</span>enSun, 27 Jul 2014 14:47:37 +0530TAEDITOR - Editorialhttps://discuss.codechef.com/questions/48549/taeditor-editorial<p><strong>Problem link</strong> : <a href="http://www.codechef.com/LTIME14/problems/TAEDITOR">contest</a> <a href="http://www.codechef.com/problems/TAEDITOR">practice</a> </p>
<p><strong>Difficulty</strong> : Medium </p>
<p><strong>Pre-requisites</strong> : Strings, Segment Tree/BIT</p>
<p><strong>Problem</strong> : </p>
<p>You need to implement two kinds of query on a string S: </p>
<ol>
<li>Insert a string in a specific position. </li>
<li>Print out a specific sub-string of S. </li>
</ol>
<h2>Explanation</h2>
<p>At first, let's consider some partial solutions. </p>
<h3>How to get 20/50 points</h3>
<p>Just use the built-in library in you language. You will pass this sub-task with that. You might even pass the second subtask.</p>
<h3>How to get 100 points</h3>
<p>Firstly, we can simplify the problem by converting the queries so that we deal with the characters only. </p>
<ol>
<li>Inserting a string x = c_1,c_2,..,c_m after the i'th character of S is equivalent to m queries of inserting the character c_1 after the i'th character of S and then inserting the character c_2 after the (i+1)'th character of S and so on until c_m. </li>
<li>Query about the sub-string of length m starts at position i of S means you have to know what character is in the position i, i + 1 and i + m - 1 of S.</li>
</ol>
<p>So, we'll process each query character by character. We break each update query in updation of various single characters and second query into retrieval of many single characters.</p>
<p>First we find out what will be the length of the final string, which is very easy. Let N be the length of the final string, so we have N positions, numbered from 1 to N. Consider all the query in the inverse order, for each query we will convert the given positions into the corresponding final value. It is pretty straight forward. For example you are given to update/query the k'th character. Position k means it is the k'th smallest position among the "available" positions. We use the word "available" here because after you visit an insert query, you must remove the position that that query used since it is not available for the previous insert queries.</p>
<p>An example will make it more clear. Let's consider the sample input given in question.</p>
<pre><code>5
+ 0 ab
+ 1 c
? 1 3
+ 2 dd
? 1 5
</code></pre>
<p>We break our queries first. Our queries are:</p>
<pre><code>+ 0 a
+ 1 b
+ 1 c
? 1
? 2
? 3
+ 2 d
+ 3 d
? 1
? 2
? 3
? 4
? 5
</code></pre>
<p>We know the final length of string is 5. Right now all positions from 1 to 5 are empty. We'll start processing the queries in inverse order. <br>
For, "? 5" the 5'th smallest position available is 5. So we know our answer will be the 5'th character. Similarily for the "? 4", "? 3", "? 2" and "? 1". <br>
Now, "+ 3 d", what is the 4'th smallest available position? 4 is available. So we mark ANS[4]='d'. <br>
Now, "+ 2 d", what is the 3'rd smallest available position? 2 is available. So we mark ANS[3]='d'. <br>
Now, "? 3", what is the 3'rd smallest available position.(1,2,5 are empty). So, our answer to this query will be ANS[5]. <br>
Now, "? 2", what is the 2'nd smallest available position.(1,2,5 are empty). So, our answer to this query will be ANS[2]. <br>
Now, "? 1", what is the 1'st smallest available position.(1,2,5 are empty). So, our answer to this query will be ANS<a href="http://www.codechef.com/LTIME14/problems/TAEDITOR">1</a>. <br>
Now, "+ 1 c", what is the 2'nd smallest available position? 2 is available. So we mark ANS[2]='c'. <br>
Now, "+ 1 b", what is the 2'nd smallest available position? 5 is available. So we mark ANS[5]='b'. <br>
Now, "+ 0 a", what is the 1'st smallest available position? 1 is available. So we mark ANS<a href="http://www.codechef.com/LTIME14/problems/TAEDITOR">1</a>='a'. </p>
<p>For all "?" queries we know what answer will be. After building the whole string we just have to process those queries in chronological order. </p>
<p>Now, the problem is how do we find the k'th smallest position available? <br>
Suppose right now we have an array of 1's and 0's where arr[i]=1 if the i'th position is not available. How do we go about finding the k'th smallest position available? <br>
SUM[arr[i], i=1 to j] is an non-decreasing function on j. So, we can apply binary search on j to find the answer. <br>
But, once we mark and arr[i]=0, we'll have to calculate the prefix sum again and again. Here comes into play the <a href="http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees">Binary Indexed Trees</a>. Using them we can mark/unmark in log(N) complexity and find the prefix sum also in log(N). So complexity here would be O(log N * log N) since each query will take O(log N). This solution should pass. <br>
Another method to achieve better complexity would be balanced binary search tree or splay trees. Here on an average, the complexity is O(log N) for searching the K'th smallest element. Also, add/remove in O(log N).</p>
<p>So, our problem is solved. :) </p>
<p><strong>Solutions</strong> : <a href="http://www.codechef.com/download/Solutions/LTIME14/Setter/TAEDITOR.cpp">setter</a> <a href="http://www.codechef.com/download/Solutions/LTIME14/Tester/TAEDITOR.cpp">tester</a></p>
<p><strong>Clarification</strong>: It was realised during the contest that brute force solutions are getting accepted, even though testdata was strong. Tester/Setter's brute force solutions during testing phase were not getting accepted. We apologise for this.</p>darkshadowsSun, 27 Jul 2014 14:47:22 +0530https://discuss.codechef.com/questions/48549/taeditor-editorialsegment-treebitstringsmedium-hardltime14TAAND - Editorialhttps://discuss.codechef.com/questions/48551/taand-editorial<p><strong>Problem link</strong> : <a href="http://www.codechef.com/LTIME14/problems/TAAND">contest</a> <a href="http://www.codechef.com/problems/TAAND">practice</a></p>
<p><strong>Difficulty</strong> : Simple</p>
<p><strong>Pre-requisites</strong> : Basic Math, Recursion, Bit Operations</p>
<p><strong>Problem</strong> : Given an array find maximum AND(&) possible between any two elements.</p>
<h2>Explanation</h2>
<p>At first, let's consider some partial solutions.</p>
<h3>How to get 50 points</h3>
<p>Here you can go through each possible pair and check what AND value is. And we can find what is the maximum AND possible. Complexity of this will be O(N*N).</p>
<pre><code>n=input()
arr=[]
ans=-1
for i=1 to n:
arr[i]=input()
for i=1 to n:
for j=i+1 to n:
ans = max( ans, arr[i]&arr[j] )
</code></pre>
<h3>How to get 100 points</h3>
<p>When we are ANDing two numbers, we would like to have a 1 at the most significant bit(MSB). So, first we'll try to get a 1 at MSB. Now, suppose we denote A[i]=b_i<sub>n</sub>,b_i<sub>n-1</sub>...b_i<sub>0</sub>, where b_i's are the bits that could be 1 or 0.</p>
<p>Let's say S be the set of A[i] whose b_i<sub>n</sub> is 1 and S' be the set of A[i] whose b_i<sub>n</sub> is 0. If size of S ≥ 2 we are sure that our answer will be maximum if we chose a pair of numbers from S, because n'th bit of their AND will be 1 for sure. So, we know our answer lies in S.</p>
<p>However, if size of S is less than 2, we can never have n'th bit 1 in our answer. So, we'll have to continue with n'th bit as 0. Note that our answer will now be in S'.</p>
<p>Now, we know our answer is in S or S' and we also know n'th bit of our answer. So, our new subproblem is to find (n-1)'th bit of our answer using numbers in S or S'. We can write a recursive code for this.
What will be the complexity? For each of the n bits, we'll traverse whole array to sort according to their bits. So O(n*N). We will be keeping n=30, because A[i] ≤ 10<sup>9</sup>.</p>
<pre><code>n=input()
arr=[]
flag[n]={}
for i=0 to n-1:
arr[i]=input()
print foo(30)
def foo(level): //this function will find the level'th bit
//and accordingly return answer
if level==-1: // we already have solved for all bits. return 0 from here
return 0
Scount=0 // stores the size of set S
ans=0 // the answer in decimal form
for i=0 to n-1:
if flag[i]==0: // flag[i]=0 means arr[i] is available for us to use
if (arr[i]&(1<<level)): // level'th bit of arr[i] is 1
Scount++
if Scount>=2: // our answer's level'th bit will be 1
ans += (1<<level)
// but we also have to set the flag of unavailable numbers
for i=0 to n-1:
if (arr[i]&(1<<level))==0: // level'th bit is 0, set the flag
flag[i]=1
return ans+foo(level-1); // return the current answer + answer for the next bit
</code></pre>
<p><strong>Solutions</strong> : <a href="http://www.codechef.com/download/Solutions/LTIME14/Setter/TAAND.cpp">setter</a> <a href="http://www.codechef.com/download/Solutions/LTIME14/Tester/TAAND.cpp">tester</a></p>darkshadowsSun, 27 Jul 2014 14:47:37 +0530https://discuss.codechef.com/questions/48551/taand-editorialad-hocbitwise-operatneasy-mediumltime14TALCA - Editorialhttps://discuss.codechef.com/questions/48548/talca-editorial<p><strong>Problem link</strong> : <a href="http://www.codechef.com/LTIME14/problems/TALCA">contest</a> <a href="http://www.codechef.com/problems/TALCA">practice</a> </p>
<p><strong>Difficulty</strong> : Medium </p>
<p><strong>Pre-requisites</strong> : <a href="http://wcipeg.com/wiki/Lowest_common_ancestor">Lowest Common Ancestor</a>, Trees </p>
<p><strong>Problem</strong> : Given a tree, you have to answer the question of the format "r u v" which means which is the LCA of u and v if the root of the tree is at r. </p>
<h2>Explanation</h2>
<p>At first, let's consider some partial solutions. </p>
<h3>How to get 20 points</h3>
<p>For this sub-task you an find the LCA in any way you want as long as the complexity is not slower than O(N). For example, by DFS from the root, you can number the vertices so that given two arbitrary vertices, you can check whether they are ancestor and descendant(for this, you can store T_in and T_out for each node. T_in is the time when the DFS for that node was begun. T_out is the time when the DFS was over).</p>
<h3>How to get 60 points</h3>
<p>Here there are not more than 10 different roots, but the queries are quite high, so you should know the fast way to find LCA. More specifically O(Nlog(N)) is enough. Notice that there will be no more than 10 different roots so your complexity will be O(10 × Nlog(N)).</p>
<h3>How to get 100 points</h3>
<p>There are two interesting observations that you can make: </p>
<ol>
<li>
<p>Given the query "r u v" what can be the answer? The possible answers are <b>r</b>, <b>u</b>, <b>v</b>, <b>LCA(r, u)</b>, <b>LCA(r, v)</b>, <b>LCA(u, v)</b> where <b>LCA(x, y)</b> is LCA of <b>x</b> and <b>y</b> when the tree is rooted at 1. </p>
</li>
<li>
<p>The LCA of u and v when the root is at r is the vertex x such that the sum of shortest path from x to u, x to v and x to r is smallest. </p>
</li>
</ol>
<p>With this two observations you need to implement two function: finding LCA and distance of the two vertices in the tree. Proof for these two observation is not hard but too long to be mentioned here. It is left as an exercise for you. </p>
<p><strong>Solutions</strong> : <a href="http://www.codechef.com/download/Solutions/LTIME14/Setter/TALCA.cpp">setter</a> <a href="http://www.codechef.com/download/Solutions/LTIME14/Tester/TALCA.cpp">tester</a></p>darkshadowsSun, 27 Jul 2014 14:46:57 +0530https://discuss.codechef.com/questions/48548/talca-editorialltime14treemedium-hardlcaTASHIFT - Editorialhttps://discuss.codechef.com/questions/48550/tashift-editorial<p><strong>Problem link</strong> : <a href="http://www.codechef.com/LTIME14/problems/TASHIFT">contest</a> <a href="http://www.codechef.com/problems/TASHIFT">practice</a></p>
<p><strong>Difficulty</strong> : Simple</p>
<p><strong>Pre-requisites</strong> : Strings, KMP</p>
<p><strong>Problem</strong> : Given two String A and B of the same length. You can do some (may be none) shift operations which results in the first character of B moving to the end. What is the minimum number of operations that are needed so that B has the longest common prefix with A. </p>
<h2>Explanation</h2>
<p>At first, let's consider some partial solutions. </p>
<h3>How to get 30 points</h3>
<p>Just try implement the shift operations in O(N) and try all possible numbers of Shift operations on B. You properly even do not need write so much code if your language have some built-in library for string. You also do not have to do anything to speed up the string comparison. The overall complexity is O(N<sup>2</sup>). </p>
<h3>How to get 60 points</h3>
<p>Let's say we append string B at the end of string B. We get: B<sub>1</sub>,B<sub>2</sub>...B<sub>N</sub>B<sub>1</sub>,B<sub>2</sub>...B<sub>N</sub>. The thing worth noting is that after K shift operations we get B<sub>K+1</sub>,B<sub>K+2</sub>...B<sub>N</sub>,B<sub>1</sub>,B<sub>2</sub>...B<sub>K</sub>. This string(which we get after K shift operations) is now a substring of the new string that we got by appending B at the end of B. <br>
So we'll now search all prefixes of A in B.B(means concatanation of B with B) which will help us in knowing which prefixes of A are present in B.B.
Let's say we have to search a string A of length M in a string B of length N. What we can do is generate hash of all substrings of B which are of length M and search for hash of string A in the generated hashes. <br>
A hash function of string S could be say Summation[i=0 to length][26<sup>i</sup>*(S[i]-'a')] modulo some prime P. If we have the hash of a substring of length N say S[i,i+N], we can easily generate hash of S[i+1,i+N+1] by using inverse modulo since we are using a prime for modulo operations.</p>
<h3>How to get 100 points</h3>
<p>You need to know string matching algorithm KMP to get full points. You can learn KMP <a href="http://www.inf.fh-flensburg.de/lang/algorithmen/pattern/kmpen.htm">here</a>, <a href="http://www.ics.uci.edu/~eppstein/161/960227.html">here</a>, or anywhere you like to :).<br>
KMP helps us in finding all prefixes of a string X in string Y. So we'll search A in B.B(means concatanation of B with B) which will help us in knowing which prefixes of A are present in B.B. We'll choose an answer that gives us the largest prefix, also it'll give the index at which that prefix matches, from which we can find the number of shifts required. </p>
<p><strong>Solutions</strong> : <a href="http://www.codechef.com/download/Solutions/LTIME14/Setter/TASHIFT.cpp">setter</a> <a href="http://www.codechef.com/download/Solutions/LTIME14/Tester/TASHIFT.cpp">tester</a></p>darkshadowsSun, 27 Jul 2014 14:47:29 +0530https://discuss.codechef.com/questions/48550/tashift-editorialmediumstringsltime14kmp