Questions Tagged With may13https://discuss.codechef.com/tags/may13/?type=rssquestions tagged <span class="tag">may13</span>enThu, 16 May 2013 05:56:36 +0530CHALENGE  Editorialhttps://discuss.codechef.com/questions/10136/chalengeeditorial<h1>PROBLEM LINKS</h1>
<p><a href="http://www.codechef.com/problems/CHALENGE">Practice</a><br>
<a href="http://www.codechef.com/MAY13/problems/CHALENGE">Contest</a></p>
<h1>DIFFICULTY</h1>
<p>CHALENGE</p>
<h1>PREREQUISITES</h1>
<p>AdHoc, Brute Force</p>
<h1>PROBLEM</h1>
<p>You are given N servers, out of which a vast majority are honeypots. You have to guess the passwords at these servers. You know that the servers mix the passwords with some random salt, and then compare SHA1 hashes of both the strings.</p>
<p>The score is equal to the sum of the square of the number of bits correctly matched. Honeypot servers do not affect the score at all.</p>
<h1>EXPLANATION</h1>
<p>Firstly, you can try to find which servers are honeypot servers.</p>
<p>This can be done by first getting a reference score by using some a set of passwords initially; then</p>
<ul>
<li>Change a single password to some other string</li>
<li>If the score changes, then that server is not honeypot</li>
<li>Otherwise the server is honeypot</li>
</ul>
<p>Since we know that the density of honeypot servers is high, we can be smarter and try to find blocks of honeypot servers together. In case we find the score did change for the block of servers we were hoping to be honeypot, we can then try them one by one.</p>
<p>After finding the honeypot servers, we must now try to find the passwords.</p>
<p>The chances of finding the exact password in this problem for any server are extremely narrow. Because of the nature of SHA1, you cannot even hope to change a string ever so slightly to try and get a better result.</p>
<p>Your best bet is to generate random strings and see which one gets you closer to better and better scores.</p>
<p>One method is to only generate random strings and then try to run the corpus of random strings for each server (of course not for honeypots) while keeping all the other strings constant to try and maximize the score.</p>
<p>This is what the tester's solution does. You have to be careful that you should not exceed the number of attepts you have.</p>
<h1>SETTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2013/May/Setter/CHALENGE.cpp">here</a>.</p>
<h1>TESTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2013/May/Tester/CHALENGE.cpp">here</a>.</p>gamabuntaThu, 16 May 2013 05:56:36 +0530https://discuss.codechef.com/questions/10136/chalengeeditorialbruteforcemay13adhocchallengeeditorialinteractiveJUNONGF  Editorialhttps://discuss.codechef.com/questions/9733/junongfeditorial<h1>PROBLEM LINKS</h1>
<p><a href="http://www.codechef.com/problems/JUNONGF">Practice</a><br>
<a href="http://www.codechef.com/MAY13/problems/JUNONGF">Contest</a></p>
<h1>DIFFICULTY</h1>
<p>MEDIUM</p>
<h1>PREREQUISITES</h1>
<p>Math, <a href="http://en.wikipedia.org/wiki/Exponentiation_by_squaring">Repeated Squaring</a>, <a href="http://en.wikipedia.org/wiki/Fermat's_little_theorem">Fermat's Little Theorem</a></p>
<h1>PROBLEM</h1>
<p>You are given a <b>N</b> dimensional hyper rectangle. You have to fill each cell in the hyper rectangle with a value between <b>0</b> and <b>V1</b>, inclusive, such that the sum of all the values in each <b>1dimensional slice</b> of the hyper rectangle is divisible by <b>V</b>, which is also given.</p>
<p>Find the number of ways of filling the cells with the values.</p>
<h1>QUICK EXPLANATION</h1>
<p>Let the dimensions of the hyper rectangle be given in an array D = { D<sub>1</sub>, D<sub>2</sub>, ... D<sub>N</sub> }.</p>
<p>Assume we fill the each of the following cells of the hyper rectangle with any arbitrary value from 0 to V1 of our choosing</p>
<ul>
<li>Fill { x<sub>1</sub>, x<sub>2</sub>, ... x<sub>N</sub> } iff<ul>
<li>x<sub>1</sub> < D<sub>1</sub> AND</li>
<li>x<sub>2</sub> < D<sub>2</sub> AND</li>
<li>so on..</li>
</ul>
</li>
</ul>
<p>The rest of the cells that have not been filled can only be filled by singular values that satisfy the divisibility constraint.</p>
<p>Take for example a hyperrectangle { 4, 4, 3 } and V = 10. Suppose we fill all the cells as described above arbitrarily. There are of course 10<sup>3*3*2</sup> ways of filling them. Now, when we take any slice of this hyperrectangle, we find that</p>
<ul>
<li>Either the cell is filled by a value of our choosing</li>
<li>The value of the cell is being forced by some or the other 1dimensional slice</li>
</ul>
<p>All except one value in each slice will be prefilled or forced, and the last value is of course being forced by the constraint that the sum of all the values in this slice must be divisible by V.</p>
<p>Thus, the answer for each case is going to be</p>
<p>V<sup>(D<sub>1</sub>1)(D<sub>2</sub>1)...(D<sub>N</sub>1)</sup></p>
<h1>EXPLANATION</h1>
<p>V is a 64bit integer. But we want to find the result modulo 1000000007. Thus, we can instantly change V to the remainder modulo 1000000007.</p>
<p>Given that each of the dimensions are 64bit integers, it is obvious that the exponent of V for the answer is potentially very large. It is potentially a 6400bit integer. Repeated squaring to find the result of V<sup>6400bitinteger</sup> will take 6400 iterations. This is too many iterations per test case.</p>
<p>We require Fermat's Little Theorem to solve the problem now.</p>
<pre>a<sup>p1</sup> = 1 modulo p
for some prime p
</pre>
<p>We know that 1000000007 is prime. Thus we can find</p>
<pre>T = (D<sub>1</sub>  1)(D<sub>2</sub>  1) ... (D<sub>N</sub>  1) modulo 1000000006
</pre>
<p>and find V<sup>T</sup> modulo 1000000007.</p>
<p>There is one edge case that deserves special mention. V modulo 1000000007 may or may not be 0. If it is not 0, then we have no problems. But if it is 0 there is a special case that should be carefully handled. This is the case where one or more dimension is equal to 1. In this case, all the values in the hyper rectangle must be 0. This is because every cell is a single dimensional slice in a dimension that is equal to 1. Thus the answer in that case should be 1, instead of 0 (meaning the answer is actually 1, and not a multiple of 1000000007).</p>
<p>Of course, as evil as the setter and the tester are, there is no shortage of this case among the judge test cases.</p>
<h1>SETTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2013/May/Setter/JUNONGF.cpp">here</a>.</p>
<h1>TESTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2013/May/Tester/JUNONGF.cpp">here</a>.</p>gamabuntaTue, 14 May 2013 15:39:10 +0530https://discuss.codechef.com/questions/9733/junongfeditorialmediummay13exponentiationnumbertheorysimplematheditorialTREE  Editorialhttps://discuss.codechef.com/questions/9727/treeeditorial<h1>PROBLEM LINKS</h1>
<p><a href="http://www.codechef.com/problems/TREE">Practice</a><br>
<a href="http://www.codechef.com/MAY13/problems/TREE">Contest</a></p>
<h1>DIFFICULTY</h1>
<p>EASY</p>
<h1>PREREQUISITES</h1>
<p><a href="http://en.wikipedia.org/wiki/Kirchhoff's_theorem">Kirchhoff's Matrix Tree Theorem</a>, Math</p>
<h1>PROBLEM</h1>
<p>Find the number of Trees that contain <b>k*n</b> nodes, which are labeled from <b>0</b> to <b>k*n1</b>, such that</p>
<ul>
<li>There is no edge between two vertices <b>a</b> and <b>b</b> for which <b>a div k = b div k</b>, where <b>div</b> is the <b>integer</b> <b>division</b> operator</li>
</ul>
<h1>QUICK EXPLANATION</h1>
<p>Let us assume there is a graph on <b>k*n</b> vertices such that for any two vertices <b>a</b> and <b>b</b>, if <b>a</b> <b>div</b> <b>k</b> is not equal to <b>b</b> <b>div</b> <b>k</b>, there is an edge between them. On such a graph, every unique <b>spanning</b> <b>tree</b> is a valid tree according to the definition of the problem statement.</p>
<p>Since there are only <b>3</b> possible different values of <b>k</b>, let us consider them one by one.</p>
<h2>k = 1</h2>
<p>The <b>Kirchhoff's</b> <b>Matrix</b> for a graph with <b>n</b> vertices will look like</p>
<pre>n1 1 1 ... 1
1 n1 1 ... 1
1 1 n1 ... 1
...
1 1 1 ... n1
</pre>
<p>We have to find the the <b>determinant</b> of any <b>cofactor</b> of the above matrix to find the number of spanning trees. Let us consider the <b>(n,n)</b> <b>cofactor</b>.</p>
<pre>n1 1 1 ... 1
1 n1 1 ... 1
1 1 n1 ... 1
...
1 1 1 ... n1
</pre>
<p>The <b>(n,n)</b> <b>cofactor</b> consists of <b>n1</b> rows and <b>n1</b> columns.</p>
<p>The determinant of the above matrix will give us the answer for <b>k = 1</b>. Let us perform some operations that do not affect the determinant and make the matrix <b>triangular</b>. This way the determinant is found as the <b>product of the terms in the major diagonal</b>.</p>
<p>Starting from the top row and proceeding downwards, let us subtract the next row from the current row. Thus</p>
<ul>
<li>Subtract row 2 from row 1</li>
<li>Subtract row 3 from row 2, and so on</li>
</ul>
<pre> n n 0 ... 0 0
0 n n ... 0 0
0 0 n ... 0 0
....
0 0 0 ... n n
1 1 1 ... 1 n1
</pre>
<ul>
<li>We can use the rows 1 to n2 to eliminate the first 1 in row n1</li>
<li>We can use the rows 2 to n2 to eliminate the second 1 in row n1, and so on</li>
</ul>
<p>Eventually we get</p>
<pre> n n 0 ... 0 0
0 n n ... 0 0
...
0 0 0 ... n n
0 0 0 ... 0 1
</pre>
<p>Thus, the answer for <b>k = 1</b> is <b>n<sup>n2</sup></b>.</p>
<p>The analysis for <b>k = 2</b> and <b>k = 3</b> are much more involved.</p>
<h1>EXPLANATION</h1>
<h2>k = 2</h2>
<p><b>(2n,2n)</b> <b>cofactor</b> of the Kirchhoff's Matrix for a graph with <b>2*n</b> nodes will look like</p>
<pre> 2n2 0 1 1 ... 1 1 1
0 2n2 1 1 ... 1 1 1
1 1 2n2 0 ... 1 1 1
1 1 0 2n2 ... 1 1 1
...
1 1 1 1 ... 2n2 0 1
1 1 1 1 ... 0 2n2 1
1 1 1 1 ... 1 1 2n2
</pre>
<p>It contains <b>2n1</b> rows and <b>2n1</b> columns. Similar to how we subtracted the next row from the current one for k = 1, we will subtract the next row from the current one, starting from the top row and working downwards.</p>
<pre> 2n2 (2n2) 0 0 ... 0 0 0
1 2n1 (2n1) 1 ... 0 0 0
0 0 2n2 (2n2) ... 0 0 0
0 0 1 2n1 ... 0 0 0
...
0 0 0 0 ... 2n2 (2n2) 0
0 0 0 0 ... 1 2n1 (2n1)
1 1 1 1 ... 1 1 2n2
</pre>
<p>We can use the first row to eliminate terms on the left of the major diagonal in the second row. Similarly, we can use the third row to eliminate terms on the left of the major diagonal in the fourth row, and so on.</p>
<pre> 2n2 (2n2) 0 0 ... 0 0 0
0 2n (2n1) 1 ... 0 0 0
0 0 2n2 (2n2) ... 0 0 0
0 0 0 2n ... 0 0 0
...
0 0 0 0 ... 2n2 (2n2) 0
0 0 0 0 ... 0 2n (2n1)
1 1 1 1 ... 1 1 2n2
</pre>
<p>We can use row 3 on row 2, row 5 on row 4 and so on to convert the matrix into</p>
<pre> 2n2 (2n2) 0 0 ... 0 0 0
0 2n 0 2n ... 0 0 0
0 0 2n2 (2n2) ... 0 0 0
0 0 0 2n ... 0 0 0
...
0 0 0 0 ... 2n2 (2n2) 0
0 0 0 0 ... 0 2n (2n1)
1 1 1 1 ... 1 1 2n2
</pre>
<p>Now we can convert the final row using all the previous rows into</p>
<pre> 2n2 (2n2) 0 0 ... 0 0 0
0 2n 0 2n ... 0 0 0
0 0 2n2 (2n2) ... 0 0 0
0 0 0 2n ... 0 0 0
...
0 0 0 0 ... 2n2 (2n2) 0
0 0 0 0 ... 0 2n (2n1)
0 0 0 0 ... 0 (2n2) 2n2
</pre>
<p>The last row can reduce the second to last row into</p>
<pre> 2n2 (2n2) 0 0 ... 0 0 0
0 2n 0 2n ... 0 0 0
0 0 2n2 (2n2) ... 0 0 0
0 0 0 2n ... 0 0 0
...
0 0 0 0 ... 2n2 (2n2) 0
0 0 0 0 ... 0 1 0
0 0 0 0 ... 0 (2n2) 2n2
</pre>
<p>Of course the matrix is triangular now and the determinant is simply the product of the terms in the major diagonal. There are <b>n</b> occurances of <b>2n2</b> and <b>n2</b> occurances of <b>2n</b> in the major diagonal.</p>
<p>Thus, the answer for <b>k=2</b> is <b>(2n)<sup>n2</sup>(2n2)<sup>n</sup></b>.</p>
<p>We leave <b>k = 3</b> as an exercise to the reader. As a matter of fact, this month's tester David proved during the testing of this problem that there is a closed form for any k that can be calculated using the same ideas presented above for <b>k = 1</b> and <b>k = 2</b>. The result for any <b>k</b> is</p>
<p><b>(k*n)<sup>n2</sup>(k*(n1))<sup>(k1)*n</sup></b></p>
<p>The limits were intentionally kept <b>low</b> <b>enough</b> to not let the existance of closed form solution be apparent.</p>
<h1>SETTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2013/May/Setter/TREE.cpp">here</a>.</p>
<h1>TESTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2013/May/Tester/TREE.cpp">here</a>.</p>gamabuntaTue, 14 May 2013 15:30:40 +0530https://discuss.codechef.com/questions/9727/treeeditorialeditorialmay13treekirchhoffeasymathsCPP  Editorialhttps://discuss.codechef.com/questions/10100/cppeditorial<h1>PROBLEM LINKS</h1>
<p><a href="http://www.codechef.com/problems/CPP">Practice</a><br>
<a href="http://www.codechef.com/MAY13/problems/CPP">Contest</a></p>
<h1>DIFFICULTY</h1>
<p>HARD</p>
<h1>PREREQUISITES</h1>
<p>String Parsing, Predictive Parsing of an LL(1) Grammar, Regular Expressions</p>
<h1>PROBLEM</h1>
<p>You are given a string which defines what an ID should look like followed by a list of IDs. You have to report which one of them are valid.</p>
<h1>QUICK EXPLANATION</h1>
<p>Refer to the problem statement to carefully understand the description of the grammar for parsing the expressions that describe the valid IDs for each test case. Following that description should lead you to the following <a href="http://en.wikipedia.org/wiki/Contextfree_grammar">context free grammar</a> (from the Problem Setter's notes).</p>
<pre><b>Tokens</b>
or : "or"
times : "times"
optional: "optional"
letter : "letter"
letters : "letters"
digit : "digit"
digits : "digits"
to : "to"
exactly : "exactly"
upto : "upto"
l : [AZ]
d : [09]
num : [09]{2,} //take care of leading zeroes separately
string : [AZ09]+
<b>Grammar</b>
S : E S'
;
S' : E S'

;
E : T E'
;
E' : or E

;
T : F T'
;
T' : num T''
 d T''
 optional T'

;
T'' : times T'

;
F : d F1
 l F2
 upto num F3
 upto d F3
 exactly num F4
 exactly d F4
 digit
 letter
 string
 num
 ( S )
;
F1 : to d

;
F2 : to l

;
F3 : digits
 letters
;
F4 : digits
 letters
;
</pre>
<p>Note that "" followed by nothing indicates the 'epsilon production'.</p>
<p>The grammar is indeed a <a href="http://en.wikipedia.org/wiki/LL_parser">LL(1) grammar</a>. This means that you can always figure out which of the above rules to apply after parsing some part of the string, just by looking at the next token.</p>
<h1>EXPLANATION</h1>
<p>After taking the input you may first want to clean the spaces in the expression</p>
<ul>
<li>Add spaces around paranthesis</li>
<li>Remove repeated spaces</li>
</ul>
<p>This ensures that all tokens are now separated by single space. Now you can tokenize the string and mark each token to the type of token provided.</p>
<p>The next step is to parse the list of tokens according to the rules of the grammar provided. It is important to note that given a LL(1) grammar, you can parse the array of tokens in linear time. The tester's solution below uses the <a href="http://en.wikipedia.org/wiki/Recursive_descent_parser">Recursive Descent Parsing</a> with the simplification that because the grammar is LL(1), you never have to back track.</p>
<p>The outcome of parsing the expression is creating a meaningful <a href="http://en.wikipedia.org/wiki/Regular_expression">regular expression</a>. As well as, calculating the largest possible ID that can be generated so as to discard the case if it exceeds the bound on the length of the IDs.</p>
<p>The GNU C library has <a href="http://pubs.opengroup.org/onlinepubs/7908799/xsh/regex.h.html"><regex.h></a> include that lets you use create a regex using the POSIX regular expressions syntax.</p>
<p>Once you have the regular expression compiled, you can execute it on all the IDs to check whether they match or they don't.</p>
<p>Refer to the Setter's Solution for a clean implementation of the <strong>Predictive parsing</strong> and learn how the various rules map to ideas in POSIX regular expressions. Each rule's corresponding method are named accordingly and the approach is easy to follow.</p>
<h1>SETTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2013/May/Setter/CPP.cpp">here</a>. (some permission issue on uploaded solution, fixing ASAP)</p>
<h1>TESTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2013/May/Tester/CPP.py">here</a>.</p>gamabuntaWed, 15 May 2013 21:41:05 +0530https://discuss.codechef.com/questions/10100/cppeditorialregexmay13hardeditorialstringparsinggrammarparsingQTREE  Editorialhttps://discuss.codechef.com/questions/10134/qtreeeditorial<h1>PROBLEM LINKS</h1>
<p><a href="http://www.codechef.com/problems/QTREE">Practice</a><br>
<a href="http://www.codechef.com/MAY13/problems/QTREE">Contest</a></p>
<h1>DIFFICULTY</h1>
<p>HARD</p>
<h1>PREREQUISITES</h1>
<p>Graph Theory, <a href="http://en.wikipedia.org/wiki/Segment_tree">Segment Trees</a>, <a href="http://wcipeg.com/wiki/Heavylight_decomposition">Heavy Light Decomposition</a></p>
<h1>PROBLEM</h1>
<p>You are given a connected graph on N vertices consisting of N edges.</p>
<ul>
<li>Each edge has a weight, not necessarily positive</li>
<li>The graph contains a single cycle</li>
<li>The cycle contains odd number of vertices (and edges).</li>
</ul>
<p>You wish to support two operations</p>
<ul>
<li>flip(u,v) flip the sign of the edge weights along the shortest path from u to v. Note that the shortest path is defined as the path of minimum hops, not the path with the least sum of edge weights.</li>
<li>find(u,v) consider the sequence of edge weights along the shortest path from u to v. In this sequence, find the maximum sum contiguous subsequence. Note that the shortest path is same as defined above. You have to print the sum of the maximum sum contiguous subsequence, not the sequence itself.</li>
</ul>
<h1>QUICK EXPLANATION</h1>
<p>Firstly it is obvious that a connected graph on N vertices with N edges will contain exactly one cycle.</p>
<p>It is not necessary for that cycle to be an oddlength cycle; but the problem statement assures you that such a cycle will always be odd length. This constraint ensures that there is always a unique shortest path between any two vertices in the graph.</p>
<p>Let us explore an easy to state solution for this graph.</p>
<p>For either of the flip or find operations, we will move along the unique path in the graph, edge by edge, and update / calculate the result. The update will of course change the sign of the edge weight. The result can of course be calculated using Kadane's algorithm.</p>
<p>How do we exactly trace the shortest path between any two vertices? We use the following insights</p>
<ul>
<li>The graph has a single cycle</li>
<li>Vertices of this cycle behave as roots of connected trees</li>
</ul>
<p>Now, for each of the trees, we can orient them. This effectively means that for each vertex in the tree, we can mark its unique parent, right up to the root, which lies in the cycle. We of course do not mark the root of the tree.</p>
<p>For each vertex we can mark which tree it belongs to (probably just store the label of the root vertex of the tree). This helps us figure out for some given vertices u and v, whether they are in the same tree or not.</p>
<p>Now, we can trace the path from u to v</p>
<ul>
<li>If they are in the same tree, we can find their LCA.<ul>
<li>This will require calculating the depth for each vertex</li>
</ul>
</li>
<li>If they are in separate trees<ul>
<li>The path of both the vertices to their roots, say s and t respectively are to be considered</li>
<li>Then the path from s to t, through the cycle, should be considered</li>
<li>The path from the cycle should be the smaller one. This can be determined trivially by arranging the vertices in an array in a clockwise (or counterclockwise) traversal of the vertices in the cycle.</li>
</ul>
</li>
</ul>
<p>The complextiy of each flip or find opeartion will be O(N). As you can figure, this is too low. Let us see how to make this O(log<sup>2</sup> N).</p>
<h1>EXPLANATION</h1>
<p>There are two ideas that have to be mixed together to make a flip / find operation take O(log N) time.</p>
<ul>
<li>Split the graph into paths, such that the path between any two given vertices contains O(log N) different paths from the decomposition</li>
<li>For each path, maintain a segment tree to answer queries of flip / find in O(log N) time</li>
</ul>
<p>Then, for each flip / find operation on the path from u to v we will</p>
<ul>
<li>start from u</li>
<li>iterate over the sequence of "paths" that contain edges from the path from u to v<ul>
<li>for each path, flip / find for the range of edges that belong to the path from u to v</li>
</ul>
</li>
</ul>
<p>We can consider the single cycle as a special case and build a segment tree for the cycle.</p>
<p>For all the trees, we will have to find their partitioning into paths, such that, any path from any vertex to the root visits O(log N) paths from the partitioning.</p>
<p>One way of such a decomposition is Heavy Light Decomposition. The idea is</p>
<ul>
<li>For each node, find a heavy child<ul>
<li>A heavy child is a child of the node that is the root of a tree with strictly more than half the number of vertices from among all the descendents of the node</li>
<li>mark the edge connecting to this child as heavy</li>
</ul>
</li>
<li>Each node will have at most 1 heavy child, and thus only one outgoing heavy edge</li>
<li>Heavy edges will merge into a disjoint set of paths. This is obvious because each vertex may have at most one incoming heavy edge and at most one outgoing heavy edge.</li>
<li>The rest of the edges, called light edges, can be considered individually, without the need to consider them as paths.</li>
</ul>
<p>Consider the impact of the existance of a light edge along the path from root to some vertex.</p>
<p>If you encounter a light edge in the path from root to some vertex, then after that edge, only half as many vertices remain in the subtree you are in. This means, that there can never be more than O(log N) light edges in any path from the root to any descendent!</p>
<p>The flip / find operation still require care to be taken about where the two vertices are  in the same tree or not. But in either case, you are always considering the path from some vertex u, to an ancestor t, and performing the flip / find. The procedure to do so looks like</p>
<ul>
<li>stat at vertex u</li>
<li>if you are at t, stop</li>
<li>if the edge connecting you to your parent is light edge<ul>
<li>flip the edge weight to perform the flip operation</li>
<li>consider the single edge as a segment to be merged with other segments</li>
</ul>
</li>
<li>if the edge connecting you to your parent is heavy edge<ul>
<li>if t belongs to the same heavy path, flip / find the segment from your position to t</li>
<li>otherwise flip / find the segment from your position to the highest vertex in the heavy path</li>
</ul>
</li>
</ul>
<p>The description above brings us to the most important aspect of the solution. In the find operation, we are expected to consider complete segments and merge information within the segments together to generate the answer for a merged segment.</p>
<p>More clearly, for each segment, storing only the maximum contiguous subsequence sum is not sufficient. We have to consdier the possibility of merging two segments for which we know the maximum contiguous subsequence sum.</p>
<ul>
<li>We of course take the larger of the two sums as candidate sum for the merged sequence.</li>
<li>It is also important to find the largest sum by some "suffix" of the first segment, and the largest sum by some "prefix" of the second segment. The sum of these two values is also a candidate to compete for the maximum contiguous subsequence sum in the merged segment.</li>
</ul>
<p>Thus, for each segment we should store not only the sum of the maximum contiguous sum subsequence, but also the sum of the maximum sum prefix, and suffix.</p>
<p>There are yet more details to fill to define the algorithm completely. Consider the path from u to v, where they belong to separate trees. The path from the root of the tree that has v, to the vertex v, should be considered in reverse order.</p>
<p>It is important for us then to be able to consider the reverse of a sequence. Fortunately, the information we have stored till now with each segment, is enough. We need only flip the maximum sum for prefix, and suffix to achieve the impact of considering a segment in reverse. Of course, considering a segment in reverse does not affect the maximum contiguous subsequence sum for the segment.</p>
<p>Now let us consider how flip is going to work.</p>
<p>For some segment tree, the flip operation will have to support the ability to invert the sign of all the elements in a complete segment (because that is the basic operation, an operation on the complete segment, for a segment tree). We can do this via storing</p>
<ul>
<li>the minimum contiguous subsequence sum</li>
<li>the minimum sum for some prefix</li>
<li>the minimum sum for some suffix</li>
</ul>
<p>for each segment. These values can also be just as easily merged as the values for their respective maximum versions. A flip for a complete segment will simply swap the maximums and minimums.</p>
<p>Lastly, we require to store the current flipped state for each segment (where each segment's initial state was 0). This is important because while doing a flip / find, we will only be updating / considering the largest segments in the tree that are completely in the range for the operation. That means, the child segments for a segment that is marked as flipped, is of course not touched during the operation.</p>
<p>So only when you are drilling down from a parent segment to a child segment, the parents flipped state is actually applied to the children. The parents state in this case is restored back to "unflipped". The key idea to understanding this is to consider this as lazy application of the flip operation. The flip actually happens only when some operation has to consider a strict subrange of the range covered by a segment.</p>
<p>Without these lazy updates, we would have to apply updates to O(N log N) segments in the segment tree, and the find operation would still take O(log N) anyway.</p>
<p>Thus, each flip / find in the segment tree can be done in O(log N) time. Mixing this with the fact that each flip / find operation on the graph considers O(log N) segment trees, the total complexity for a flip / find operation is O(log<sup>2</sup> N).</p>
<h1>RELATED PROBLEMS</h1>
<p><a href="http://discuss.codechef.com/questions/1588/dgcdeditorial">DGCD</a><br>
<a href="http://discuss.codechef.com/questions/6548/queryeditorial">QUERY</a></p>
<h1>SETTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2013/May/Setter/QTREE.cpp">here</a>.</p>
<h1>TESTER'S SOLUTION</h1>
<p>Tester's solution will be updated soon..</p>gamabuntaThu, 16 May 2013 03:24:04 +0530https://discuss.codechef.com/questions/10134/qtreeeditorialmay13hardsimplemathsegmenttreeheavylighteditorialNAME1  Editorialhttps://discuss.codechef.com/questions/9717/name1editorial<h1>PROBLEM LINKS</h1>
<p><a href="http://www.codechef.com/problems/NAME1">Practice</a><br>
<a href="http://www.codechef.com/MAY13/problems/NAME1">Contest</a></p>
<h1>DIFFICULTY</h1>
<p>CAKEWALK</p>
<h1>PREREQUISITES</h1>
<p>AdHoc</p>
<h1>PROBLEM</h1>
<p>You are given two strings <b>A</b> and <b>B</b>. You are also given <b>N</b> strings <b>C<sub>1</sub></b>, <b>C<sub>2</sub></b>, ... <b>C<sub>N</sub></b>.</p>
<p>Let <b>C = C<sub>1</sub> + C<sub>2</sub> + ... C<sub>N</sub></b>
where <b>+</b> is the <b>concatenation</b> <b>operator</b> (note that it is <b>not</b> <b>commutative</b>)</p>
<p>Find whether <b>C</b> may be a substring of one of the permutations of <b>A + B</b>.</p>
<h1>QUICK EXPLANATION</h1>
<p>The length of <b>A + B</b> can be <b>80000</b>. Of course, we cannot possibly generate all the permutations of <b>A + B</b>. Let us use some insight.</p>
<p>Lemma: If <b>C</b> is a substring of a permutation of <b>A + B</b>, then there is a permutation of <b>A + B</b> in which <b>C</b> is a prefix.</p>
<p>It is easy to see that if <b>C</b> exists as a substring, we can shift all the characters on the left of the first occurance of <b>C</b>, to the end of the string without affecting the presence of <b>C</b> in the permutation of <b>A + B</b>. Also, if <b>C</b> is a prefix of some permutation of <b>A + B</b>, then it is also a permutation which is proof enough to return a positive answer.</p>
<p>Lemma: If there is no permutation of <b>A + B</b> such that <b>C</b> is a prefix, then there is no permutation of <b>A + B</b> such that <b>C</b> is a substring.</p>
<p>This is easily proven by contradiction. If we assume that there is a permutation of <b>A + B</b> in which <b>C</b> is a substring, then by the previous Lemma we should have a permutation of <b>A + B</b> in which <b>C</b> is a prefix. Thus our assumption cannot be true.</p>
<p>From the above two, we can clearly say</p>
<p><b>C</b> can be a substring of some permutation of <b>A + B</b> iff there is a permutation of <b>A + B</b> of which <b>C</b> is a prefix.</p>
<h1>EXPLANATION</h1>
<p>Since we have the liberty to assume any permutation of <b>A + B</b>, we can treat it as a bag of characters and just try to build a permutation with <b>C</b> as prefix. If we are unable to, then of course we return negative. Otherwise, we can successfully have <b>C</b> as a substring by letting the other characters occupy any position on the left or right of the constructed string <b>C</b> (from characters in <b>A + B</b>).</p>
<p>We can build a count of all the characters in <b>A + B</b> as follows
</p><pre>counts[a ... z] = { 0 }<p></p>
<p>for each character c in A
counts[c]++
for each character c in B
counts[c]++
</p></pre><p></p>
<p>We can construct <b>C</b> by concatenating the given strings. The statement assures us that the length of <b>C</b> is not more than the length of <b>A + B</b>. Then we can one by one reduce the count of the characters in <b>C</b>. If any of the counts become negative, then we know that we cannot choose that character and that <b>C</b> cannot exist as a prefix (as well as substring) of any permutation of <b>A + B</b>.</p>
<pre>for each chatacter c in C
counts[c]
if counts[c] < 0
return false
return true
</pre>
<p>The complexity of the algorithm is <b>O(A + B + C)</b>.</p>
<h1>SETTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2013/May/Setter/NAME1.cpp">here</a>.</p>
<h1>TESTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2013/May/Tester/NAME1.cpp">here</a>.</p>gamabuntaTue, 14 May 2013 15:16:48 +0530https://discuss.codechef.com/questions/9717/name1editorialadhocmay13editorialcakewalkMSTICK  Editorialhttps://discuss.codechef.com/questions/9722/mstickeditorial<h1>PROBLEM LINKS</h1>
<p><a href="http://www.codechef.com/problems/MSTICK">Practice</a><br>
<a href="http://www.codechef.com/MAY13/problems/MSTICK">Contest</a></p>
<h1>DIFFICULTY</h1>
<p>SIMPLE</p>
<h1>PREREQUISITES</h1>
<p><a href="http://en.wikipedia.org/wiki/Range_Minimum_Query">Range Minimum Query</a>, Simple Math</p>
<h1>PROBLEM</h1>
<p>You are given <strong>N</strong> matchsticks arranged in a straight line, with their <strong>rear</strong> <strong>ends</strong> touching each other. You are also given the rate of burn for every matchstick (possibly same) in number of seconds it takes to burn it out. If a matchstick is lit from both ends, it burns out <strong>twice</strong> as fast  taking <strong>half</strong> as much time.</p>
<p>Answer several queries of the following type efficiently</p>
<p>All the matchsticks in the range <strong>L</strong> to <strong>R</strong>, inclusive are lit from their front ends simultaneously. Find how much time it takes for <strong>all</strong> the matchsticks to burn out.</p>
<h1>QUICK EXPLANATION</h1>
<p>For each query, the operation performed plays out in the following way</p>
<ul>
<li>All the matchsticks in the range <strong>L</strong> to <strong>R</strong> are lit from their front ends.</li>
<li>The matchstick that burns <strong>quickest</strong> in the range <strong>L</strong> to <strong>R</strong> burns out and <strong>ignites</strong> all the other matchsticks on their <strong>rear</strong> ends.</li>
<li>The matchticks in the range <strong>L</strong> to <strong>R</strong> now burn out <strong>twice</strong> as fast.</li>
<li><strong>All</strong> the other matchsticks burn out at their <strong>original</strong> rate.</li>
</ul>
<p>We can find the time taken in all the steps above using only the following pieces of information for the segment <strong>L</strong> to <strong>R</strong></p>
<ul>
<li>Quickest rate of burning for a match in the range <strong>L</strong> to <strong>R</strong>.</li>
<li>Slowest rate of burning for all matches in the range <strong>L</strong> to <strong>R</strong>.</li>
<li>Slowest rate of burning for all matches outside the range <strong>L</strong> to <strong>R</strong>.</li>
</ul>
<h1>EXPLANATION</h1>
<p>For a given range <strong>L</strong> to <strong>R</strong></p>
<ul>
<li>Let <strong>m</strong> denote the minimum time taken by some matchstick in the range <strong>L</strong> to <strong>R</strong> to burn out</li>
<li>Let <strong>M</strong> denote the largest time taken by some matchstick in the range <strong>L</strong> to <strong>R</strong> to burn out</li>
<li>Let <strong>M</strong>' denote the largest time taken by some matchstick outside the range <strong>L</strong> to <strong>R</strong> to burn out</li>
</ul>
<p>The time taken by each of the steps in the scenario described above is as follows</p>
<ul>
<li>The matchstick that burns quickest, burns out<ul>
<li>Takes time <strong>m</strong></li>
</ul>
</li>
<li>The following things happen in parallel<ul>
<li>The matchsticks in the range <strong>L</strong> to <strong>R</strong> now burn out twice as fast<ul>
<li>Takes time <strong>(M  m) / 2</strong></li>
</ul>
</li>
<li>The matchsticks outside the range <ul>
<li>Takes time <strong>M'</strong></li>
</ul>
</li>
</ul>
</li>
</ul>
<p>Thus, the time taken for all the matches to burn out completely is</p>
<pre>m + max( (Mm)/2 , M' )
</pre>
<p>It remains to find efficiently the <strong>minimum</strong> time some matchstick will take in a range, and the <strong>maximum</strong> time some matchstick will take in a <strong>range</strong>.</p>
<p>Such queries can be answered in <strong>O(N log N)</strong> time by using <a href="http://en.wikipedia.org/wiki/Segment_tree">segment trees</a>. Refer to <a href="http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=lowestCommonAncestor">this</a> topcoder tutorial for a wonderful writeup with code samples on how to get about writing a segment tree. The topcoder tutorial also describes a <strong>O(N sqrt(N))</strong> approach as well which will also work within the time limits for this problem.</p>
<p><strong>Two segment trees must be constructed</strong>. One to answer queries of the type "<strong>minimum in a range</strong>", that returns the time it takes for the fastest burning matchstick to burn out. Another to answer queries of the type "<strong>maximum in a range</strong>" to find <strong>M</strong> and <strong>M</strong>' as defined above. Note that <strong>M</strong>' will itself be the maxmimum of two ranges, <b>1 to L1</b> and <b>R+1 to N</b> respectively.</p>
<p>A lot of solutions were stuck in the caveat that it is required to <strong>always</strong> print the answer in a <strong>single</strong> decimal place. Note how the answer will either be <strong>integer</strong>, or contain a single decimal digit (<strong>5</strong>). In case the answer is <strong>integer</strong>, it is required to print a trailing decimal followed by <strong>0</strong>.</p>
<h1>SETTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2013/May/Setter/MSTICK.cpp">here</a>.</p>
<h1>TESTER'S SOLUTION</h1>
<p>Approach  finds range min query in time O(rootN)  <a href="http://www.codechef.com/download/Solutions/2013/May/Tester/MSTICKrootN.cpp">solution</a>.</p>
<p>Approach  finds range min query using segment trees in O(logN)  <a href="http://www.codechef.com/download/Solutions/2013/May/Tester/MSTICKlogN.cpp">solution</a>.</p>gamabuntaTue, 14 May 2013 15:19:12 +0530https://discuss.codechef.com/questions/9722/mstickeditorialsimplesegmenttreeeditorialmay13simplemathFTRIP  Editorialhttps://discuss.codechef.com/questions/9724/ftripeditorial<h1>PROBLEM LINKS</h1>
<p><a href="http://www.codechef.com/problems/FTRIP">Practice</a><br>
<a href="http://www.codechef.com/MAY13/problems/FTRIP">Contest</a></p>
<h1>DIFFICULTY</h1>
<p>SIMPLE</p>
<h1>PREREQUISITES</h1>
<p>Simple Math</p>
<h1>PROBLEM</h1>
<p>In your class of <b>S</b> students, <b>N</b> students are being selected to go on a trip. Your friend circle has <b>M</b> students in the class, including you. You will only enjoy the trip if you have at least <b>K</b> other friends with you.</p>
<p>What is the probability that you will enjoy the trip <b>if</b> you are selected?</p>
<h1>QUICK EXPLANATION</h1>
<p>Firstly, by <a href="http://en.wikipedia.org/wiki/Bayes'_theorem"><b>Bayes</b>' <b>Theorem</b></a> we know that we must find</p>
<ul>
<li><b>P</b> = number of ways that <b>N</b> students are selected from <b>S</b> students, such that <b>you</b> are selected and at least <b>K</b> of your friends are selected (from your <b>M1</b> other friends)</li>
<li><b>Q</b> = number of ways that <b>N</b> students are selected from <b>S</b> students, such that <b>you</b> are selected</li>
</ul>
<p>The result will be <b>P/Q</b>.</p>
<h1>EXPLANATION</h1>
<p>Q = <sup>(S1)</sup><b>C</b><sub>(N1)</sub></p>
<p>Since you are already chosen, we need to select <b>N1</b> more students out of the <b>S1</b> students left.</p>
<p>To find <b>P</b>, we can iterate over the number of friends chosen.</p>
<pre>P = 0
for f = K to min(M1,N1)
P += <sup>(M1)</sup><b>C</b><sub>f</sub> * <sup>(SM)</sup><b>C</b><sub>(Nf1)</sub>
</pre>
<p>We iterate from <b>K</b> to <b>min(M1,N1)</b>, since the cap on the number of friends who can come with you on the trip is defined by either the remaining number of slots, or the number of friends you have.</p>
<p>The term that we add for counting the number of ways of choosing <b>f</b> friends should be straight forward. The two terms in the product are</p>
<ul>
<li>number of ways of choosing <b>f</b> friends from a corpus of <b>M1</b> friends, and</li>
<li>number of ways of choosing the students for the remaining slots from a corpus of students who are not your friends</li>
</ul>
<p>We can precalculate the values of <sup>n</sup><b>C</b><sub>r</sub> for all <b>n</b> and <b>r</b> because the limits are small. None of the calculations will overflow.</p>
<p>The overall complexity of the algorithm is dominated by the precalculation of the combinations. Otherwise, the complexity of processing each case is <b>linear</b>.</p>
<h1>SETTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2013/May/Setter/FTRIP.cpp">here</a>.</p>
<h1>TESTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2013/May/Tester/FTRIP.cpp">here</a>.</p>gamabuntaTue, 14 May 2013 15:26:42 +0530https://discuss.codechef.com/questions/9724/ftripeditorialsimplesimplemathprobabilitymay13editorialNAME2  Editorialhttps://discuss.codechef.com/questions/9712/name2editorial<h1>PROBLEM LINKS</h1>
<p><a href="http://www.codechef.com/problems/NAME2">Practice</a><br>
<a href="http://www.codechef.com/MAY13/problems/NAME2">Contest</a></p>
<h1>DIFFICULTY</h1>
<p>CAKEWALK</p>
<h1>PREREQUISITES</h1>
<p>AdHoc</p>
<h1>PROBLEM</h1>
<p>Given two strings, say <b>A</b> and <b>B</b>, find whether <b>A</b> is a subsequence of <b>B</b>, or whether <b>B</b> is a subsequence of <b>A</b>.</p>
<p>A subsequence is defined as a string obtained from another string, say <b>S</b>, by <b>deleting</b> <b>one</b> <b>or</b> <b>more</b> characters form <b>S</b>, and not changing the <b>order</b> of the remaining characters.</p>
<h1>QUICK EXPLANATION</h1>
<p>If the length of <b>A</b> is more than the length of <b>B</b>, then <b>A</b> cannot be a subsequence of <b>B</b>. This is obvious because you cannot delete characters from B and end up with a string that has <b>more</b> characters than it did orginally.</p>
<p>Thus, if length of <b>A</b> is larger than length of <b>B</b> we can swap them. Now, it only needs to be checked whether <b>A</b> is a subsequence of <b>B</b>.</p>
<h1>EXPLANATION</h1>
<p>Checking whether <b>A</b> is a subsequence of <b>B</b> can be done greedily.</p>
<p>Let us find the <b>first</b> occurence of the first character of <b>A</b> in <b>B</b>.</p>
<pre>for i = 1 to B.length
if B[i] == A[1]
break
i++
</pre>
<p>If we find that <b>i</b> is larger than <b>B.length</b>, then of course the very first character of <b>A</b> doesn't exist in <b>B</b>. This would mean that it is impossible for <b>A</b> to be a subsequence of <b>B</b>.</p>
<p>On the other hand, we have found that the the first character of <b>A</b> occurs in <b>B</b> at position <b>i</b>, first. Now, we can start looking for the <b>second</b> character of <b>A</b>. But, any occurance of the second character of <b>A</b> that occurs before <b>i</b> in <b>B</b> is irrelevant because we cannot perform any operation that <b>changes</b> <b>the</b> <b>order</b> of characters in <b>A</b> (or <b>B</b> for that matter).</p>
<p>Thus, we can resume searching for the second character of <b>A</b> in <b>B</b>, after position <b>i</b>.</p>
<pre>for j = i+1 to B.length
if B[j] == A[2]
break
j++
</pre>
<p>Using the same arguments as above, if <b>j</b> is not more than <b>B.length</b>, we have to resume searching for the third character of <b>A</b> in <b>B</b>, after position <b>j</b>.</p>
<p>When we have found all the characters of <b>A</b> in <b>B</b>, we can safely end the algorithm as well (with a <b>positive</b>). Otherwise we will run out of characters in <b>B</b> and we must return with a <b>negative</b>.</p>
<p>The above algorithm will look like the following pseudo code.</p>
<pre>j = 1
for i = 1 to A.length
while j < B.length
if B[j] == A[i]
break
j++
if j > B.length
return false
i++
j++
return true
</pre>
<p>The complexity of the algorithm is <b>O(A + B)</b>, where <b>S</b> is the length of <b>S</b>. If it is not obvious to you why the algorithm isn't <b>O(A * B)</b> note that we never decrement the value of <b>j</b>. In every iteration of the above algorithm we always increment <b>i</b> as well as <b>j</b>, and probably increment <b>j</b> more so. Thus, the algorithm must terminate in at most <b>O(A)</b> iterations of the outer loop and not more than <b>O(B)</b> iterations of the inner loop.</p>
<p>Note how this problem differs from the standard Dynamic Programming problem of finding the <b>largest common subsequence</b> between two strings. We could of course solve this problem by finding the longest commong subsequence between <b>A</b> and <b>B</b> as well, but doing so requires <b>O(A * B)</b> which is too slow for the limits set for length of the strings <b>A</b> and <b>B</b>.</p>
<h1>SETTER'S SOLUTION</h1>
<p>Setter's solution will be updated soon.</p>
<h1>TESTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2013/May/Tester/NAME2.cpp">here</a>.</p>gamabuntaTue, 14 May 2013 15:14:36 +0530https://discuss.codechef.com/questions/9712/name2editorialadhocmay13editorialcakewalkWITMATH  Editorialhttps://discuss.codechef.com/questions/9723/witmatheditorial<h1>PROBLEM LINKS</h1>
<p><a href="http://www.codechef.com/problems/WITMATH">Practice</a><br>
<a href="http://www.codechef.com/MAY13/problems/WITMATH">Contest</a></p>
<h1>DIFFICULTY</h1>
<p>SIMPLE</p>
<h1>PREREQUISITES</h1>
<p>Primality Testing</p>
<h1>PROBLEM</h1>
<p>Given some <b>N</b>, find the <b>i</b> for which <b>φ(i)/i</b> is the largest among all <b>2≤i≤N</b>.</p>
<p><b>φ(i)</b> is the <b>Euler Totient Function</b>.</p>
<h1>QUICK EXPLANATION</h1>
<p><b>φ(i)</b> is equal to the number of positive integers less than <b>i</b>, which are <b>coprime</b> to <b>i</b>. The largest value of <b>φ(i)/i</b> is always achieved at prime values of <b>i</b> (primes of course are <b>coprime</b> to all values less than them). Note that for a prime <b>i</b>, <b>φ(i) = i1</b>.</p>
<p>Thus, for some <b>N</b>, we need to find the largest prime number we can find, which is less than <b>N</b>.</p>
<p><b>N</b> can be up to <b>10<sup>18</sup></b>. If we test primality via <b>Trial Division</b>, the minimum number of divisions we do for testing the primality of a single number is about <b>10<sup>9</sup></b>. Considering we have to consider several numbers and try to pluck the prime one (and do so for several cases) we are forced to find a faster way to test primality.</p>
<p><a href="http://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test">Miller Rabin</a> is such a test.</p>
<h1>EXPLANATION</h1>
<p>Although a <b>probabilistic</b> test, <b>Miller</b> <b>Rabin</b> has been successfully executed up till large enough numbers to show that performing the test while taking the first <b>9</b> prime numbers <b>{ 2, 3, 5, 7, 11, 13, 17, 19, 23 }</b> as the bases is sufficient to accurately test for primality of all numbers less than <b>10<sup>18</sup></b>.</p>
<p>If you end up falling in love with <b>Miller</b> <b>Rabin</b> (the algorithm of course), you will find <a href="http://oeis.org/A014233">this</a> link very useful to decide how many of the first few prime numbers to use as bases. It is not necessary to use small primes of course. Random bases can be chosen as well. But you might have to choose more than <b>9</b> of them to reduce the probability of a falty answer to a comfortably low level (testing with k random bases reduces the probability of a composite being reported as prime by a factor of 1/4<sup>k</sup>)</p>
<p>There are possibly two hurdles that you may face in implementing Miller Rabin.</p>
<p><b>1. Finding a<sup>r</sup> mod n, for a large r</b></p>
<p>This step must be performed using <b>repeated squaring</b>.</p>
<p><b>2. Multiplying two large integers mod n</b></p>
<p>The product of the two large integers would overflow the <b>64bit</b> integer data type as well. The only way to get around this is to use some arbitrary precision math.</p>
<p>We can assume that the two integers, say <b>a</b> and <b>b</b>, are less than <b>n</b>. One way to perform the multiplication is as follows</p>
<pre> 1. a_low = a % 10<sup>9</sup>
2. a_high = a / 10<sup>9</sup>
3.
4. b_low = b % 10<sup>9</sup>
5. b_high = b / 10<sup>9</sup>
6.
7. result = (a_high * b_high) % n
8.
9. repeat 9 times
10. result = (result * 10) % n
11.
12. result = (result + a_low*b_high + b_low*a_high) % n
13.
14. repeat 9 times
15. result = (result * 10) % n
16.
17. result = (result + a_low*b_low) % n
</pre>
<p>The reason the above procedure would work is</p>
<ul>
<li>The product in line 7, 12 and 17 are betwee two 30bit integers and will not overflow 64bit integers.</li>
<li>The product in line 10 and 15 are between a 60bit integer and 4bit integer and will not overflow 64bit integers. (although we must use unsigned)</li>
</ul>
<h1>SETTER'S SOLUTION</h1>
<p>Setter's solution will be updated soon.</p>
<h1>TESTER'S SOLUTION</h1>
<p>Can be found <a href="http://www.codechef.com/download/Solutions/2013/May/Tester/WITMATH.java">here</a>.</p>gamabuntaTue, 14 May 2013 15:21:48 +0530https://discuss.codechef.com/questions/9723/witmatheditorialsimpleprimenumbersmay13millerrabineditorial