Questions Tagged With ltime20https://discuss.codechef.com/tags/ltime20/?type=rssquestions tagged <span class="tag">ltime20</span>enSun, 25 Jan 2015 14:42:50 +0530LCH15JAB - Editorialhttps://discuss.codechef.com/questions/62664/lch15jab-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/LCH15JAB">Practice</a>
<a href="http://www.codechef.com/LTIME20/problems/LCH15JAB">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/pavel1996">Pavel Sheftelevich</a> <br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/rubanenko">Roman Rubanenko</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/pkacprzak">Paweł Kacprzak</a> </p>
<h1>DIFFICULTY:</h1>
<p>CAKEWALK</p>
<h1>PREREQUISITES:</h1>
<p>Ad-hoc</p>
<h1>PROBLEM:</h1>
<p>As the name suggest, this problem is really easy. You are given a string S. The task is to decide whether there exists a character for which a number of occurrences of this character in S is equal to a sum of occurrences of all other characters in S.</p>
<h1>QUICK EXPLANATION:</h1>
<p>Count a number of occurrences for each of 26 possible letters and for each such letter, check if the counter equals a sum of occurrences of all other characters in S.</p>
<h1>EXPLANATION:</h1>
<p><strong>First observation:</strong> <br>
There are at most 26 possible distinct letters in S because the Latin alphabet has 26 letters ('a' to 'z').</p>
<p>Let cnt[a] denote number of occurrences of letter ch in S. We can compute the cnt table iterating over S from left to right and maintaining and updating a counter for each character.</p>
<pre>int cnt[26];
for (i = 0; i < 26; i++)
cnt[i] = 0;
for (i = 0; i < s.size(); i++)
cnt[s[i] - 'a']++;
</pre>
<p>Let n be the length of S. A simple observation which may help is that a sum of occurrences of all characters different than ch equals n - cnt[ch].</p>
<p>Based on this fact we can decide out problem easily. Just iterate over all possible letters and check if there is a letter ch for which cnt[ch] = n - cnt[ch]</p>
<p>Also note that if you are an C++/Java user, you can also make use of map/Map in STL(Standard Template Library)/ Java Collections. map/Map is a balanced red black tree, in which you can put (key, value) pairs and also search for value corresponding to the key. All these operations are logarithmic in number of elements present in the data structure. So you can use map/Map to count number of occurrences of a particular character too. For more faster solution, you can use unordered_map/HashMap too which is implemented using hashing and gives constant time for the above operations.</p>
<h1>TIME COMPLEXITY</h1>
<p>For a solution which uses counters is O(n) and the same for a solution using map/Map or unordered_map/HashMap, because if you use it, you will store up to 26 entries in it, so this is not much an upgrade. I suggest to use a simple table because for such small dataset it is the fastest method.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME20/Setter/LCH15JAB.cpp">here</a>.
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME20/Tester/LCH15JAB.java">here</a>. </p>
<h1>RELATED PROBLEMS:</h1>pkacprzakSun, 25 Jan 2015 14:37:41 +0530https://discuss.codechef.com/questions/62664/lch15jab-editorialad-hocltime20editorialcakewalkLCH15JGH - Editorialhttps://discuss.codechef.com/questions/62667/lch15jgh-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/LCH15JGH">Practice</a>
<a href="http://www.codechef.com/LTIME20/problems/LCH15JGH">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/pavel1996">Pavel Sheftelevich</a> <br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/rubanenko">Roman Rubanenko</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/pkacprzak">Paweł Kacprzak</a> </p>
<h1>DIFFICULTY:</h1>
<p>Medium Hard</p>
<h1>PREREQUISITES:</h1>
<p>Math, [Fenwick tree][11111], Segment tree, Ad-hoc</p>
<h1>PROBLEM:</h1>
<p>There are initially N families of people of a different given size. You have to be able to handle 3 types of queries on the set of these families:</p>
<ol>
<li>Add one family of size X to the set</li>
<li>Remove one family of size X from the set</li>
<li>You will give Y bananas to every family in the set in such a way that for any particular family, all member of it will receive the same number of bananas and this number will be maximum possible i.e if a family has M members then every member will receive Y / M bananas and there will be Y % M bananas left. Your tast is to count the number of all bananas left in this process.</li>
</ol>
<h1>QUICK EXPLANATION:</h1>
<p>Use the fact that x % y = x - (x / y) * y, where x / y is an integer division, so in order to calculate the number of bananas left you can avoid calculating modulo. To handle queries of the first and the second type you can use a [Fenwick tree][11111] or a Segment tree, which can answer two queries: how many total people are currently in families for which Y / M is equal and how many families are there for which Y / M is equal, where M denotes the number of people in one such family. If you are able to answer this question, in order to answer a query of the third type, you can iterate over all possible values of Y / M and accumulate the results.</p>
<h1>EXPLANATION:</h1>
<p>There are multiple very good approaches for this problem and almost all of them depends on the facts given above. I will sketch 3 of them:</p>
<h1>SOLUTIONS BASED ON SEGMENT-TYPE-LIKE DATA STRUCTURE</h1>
<p>As mentioned in quick explanation, you can use a data structure which can handle queries about segments, where a segment [L, R] corrensponds to all families with sizes in a range [L, R]. If you are able to keep track of these ranges, you can easily handle queries of first two types. In order to handle the third query, notice that there are many families of different sizes for which Y / M is equal, where M denotes a size of a family. Based on this fact, and the fact that Y % M = Y - (Y / M) * M, you can avoid calculating modulo on every such family and you can calculate a result for all such familis at once by querying the data structure about the number of people in families in a range [L, R] in which Y / M is equal for every family and querying it also about the number of families in the same range. Based on this two subresults, you can compute the number of bananas left in the process for each of family in [L, R]. If you sum these results over all possible values of Y / M you will get the result for the third query.</p>
<p>The complexity of these solutions are about O(log N * M * sqrt(max(Y)))</p>
<h1>SOLUTIONS BASED ON BLOCKS</h1>
<p>Rather than using a segment-based data structure, you can divide the range of possible family sizes in contant size blocks. You can use similar facts as in the above solution to get the results, but rather than querying for a particular range [L, R] you will divide it into two calculations of result for a range [1, L - 1] and [1, R] and you will subtract first from the second. In order to calculate the result for a given range [1, R] you will sum results for all full blocks which fit into the range and possibly one chunk at the end of the range for which you can calculate the result iterating over all its elements.</p>
<p>Let B be the number of used blocks and S be the size of one such block.</p>
<p>The complexity of these type solutions are about O(M * sqrt(max(Y)) + N * (B + S)) which can be an upgrade over the segment-tree-like data structure.</p>
<h1>AD HOC SOLUTIONS</h1>
<p>You can also keep it really simple and get away with using advanced data structures or blocks. A quick overview is that you can compute the results for families given initially in some way, then handle a portion of up to Q queries (Q is choosen arbitrary to fit the time limits, we saw contestants using Q = 200) by using previously computed results and bruteforcing over previous updates in current portion of queries. After you handle Q queries, you can rebuilt your current results and start with another Q queries.</p>
<p>The complexity of these type solutions depends on the implementation, but if done right with appropriate constants, they can be really fast for this problem.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME20/Setter/LCH15JGH.cpp">here</a>.
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME20/Tester/LCH15JGH.java">here</a>. </p>
<h1>RELATED PROBLEMS:</h1>pkacprzakSun, 25 Jan 2015 14:42:50 +0530https://discuss.codechef.com/questions/62667/lch15jgh-editorialeditorialad-hocfenwicksegment-treeltime20medium-hardmathsLCH15JEF - Editorialhttps://discuss.codechef.com/questions/62658/lch15jef-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/LCH15JEF">Practice</a> <br>
<a href="http://www.codechef.com/LTIME20/problems/LCH15JEF">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/pavel1996">Pavel Sheftelevich</a> <br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/rubanenko">Roman Rubanenko</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/pkacprzak">Paweł Kacprzak</a> </p>
<h1>DIFFICULTY:</h1>
<p>Easy</p>
<h1>PREREQUISITES:</h1>
<p>Math, Big-num</p>
<h1>PROBLEM:</h1>
<p>For each test case you are given a number m and an expression which contains only numbers multiplications and exponentiations. Your task is to find the value of the expression modulo m</p>
<h1>QUICK EXPLANATION:</h1>
<p>Parse the expression and calculate it using big num representation and fast exponentiation.</p>
<h1>EXPLANATION:</h1>
<h1>EXPECTED SOLUTION:</h1>
<p>If we are able to handle 3 operations: multiplication, exponentiation and modulo calculation, we can solve the problem easily after parsing the input first. Since input numbers can be very large, this is not straightforward and I'll show how to implement these 3 operations step by step:</p>
<ol>
<li>
<p><strong>Calculating modulo</strong>. Let assume that we have to calculate A % M. In this problem M is always < 10^8 so we can store it as 64-bit integer. Let d<sub>k-1</sub>, d<sub>k-2</sub>, ..., d<sub>0</sub> be the digits of A from left to right. Then A = 10^(k-1) * d<sub>k-1</sub> + 10^(k-2) * d<sub>k-2</sub> + ... + d<sub>0</sub> and based on this fact, we can write A % M as (10^(k-1) * d<sub>k-1</sub>) % M + (10^(k-2) * d<sub>k-2</sub>) % M + ... + d<sub>0 % M which can be easily computed using <a href="http://en.wikipedia.org/wiki/Horner%27s_method">Horner's method</a> - please check the author's solution for details.</sub></p>
</li>
<li>
<p><strong>Exponentiation</strong>. Let assume that we have to calculate A^B, where A and B can be arbitrary long numbers. First we can calculate reduce A to A^M because (A^B) % M = ((A%M)^B) % M. So now we are raising a number A < 10^8 to an arbitrary long exponent. Let B = 10^(k-1) * d<sub>k-1</sub> + 10^(k-2) * d<sub>k-2</sub> + ... + d<sub>0</sub> where d<sub>i</sub> is the i-th rightmost digit of B. Then A^B = A^(10^(k-1) * d<sub>k-1</sub> + 10^(k-2) * d<sub>k-2</sub> + ... + d<sub>0</sub>) which can be written as A^(10^(k-1) * d<sub>k-1</sub>) * A^(10^(k-2) * d<sub>k-2</sub>) * ... * A^d<sub>0</sub> and you can again use the <a href="http://en.wikipedia.org/wiki/Horner%27s_method">Horner's method</a> to compute it - please check the author's solution for details.</p>
</li>
<li>
<p><strong>Multiplication of two numbers A, B < 10^18 modulo MOD < 10^18</strong>. The result of this operation may not fit into 64-bit integer, so we have to be smart here. You can use the same idea as in the fast exponentiation algorithm here, please check this function from author's code:</p>
</li>
</ol>
<pre>long long MOD;
long long mult(long long A, long long B)
{
if ( B == 0 ) return 0;
long long u = mult(A, B/2);
long long res;
if ( B%2 == 0 )
res = u + u;
else
res = u + u + A;
while ( res >= MOD ) res -= MOD;
return res;
}
</pre>
<h1>SOLUTION USING BIG NUMS:</h1>
<p>Since numbers in the statement can be very large and m can be big also, this problem is very easier to code in a language which has implemented a big number representation. For example Java or Python is a really good choice here. If you are planing to write the solution in a language which doesn't support big numbers, you have to implement it on your own along with operation of multiplication, fast exponentiation (which is done by multiplication) and modulo calculation. The bottom line is that you have a strong advantage here if you are using a language which supports big numbers or you have an implementation of it prepared before the contest.</p>
<p>I will focus now on the implementation, because if you do it fast and smart, you can benefit huge from it.</p>
<p>First things first, we have to parse the input statement, because it is given as a string of numbers and operands. If you are familiar with regular expressions, you are in a <a href="http://en.wikipedia.org/wiki/Pole_position">pole position</a> here. Let change two start representing exponentiation to ^ symbol duo to formatting issues in this editor only for editorial purposes. If we divide the statement x<sub>1</sub>^y<sub>1</sub> * x<sub>2</sub>^y <sub>2</sub> * ... * x<sub>n</sub>^y<sub>n</sub> into pairs of numbers (x<sub>1</sub>, y<sub>1</sub>), (x<sub>2</sub>, y<sub>2</sub>), ..., (x<sub>n</sub>, y<sub>n</sub>) we can first compute the result of exponentiation for each pair and then multiply these intermediate results. So let's split the input statement just into consecutive numbers! Then we can get two such numbers, do the exponentiation on them and multiply the current result by the result of this exponentiation - remember that all operations have to be calculated modulo m.</p>
<p>If you are using python or another language with regular expressions built in, you can split the input statement s in consecutive numbers using the below regular expression:</p>
<pre>re.split(r'[^0-9]+', s)
</pre>
<p>where s is the input string and re is the standard regular expression module</p>
<p>In python there is a built in fast exponentiation functions which can also calculate the result modulo given number. To compute (a^b) % c just run mod(a, b, c). I encourage you to use it, because it is really fast and very well implemented.</p>
<p>If you want to know how to do fast exponentiation on your own, please check this <a href="http://en.wikipedia.org/wiki/Exponentiation_by_squaring">link</a>. One important note is that for big exponents, a resursive exponentiation of it will give you Runtime Error duo to stack overflow. You should implement it iteratively.</p>
<p>Since my python solution in quite short, you can see the full code below:</p>
<pre>import re
t = int(raw_input())
for i in xrange(t):
m, s = raw_input().strip().split()
m = long(m)
s = s.strip()
a = re.split(r'[^0-9]+', s)
res = 1
for i in xrange(0, len(a), 2):
res = (res * pow(long(a[i]), long(a[i + 1]), m)) % m
print res
</pre>
<h1>ALTERNATIVE SOLUTIONS:</h1>
<p>For the first subtask, you don't have to use big numbers at all since numbers in the expression are digits and m is small enough. For the second subtask, every result of an exponentiation can be keeped small when calculated modulo m, because m < 10^9 and this allows you to do multiplication in the statement in 64-bit integers because a * b, for a, b < 10^9 fits 64-bit integer.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME20/Setter/LCH15JEF.cpp">here</a>.<br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME20/Tester/LCH15JEF.java">here</a>. </p>
<h1>RELATED PROBLEMS:</h1>pkacprzakSun, 25 Jan 2015 14:32:21 +0530https://discuss.codechef.com/questions/62658/lch15jef-editorialbignumeasyimplementationltime20editorialmathsLCH15CD - Editorialhttps://discuss.codechef.com/questions/62645/lch15cd-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/LCH15CD">Practice</a> <br>
<a href="http://www.codechef.com/LTIME20/problems/LCH15CD">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/pavel1996">Pavel Sheftelevich</a> <br>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/rubanenko">Roman Rubanenko</a> <br>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/pkacprzak">Paweł Kacprzak</a> </p>
<h1>DIFFICULTY:</h1>
<p>Easy Medium </p>
<h1>PREREQUISITES:</h1>
<p>DP, Implementation</p>
<h1>PROBLEM:</h1>
<p>You are given a n-dimensional cube of size d in which you have to find the cheapest way to get from (0, 0, ..., 0) to (d-1, d-1, ..., d-1) in such a way that that you can move from point a to b if b differs from a in exactly one coordinate by 1 and the sum of coordinates of a is less than the sum of coordinates of b while the cost of visiting a point a = (a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n-1</sub>) equals (a<sub>0</sub> ^ a<sub>1</sub> ^ ... ^ a<sub>n-1</sub>) * (a<sub>0</sub> + a<sub>1</sub> + ... + a<sub>n-1</sub>) where ^ denotes the XOR operation.</p>
<h1>QUICK EXPLANATION:</h1>
<p>This is a multidimensional version of a very classic dynamic programming problem. Let b be a point in the cube and let PREV be a set of points from b can be reached. The cheapest way to reach b is the cheapest way to reach a point from PREV plus the cost of visiting b and the cost of reaching (0, 0, 0, ..., 0) equals 0 by the definition.</p>
<h1>EXPLANATION:</h1>
<p>If you read the quick explanation you know that the only difficulty here is the implementation, but first let me go through the idea in details again.</p>
<p>Let divide out the cube in layers, layer[i] consists of all points for which the sum of its coordinates equals i. Clearly there are exactly n * d layers, because there are n coordinates and for each one there are d possible values. From the statement we know that in one move we can go from any point in layer[i] to any point in layer[i + 1]. The goal is start in the first layer which contains only the point (0, 0, 0, ..., 0) and to reach the one and only point in the last layer in the cheapest way. If you are familiar with dynamic programming you know already how to solve it: iterate over layers starting in the lowest one and while we are in layer[i] we iterate over all points in it and update the cheapest way of reaching all reachable points in layer[i + 1] from the current point.</p>
<p>I really encourage you to implement a solution, because if you haven't done it yet, you can learn a few useful techniques in this type of problems.</p>
<p>Here are a few tips (for exact implementation please check solutions section down below, there is a tester solution in java and mine in c++):</p>
<ul>
<li>
<p>represent points as numbers in base d. This allows you to iterate easily over them and to extract coordinates from representation very straightforward.</p>
</li>
<li>
<p>define a simple mapping from a point a = (a<sub>0</sub>, a<sub>1</sub>, ..., a<sub>n-1</sub>) to a point which has exactly one, let's say i-th coordinate, bigger by 1 than a. You can check for this mapping in tester's solution, where he compute a deg[] array which helps to move between these points using only one addition</p>
</li>
<li>
<p>in this problem, it's easier to update a result in layer[i + 1] while being in layer[i] which is an opposite technique to a standard dynamic programming approach where you would update a result for layer[i + 1] while being in it and iterating over all points in layer[i]</p>
</li>
<li>
<p>remember to define the initial results for each point in a cube first. It should be the INFINITY value for all points but (0, 0, 0, ..., 0) which has a cost of reaching it 0</p>
</li>
</ul>
<p>Time complexity here is O(d^n * n) because there are d^n cells in a cube and we perform O(n) atomic operations for each of them.</p>
<h1>ALTERNATIVE SOLUTION:</h1>
<p>Subtasks can be solved using the similar dynamic programming approach but they are easier to implement if N = 1 or N = 2. For example, if N = 1 you are basically moving along a line and each layer contains exactly one point.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME20/Setter/LCH15CD.cpp">here</a>.<br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME20/Tester/LCH15CD.java">here</a>. </p>
<h1>RELATED PROBLEMS:</h1>pkacprzakSun, 25 Jan 2015 14:19:44 +0530https://discuss.codechef.com/questions/62645/lch15cd-editorialimplementationdynamic-programmingltime20easy-mediumeditorial