Questions asked by deadwing97https://discuss.codechef.com/questions/asked-by/220103/deadwing97/?type=rssQuestions asked by <a href="/users/220103/deadwing97" >deadwing97</a>enThu, 30 Aug 2018 01:44:00 +0530ADACRA - Editorialhttps://discuss.codechef.com/questions/102422/adacra-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/ADACRA">Practice</a> <br>
<a href="https://www.codechef.com/COOK83/problems/ADACRA">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/alei">Alei Reyes</a> <br>
<strong>Primary Tester:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a> <br>
<strong>Secondary Tester:</strong> <a href="https://www.codechef.com/users/miyukine">Kacper Walentynowicz</a><br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>DIFFICULTY:</h1>
<p>Cakewalk</p>
<h1>PREREQUISITES:</h1>
<p>None</p>
<h1>PROBLEM:</h1>
<p>Given a string consisting of characters U,D. In a move you can select a consecutive substring and flip all characters belonging to. (U changes to D and vice versa). What's the minimum number of moves to make all characters equal?</p>
<h1>EXPLANATION:</h1>
<p>The first thing that will come up to our minds is that we should split the string from the beginning into a block of consecutive 'U' characters, followed immediately by a block of consecutive 'D' characters, then a block of 'U' characters, then a block of 'D' characters... etc. (Of course if our string starts with D then the letters are the opposite). And flip the D blocks. </p>
<p>The number of D blocks = (The number of U blocks) or (the number of U blocks + 1)</p>
<p>If our string starts with D then</p>
<p>The number of U blocks = (The number of D blocks) or (the number of D blocks + 1)</p>
<p>so our answer would be <strong>[number of blocks / 2]</strong> (of course rounded down).</p>
<h1>Example:</h1>
<p>Consider our string was "<strong>UUUDDUUUDDDUU</strong>"</p>
<p>We would split it into :</p>
<p><strong>[UUU] , [DD] , [UUU] , [DDD] , [UU]</strong></p>
<p>The best solution is to flip <strong>[DD] , [DDD]</strong></p>
<h1>Another Example :</h1>
<p>Consider our string was "<strong>DDDUDDUU</strong>"</p>
<p>We would split it into :</p>
<p><strong>[DDD] , [U] , [DD] , [UU]</strong></p>
<p>Here because the number of U blocks is equal to number of D blocks then flipping the blocks of any letter would be optimal.</p>
<p>Why is this always correct?</p>
<p>If we are looking for a better solution than the mentioned above, then we should flip at least 2 of our targeted blocks at once. But that's impossible because we would affect at least one proper block between them (consisting of characters equal to our final character) and we must return it to its original state again and that's impossible without an additional move.</p>
<p>Consider we tried to obtain a better strategy in the first example:</p>
<p>That means that we would change all D letters to U in one move. It's only possible by flipping the substring <strong>[DDUUUDDD]</strong> (or any substring formed by extending this one from left or right), but doing this would change U letters to D and we need to return them back to U, and this will cost us at least one operation.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><strong>AUTHOR's solution</strong>: <a href="http://www.codechef.com/download/Solutions/COOK83/Setter/ADACRA.cpp">Here</a><br>
<strong>TESTER's solution</strong>: <a href="http://www.codechef.com/download/Solutions/COOK83/Tester1/ADACRA.cpp">Here</a></p>deadwing97Mon, 19 Jun 2017 03:34:48 +0530https://discuss.codechef.com/questions/102422/adacra-editorialcook83adacraeditorialcakewalkSNACKUP - Editorialhttps://discuss.codechef.com/questions/102423/snackup-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/SNACKUP">Practice</a> <br>
<a href="https://www.codechef.com/COOK83/problems/SNACKUP">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/alei">Alei Reyes</a> <br>
<strong>Primary Tester:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a> <br>
<strong>Secondary Tester:</strong> <a href="https://www.codechef.com/users/miyukine">Kacper Walentynowicz</a><br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>DIFFICULTY:</h1>
<p>Easy</p>
<h1>PREREQUISITES:</h1>
<p>None</p>
<h1>PROBLEM:</h1>
<p>We have <strong>n</strong> recipes and <strong>n</strong> judges to taste them. Each judge must try every recipe exactly twice. </p>
<p>You have to organize tasting rounds. A round is is structured as follows:</p>
<p>You will choose distinct <strong>k</strong> recipes and for each one of them prepare 2 <strong>identical</strong> dishes.
You will choose distinct <strong>k</strong> judges and each of them must try 2 <strong>different</strong> recipes from the ones we chose (1 dish of each of them in particular). Two different judges may try the same recipe (but they may not share a common dish).</p>
<p>After each round all prepared dishes must be eaten by judges.</p>
<p>You can arbitrarily decide the number of rounds, and the structure of each one (number of invited judges), but as a rule of the contest at the end of all round each judge must have tasted every recipe exactly twice. </p>
<h1>EXPLANATION:</h1>
<p>This is a constructive problem, which can be solved by different ways. I will describe mine which is quite simple.</p>
<p>Let's organize <strong>n</strong> rounds. You can imagine the recipes aligned in a circle. At the <strong>1<sup>st</sup></strong> round the <strong>i<sup>th</sup></strong> judge is standing beside the <strong>i<sup>th</sup></strong> recipe. In each round each judge tries the recipe he is standing beside and the next one in front of him. After each round our judges move 1 step around the circle. Check this solution for n = 4 :
</p><table width="278">
<tbody>
<tr>
<td>Round</td>
<td>Judge</td>
<td>1st Recipe</td>
<td>2nd recipe</td>
</tr>
<tr>
<td>1</td>
<td>1</td>
<td>1</td>
<td>2</td>
</tr>
<tr>
<td>1</td>
<td>2</td>
<td>2</td>
<td>3</td>
</tr>
<tr>
<td>1</td>
<td>3</td>
<td>3</td>
<td>4</td>
</tr>
<tr>
<td>1</td>
<td>4</td>
<td>4</td>
<td>1</td>
</tr>
<tr>
<td>2</td>
<td>1</td>
<td>2</td>
<td>3</td>
</tr>
<tr>
<td>2</td>
<td>2</td>
<td>3</td>
<td>4</td>
</tr>
<tr>
<td>2</td>
<td>3</td>
<td>4</td>
<td>2</td>
</tr>
<tr>
<td>2</td>
<td>4</td>
<td>1</td>
<td>1</td>
</tr>
<tr>
<td>3</td>
<td>1</td>
<td>3</td>
<td>4</td>
</tr>
<tr>
<td>3</td>
<td>2</td>
<td>4</td>
<td>1</td>
</tr>
<tr>
<td>3</td>
<td>3</td>
<td>1</td>
<td>2</td>
</tr>
<tr>
<td>3</td>
<td>4</td>
<td>2</td>
<td>3</td>
</tr>
<tr>
<td>4</td>
<td>1</td>
<td>4</td>
<td>1</td>
</tr>
<tr>
<td>4</td>
<td>2</td>
<td>1</td>
<td>2</td>
</tr>
<tr>
<td>4</td>
<td>3</td>
<td>2</td>
<td>3</td>
</tr>
<tr>
<td>4</td>
<td>4</td>
<td>3</td>
<td>4</td>
</tr>
</tbody>
</table>
<p> </p><p></p>
<p>By scheduling rounds this way, it's guaranteed that every recipe would be tasted by every judge exactly twice by the end of the <strong>n<sup>th</sup></strong> round.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><strong>AUTHOR's solution</strong>: <a href="http://www.codechef.com/download/Solutions/COOK83/Setter/SNACKUP.cpp">Here</a><br>
<strong>TESTER's solution</strong>: <a href="http://www.codechef.com/download/Solutions/COOK83/Tester1/SNACKUP.cpp">Here</a></p>deadwing97Mon, 19 Jun 2017 04:27:18 +0530https://discuss.codechef.com/questions/102423/snackup-editorialad-hoccook83snackupeasyconstructiveCENTREE - Editorialhttps://discuss.codechef.com/questions/102432/centree-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/CENTREE">Practice</a> <br>
<a href="https://www.codechef.com/COOK83/problems/CENTREE">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/alei">Alei Reyes</a> <br>
<strong>Primary Tester:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a> <br>
<strong>Secondary Tester:</strong> <a href="https://www.codechef.com/users/miyukine">Kacper Walentynowicz</a><br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>DIFFICULTY:</h1>
<p>Easy</p>
<h1>PREREQUISITES:</h1>
<p>Graph Theory</p>
<h1>PROBLEM:</h1>
<p>Construct a tree of <strong>N</strong> nodes such that the maximum distance between one of its centers and one of its centroids is exactly <strong>B</strong>.</p>
<p>A vertex <strong>u</strong> is a centroid if after removing <strong>u</strong> from the tree, the size of any of the resulting connected components is at most <strong>n/2</strong>.</p>
<p>Let <strong>f(x)</strong> be the greatest distance from u to any other vertex of the tree. A vertex <strong>u</strong> is a center if <strong>f(u) ≤ f(v)</strong> for any other vertex <strong>v</strong>. </p>
<h1>EXPLANATION:</h1>
<p>First of all let's create a tree consisting of a single node numbered <strong>1</strong> and assuming that it will be our centroid. </p>
<p>Now we should construct a chain consisting of <strong>B</strong> edges ending in a node representing our future center and this node is numbered <strong>B+1</strong>. Currently our tree is composed of a chain containing <strong>B+1</strong> nodes. Currently node <strong>B+1</strong> is not the center of our tree. So to make it our center we should extend this chain from this node by <strong>B</strong> extra nodes. Resulting a chain consisting of <strong>2*B+1</strong> node where the i<sup>th</sup> node and the (i+1)<sup>th</sup> node are connected by an edge for each <strong>0 < i < 2*B+1</strong></p>
<p>Now we assured that node <strong>B+1</strong> is our center. And clearly node <strong>1</strong> is not our centroid. So we must make use of the remaining nodes and attach each one of them directly to node <strong>1</strong> (Each of them connected to <strong>1</strong> by a directed edge so we keep our center unchanged). Of course we must have enough nodes to ensure that. Removing node <strong>1</strong> would leave us with a subtree consisting of <strong>2*B</strong> nodes, and subtrees made of single nodes (we attached). </p>
<p>As a conclusion we can say that for any <strong>N,B</strong> such that :</p>
<p><strong>2*B ≤ N/2</strong> <strong>-></strong> <strong>4*B ≤ N</strong> </p>
<p>A solution exists and can be constructed by this way. For cases where 4*B > N, constructing such a tree is impossible.</p>
<p>Of course we must handle this special case : </p>
<p>Case n = 2:</p>
<p>if B = 1 the tree made of 2 nodes connected by an edge is the solution, for other values of B the answer is NO</p>
<p>This image briefly describes the configuration of our tree:
<img alt="centree" src="https://codechef_shared.s3.amazonaws.com/download/upload/COOK83/centroid.jpg"></p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><strong>AUTHOR's solution</strong>: <a href="http://www.codechef.com/download/Solutions/COOK83/Setter/CENTREE.cpp">Here</a><br>
<strong>TESTER's solution</strong>: <a href="http://www.codechef.com/download/Solutions/COOK83/Tester1/CENTREE.cpp">Here</a></p>deadwing97Mon, 19 Jun 2017 07:10:14 +0530https://discuss.codechef.com/questions/102432/centree-editorialcentreead-hocgraphtreeconstructivecook83editorialKNICOV - Editorialhttps://discuss.codechef.com/questions/102582/knicov-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/KNICOV">Practice</a> <br>
<a href="https://www.codechef.com/COOK83/problems/KNICOV">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/alei">Alei Reyes</a> <br>
<strong>Primary Tester:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a> <br>
<strong>Secondary Tester:</strong> <a href="https://www.codechef.com/users/miyukine">Kacper Walentynowicz</a><br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>DIFFICULTY:</h1>
<p>Easy - Medium</p>
<h1>PREREQUISITES:</h1>
<p>DP , bitmasks</p>
<h1>PROBLEM:</h1>
<p>Given a board consisting of <strong>N</strong> rows , <strong>M</strong> columns. <strong>(N <= 3 , M <= 50)</strong>. What is the minimum number of knights we could place such that each cell is occupied by a knight or attacked by at least one knight.</p>
<h1>OBSERVATIONS</h1>
<p>Let’s consider some cases first:</p>
<p>If <strong>N = 1</strong> ,then it’s clear that we should fill our board completely, because a knight cannot attack a cell in the same row. So we must fill all of them.</p>
<p>If <strong>N = 2</strong> , let’s consider the starting few cases</p>
<p><strong>M=1 or M=2</strong> we should completely fill the board</p>
<p><strong>M = 3</strong> we should fill it this way
</p><table width="82">
<tbody>
<tr>
<td>Empty</td>
<td>Knight</td>
<td>Knight</td>
</tr>
<tr>
<td>Empty</td>
<td>Knight</td>
<td>Knight</td>
</tr>
</tbody>
</table><p></p>
<p><strong>M = 4</strong> try to figure it yourself.</p>
<p>Let's consider <strong>M = 6</strong>, the optimal way to fill for <strong>N=2,M=6</strong> is :</p>
<table width="145">
<tbody>
<tr>
<td>Empty</td>
<td>Empty</td>
<td>Knight</td>
<td>Knight</td>
<td>Empty</td>
<td>Empty</td>
</tr>
<tr>
<td>Empty</td>
<td>Empty</td>
<td>Knight</td>
<td>Knight</td>
<td>Empty</td>
<td>Empty</td>
</tr>
</tbody>
</table>
<p> </p>
<p>It's optimal to place our knights in the middle because a knight can attack cells to the left and to the right. You can notice that this is strategy is optimal for filling boards consisting of <strong>2</strong> rows and any number of columns. Taking each <strong>6</strong> consecutive columns and placing 4 knights in the same way above. Because to eliminate the first column you must place 2 knights either in the first column or in the third column, and of course placing them in the third is better (so they can eliminate another succeeding columns). The same relation holds between the second and the forth column. You can prove the correctness by this logic and continue filling the board.</p>
<p>So our answer for <strong>N = 2</strong> equals :</p>
<p>$ \lfloor{\frac{M}{6}}\rfloor * 4 + min(M \ mod \ 6 , 2) * 2 $</p>
<p>Now we are left with <strong>N = 3</strong> case, this is solved by Dynamic Programming.</p>
<h1>EXPLANATION:</h1>
<p>First of all let's think of a recursive solution to fill the board and pick the cheapest way. Something important we should take advantage of is that we have only <strong>3</strong> rows, so filling the board column by column would make it much easier for us. So let's fill them one by one from left to right:</p>
<p>Let's say we are filling a certain column, which columns affect our current? The next 2 columns may affect our current one (but we will take them down later since we are filling from left to right), and the previous 2 columns. Also, our current column affects the next 2 and the previous 2. So it's mandatory to know the knights placement configuration in the previous 2. Columns further than 2 steps don't affect our current column. We can store information about each column in a mask of 3 bits.</p>
<p>So is it enough to store only information about the knights placement in the previous 2 columns?</p>
<p>Actually No, Let's consider the pre-previous column (the one before the previous). It may contain some <strong>empty</strong> cells which are attacked by columns behind it (and we don't have information about them since we are only keeping info about the last 2). After filling our current column we should get rid of the pre-previous column before continuing to our next one, so we must assure that cells of this column are all attacked (so we are missing some information that we must have kept in order to determine that the pre-previous column is completely attacked). This information can be kept in different ways. In my solution, I store information about the attacked cells in the previous 2 columns in addition to knights placement in them and update this information between calls of my function. By attacked cells I mean for each column, I mark cells which are occupied or attacked by any other previously placed knight. </p>
<p>This information is enough to make us able to write a Dynamic Programming solution:</p>
<p><strong>Dp[column][PrePreAttacked][PreAttacked][PrePreKnights][PreKnights]</strong></p>
<p>For each state, we should iterate on all possible ways of filling this new column, after that we must make sure that Pre-Previous column cells are all attacked (after filling our current column in addition to information we have about it).</p>
<p>After that we can take rid of PrePrevious column and proceed to the next column. Of course we should update the information about the attacked cells in the Previous column (which will be the pre-previous column after we call the function for the next one) and also update the attacked cells in our latest filled column (which would become the previous) before calling the function for the next column.</p>
<p>Another Dynamic Programming solution is done by keeping information about knights placement in the previous 4 columns.</p>
<p>This solution runs in :</p>
<p><strong>O(M * 2^<sup>5*n</sup>)</strong></p>
<p>Final Note:</p>
<p>This DP solution works for all N (small values because complexity is pretty huge), but I found that solving N={1,2} cases separately would make it easier for me while implementing the DP.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><strong>AUTHOR's solution</strong>: Will be uploaded soon. <br>
<strong>TESTER's solution</strong>: <a href="http://www.codechef.com/download/Solutions/COOK83/Tester1/KNICOV.cpp">Here</a></p>deadwing97Mon, 19 Jun 2017 19:26:53 +0530https://discuss.codechef.com/questions/102582/knicov-editorialbitmaskseditorialdynamic-programmingcook83easy-mediumknicovADADET - Editorialhttps://discuss.codechef.com/questions/102761/adadet-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/ADADET">Practice</a> <br>
<a href="https://www.codechef.com/COOK83/problems/ADADET">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/alei">Alei Reyes</a> <br>
<strong>Primary Tester:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a> <br>
<strong>Secondary Tester:</strong> <a href="https://www.codechef.com/users/miyukine">Kacper Walentynowicz</a><br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>DIFFICULTY:</h1>
<p>Medium</p>
<h1>PREREQUISITES:</h1>
<p>Basic Geometry , Convex Hull</p>
<h1>PROBLEM:</h1>
<p>Given N towers on the X axis. Each tower can be imagined a straight vertical segment. Given the position of each tower on the axis and its height (segment length). Towers are given in ascending order of positions, and no 2 towers share the same height.</p>
<p>You have to determine for each tower the rightmost tower with <strong>shorter height</strong> such that drawing a segment between their tops doesn't intersect any other tower. Intersection with towers exactly at its top is ok. (this case is covered in the sample please check the image in problem description).</p>
<p>N ≤ 500000</p>
<h1>EXPLANATION:</h1>
<p>This problem is similar to finding the upper convex hull of a set of points, but forcing each tower to be able to shoot only shorter towers made it a little bit tricky.</p>
<p>An important observation here. Consider the i<sup>th</sup> tower and let's find the smallest j (j>i) such that H<sub>j</sub> > H<sub>i</sub>. (The closest tower to the i<sup>th</sup> which is taller than it). It's obvious that we can't draw a segment from the i<sup>th</sup> to any other <strong>shorter</strong> tower after the j<sup>th</sup> one without intersecting with it. (Proof is easy).</p>
<p>Let's process the towers one by one from the rightmost one to the leftmost one. We will stack our towers into piles, each one having towers sorted in decreasing order of height from left to right.
Suppose we are processing a certain tower and the last added tower was higher, so the answer of our current tower would be -1 and we will make a new pile and insert it into.</p>
<p>Since each pile will have towers sorted in height from left to right, If we consider having towers forming only one pile, then the segments representing answers of towers in this pile must form the upper convex hull of it. (Check these examples of a pile):</p>
<p><img alt="alt text" src="https://codechef_shared.s3.amazonaws.com/upfiles/pile1.jpg"></p>
<p><img alt="alt text" src="https://codechef_shared.s3.amazonaws.com/upfiles/pile2.jpg"></p>
<p>Now back to our problem, let's consider this case. Points <strong>A,B,C</strong> must be added into the same pile.
Currently, ans(A) = -1 , ans(B) = A , ans(C) = B</p>
<p><img alt="alt text" src="https://codechef_shared.s3.amazonaws.com/upfiles/ed1.jpg"></p>
<p>If our tower was higher than the last added one <strong>(and we had only one pile)</strong>, we should process the pile, and evaluate our current tower with the last added two towers to ensure that we are maintaining the convex hull of this pile, and this can be done easily by checking the cross product of 2 vectors and behaving according to the sign.</p>
<p>Let's insert point <strong>D</strong>, as you can see the vectors (D->C,C->B) make a counter clockwise turn, so we must pop point C from our pile to maintain convexity.</p>
<p><img alt="alt text" src="https://codechef_shared.s3.amazonaws.com/upfiles/ed2.jpg"></p>
<p>The trick here is when we have a tower to process and we have more than one pile (with the highest tower of each shorter than the processed tower), then we should drop the nearest pile as long as we have more than one. After that, we will be left with only one pile and we insert our tower there. Because the head of each pile will have no tower to the left higher than it, otherwise we would insert it in the same pile (or maybe drop the whole pile). So since our current tower is higher than the shot one and the shot one has no higher tower to the left. We can shoot it without intersecting with any other tower.</p>
<p>After processing points <strong>{A,B,C,D,E,F}</strong> we had two piles <strong>{A,B,C,D},{E,F}</strong>. When we came to process point <strong>G</strong>, you can see that we can shoot the head of each pile. The purpose of dropping piles can be shown in this sample. Because point E cannot be shot from point G.</p>
<p><img alt="alt text" src="https://codechef_shared.s3.amazonaws.com/upfiles/ed3.jpg"></p>
<p>We insert point <strong>G</strong> into the pile of <strong>D</strong> and drop <strong>{E,F}</strong></p>
<p><img alt="alt text" src="https://codechef_shared.s3.amazonaws.com/upfiles/ed4.jpg"></p>
<p>This solution runs in <strong>O(N)</strong>, each tower is inserted once, and may be popped once and for all.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><strong>AUTHOR's solution</strong>: <a href="http://www.codechef.com/download/Solutions/COOK83/Setter/ADADET.cpp">Here</a><br>
<strong>TESTER's solution</strong>: <a href="http://www.codechef.com/download/Solutions/COOK83/Tester1/ADADET.cpp">Here</a></p>deadwing97Tue, 20 Jun 2017 23:07:24 +0530https://discuss.codechef.com/questions/102761/adadet-editorialmediumgeometryhullcook83adadetconvexstackJune CookOff ADADET Editorialhttps://discuss.codechef.com/questions/102854/june-cookoff-adadet-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/ADADET">Practice</a> <br>
<a href="https://www.codechef.com/COOK83/problems/ADADET">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/alei">Alei Reyes</a> <br>
<strong>Primary Tester:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a> <br>
<strong>Secondary Tester:</strong> <a href="https://www.codechef.com/users/miyukine">Kacper Walentynowicz</a><br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>DIFFICULTY:</h1>
<p>Medium</p>
<h1>PREREQUISITES:</h1>
<p>Basic Geometry , Convex Hull</p>
<h1>PROBLEM:</h1>
<p>Given N towers on the X axis. Each tower can be imagined a straight vertical segment. Given the position of each tower on the axis and its height (segment length). Towers are given in ascending order of positions, and no 2 towers share the same height.</p>
<p>You have to determine for each tower the rightmost tower with <strong>shorter height</strong> such that drawing a segment between their tops doesn't intersect any other tower. Intersection with towers exactly at its top is ok. (this case is covered in the sample please check the image in problem description).</p>
<p>N ≤ 500000</p>
<h1>EXPLANATION:</h1>
<p>This problem is similar to finding the upper convex hull of a set of points, but forcing each tower to be able to shoot only shorter towers made it a little bit tricky.</p>
<p>An important observation here. Consider the i<sup>th</sup> tower and let's find the smallest j (j>i) such that H<sub>j</sub> > H<sub>i</sub>. (The closest tower to the i<sup>th</sup> which is taller than it). It's obvious that we can't draw a segment from the i<sup>th</sup> to any other <strong>shorter</strong> tower after the j<sup>th</sup> one without intersecting with it. (Proof is easy).</p>
<p>Let's process the towers one by one from the rightmost one to the leftmost one. We will stack our towers into piles, each one having towers sorted in decreasing order of height from left to right.
Suppose we are processing a certain tower and the last added tower was higher, so the answer of our current tower would be -1 and we will make a new pile and insert it into.</p>
<p>Since each pile will have towers sorted in height from left to right, If we consider having towers forming only one pile, then the segments representing answers of towers in this pile must form the upper convex hull of it. (Check these examples of a pile):</p>
<p><img alt="alt text" src="https://codechef_shared.s3.amazonaws.com/upfiles/pile1.jpg"></p>
<p><img alt="alt text" src="https://codechef_shared.s3.amazonaws.com/upfiles/pile2.jpg"></p>
<p>Now back to our problem, let's consider this case. Points <strong>A,B,C</strong> must be added into the same pile.
Currently, ans(A) = -1 , ans(B) = A , ans(C) = B</p>
<p><img alt="alt text" src="https://codechef_shared.s3.amazonaws.com/upfiles/ed1.jpg"></p>
<p>If our tower was higher than the last added one <strong>(and we had only one pile)</strong>, we should process the pile, and evaluate our current tower with the last added two towers to ensure that we are maintaining the convex hull of this pile, and this can be done easily by checking the cross product of 2 vectors and behaving according to the sign.</p>
<p>Let's insert point <strong>D</strong>, as you can see the vectors (D->C,C->B) make a counter clockwise turn, so we must pop point C from our pile to maintain convexity.</p>
<p><img alt="alt text" src="https://codechef_shared.s3.amazonaws.com/upfiles/ed2.jpg"></p>
<p>The trick here is when we have a tower to process and we have more than one pile (with the highest tower of each shorter than the processed tower), then we should drop the nearest pile as long as we have more than one. After that, we will be left with only one pile and we insert our tower there. Because the head of each pile will have no tower to the left higher than it, otherwise we would insert it in the same pile (or maybe drop the whole pile). So since our current tower is higher than the shot one and the shot one has no higher tower to the left. We can shoot it without intersecting with any other tower.</p>
<p>After processing points <strong>{A,B,C,D,E,F}</strong> we had two piles <strong>{A,B,C,D},{E,F}</strong>. When we came to process point <strong>G</strong>, you can see that we can shoot the head of each pile. The purpose of dropping piles can be shown in this sample. Because point E cannot be shot from point G.</p>
<p><img alt="alt text" src="https://codechef_shared.s3.amazonaws.com/upfiles/ed3.jpg"></p>
<p>We insert point <strong>G</strong> into the pile of <strong>D</strong> and drop <strong>{E,F}</strong></p>
<p><img alt="alt text" src="https://codechef_shared.s3.amazonaws.com/upfiles/ed4.jpg"></p>
<p>This solution runs in <strong>O(N)</strong>, each tower is inserted once, and may be popped once and for all.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>deadwing97Wed, 21 Jun 2017 22:50:52 +0530https://discuss.codechef.com/questions/102854/june-cookoff-adadet-editorialcook83mediumstackconvexhulleditorialNITIKA - editorialhttps://discuss.codechef.com/questions/104163/nitika-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/JULY17/problems/NITIKA">Practice</a> <br>
<a href="https://www.codechef.com/problems/NITIKA">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/iamabjain">Abhinav Jain</a> <br>
<strong>Primary Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>DIFFICULTY:</h1>
<p>Cakewalk</p>
<h1>PREREQUISITES:</h1>
<p>None</p>
<h1>PROBLEM:</h1>
<p>Given names of people. Each name may consist of at least one and at most three parts. You are asked to show the name with replacing the first two parts (if they exist) with the first letter of each (abbreviation) and followed by the last part (last name). Abbreviations should be upper case letters. <strong>Only</strong> the first letter of the last name should be in uppercase.</p>
<h1>EXPLANATION:</h1>
<p>This problem is straight forward implementation (string manipulation). Each name will be given on a separate line, so we should read each line completely (one by one). We have to find the parts of each name and separate them from each other. Since each two consecutive parts are separated by a space,we should be looking for spaces in each line. The first space (if it exists) separates between the 1<sup>st</sup> and the 2<sup>nd</sup> part, the second space (if it exists) separates between the 2<sup>nd</sup> and the 3<sup>rd</sup> part. Finding spaces on each line would make us able to break our full name into parts (This can be done manually by a loop). </p>
<p>My solution uses stringstream (C++ class) which is very useful for parsing input and solves this problem easily. A brief explanation can be found here :<a href="https://www.eecis.udel.edu/~breech/progteam/stringstream.html">stringstream</a></p>
<p>After breaking the name into parts we should capitalize the first letter of each part. We should output <strong>only</strong> the first letter of each part capitalized (except the last part). As for the last part, we must set its first letter to uppercase, and the rest of its letters to lowercase. After that, we can print it.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><strong>AUTHOR's solution</strong>: Will be found <a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Setter/NITIKA.java">here</a> <br>
<strong>TESTER's solution</strong>: Will be found <a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Tester/NITIKA.cpp">here</a><br>
<strong>EDITORIALIST's solution</strong>: Will be found <a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Editorialist/NITIKA.cpp">here</a></p>deadwing97Tue, 04 Jul 2017 19:13:18 +0530https://discuss.codechef.com/questions/104163/nitika-editorialjuly17implementationnitikaeditorialCHEFSIGN - Editorialhttps://discuss.codechef.com/questions/105178/chefsign-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/JULY17/problems/CHEFSIGN">Practice</a> <br>
<a href="https://www.codechef.com/problems/CHEFSIGN">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/berezin">Dmytro Berezin</a> <br>
<strong>Primary Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>DIFFICULTY:</h1>
<p>Cakewalk</p>
<h1>PREREQUISITES:</h1>
<p>None</p>
<h1>PROBLEM:</h1>
<p>Given a sequence of <strong>N</strong> arithmetic signs <strong>( = , + , - )</strong> between <strong>N+1</strong> unknown integers. You are allowed to fix these integers using numbers in the range [1,P] such that the expression is true when you read it from left to right. (Numbers don't violate the signs). You are asked to calculate <strong>minimum</strong> possible <strong>P</strong> such you can construct a valid expression.</p>
<h1>EXPLANATION:</h1>
<p>First of all, it's clear that we can drop all <strong>'='</strong> signs and pretend that they never existed, because each number which follows an '=' sign would be identical to the number preceding this sign. So these signs aren't affecting our answer at all.
After discarding all '=' signs our answer would be :</p>
<p><strong>P = max(maximum number of consecutive '<' signs, maximum number of consecutive '>' signs) + 1</strong></p>
<p>Let's process our expression from left to right, If we are facing <strong>X (X ≤ P-1)</strong> consecutive '<' signs, our starting number would be <strong>P-X</strong>, and we increment our last number by 1 after each sign,so the number after the last sign would be exactly <strong>P</strong> (which will be followed by '>' sign). Our last number will be followed by <strong>Y</strong> consecutive '>' signs, so we assign the next number to <strong>Y (Y < P)</strong> and we decrement the last number by 1 by each '>' sign we process. The number after the last sign would be <strong>1</strong>. (In case our expression starts with '>' the situation would just be reversed).
After that we would have another block of <strong>Z</strong> consecutive '<' signs, so we assign the next number to <strong>P-Z (P-Z ≥ 1)</strong> so the number after the last sign would be <strong>P</strong> and we continue....</p>
<p>Following this approach, the last number after a block of consecutive '<' signs would be <strong>P</strong> (the maximal value), and the last number after a block of consecutive '>' signs would be <strong>1</strong> (the minimal value). So according to our bold assumption below we can assign values using numbers in the range <strong>[1,P]</strong> without violating the signs.</p>
<p>Let's take an example:</p>
<p><<<=>=>=>>><<>>>><<<<<>><<>></p>
<p>After removing = signs our sequence would be</p>
<p><<< >>>>> << >>>> << >>>>></p>
<p>(Blocks are separated by spaces for clarity)</p>
<p>here P = max(3 , 5 , 2 , 4 , 5 , 2 , 2 , 2) + 1 = 6</p>
<p>Our sequence would be</p>
<p><strong>3</strong> < 4 < 5 < <strong>6</strong> > 5 > 4 > 3 > 2 > <strong>1</strong> < <strong>5</strong> < <strong>6</strong> > <strong>4</strong> > 3 > 2 > <strong>1</strong> < <strong>5</strong> < 6 > 5 > 4 > 3 > 2 > 1</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><strong>TESTER's solution</strong>: Will be found <a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Tester/CHEFSIGN.cpp">here</a><br>
<strong>EDITORIALIST's solution</strong>: Will be found <a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Editorialist/CHEFSIGN.cpp">here</a></p>deadwing97Sat, 15 Jul 2017 06:48:55 +0530https://discuss.codechef.com/questions/105178/chefsign-editorialchefsignad-hocgreedyjuly17editorialcakewalkCALC - Editorialhttps://discuss.codechef.com/questions/105179/calc-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/JULY17/problems/CALC">Contest</a> <br>
<a href="https://www.codechef.com/problems/CALC">Practice</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/kingofnumbers">Hasan Jaddouh</a> <br>
<strong>Primary Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>DIFFICULTY:</h1>
<p>Easy</p>
<h1>PREREQUISITES:</h1>
<p>Simple Math</p>
<h1>PROBLEM:</h1>
<p>We have a calculator with 2 screens and 2 buttons. Each screen shows number zero initially. Pressing the first button increments the number on the first screen by <strong>1</strong>, and each press of this button consumes <strong>1</strong> unit of energy. Pressing the second button increases the number on the second screen by the number appearing on the first screen. Each click of this button consumes <strong>B</strong> units of energy. Given <strong>B,N</strong> what's the maximum possible number that may show on the second screen without consuming more than <strong>N</strong> units of energy?</p>
<h1>EXPLANATION:</h1>
<p>First of all, it's obvious that it's not optimal to press the first button after pressing the second. We must press the first button for number of times, after that we should spend the remaining energy on pressing the second button.</p>
<p>Let's define a function <strong>f(x)</strong> where <strong>f(x)</strong> represents the maximum number displayed on the second screen if we pressed the second button exactly <strong>x</strong> times.</p>
<p>$f(x) = (N-x*B) * x$</p>
<p>$f(x) = -x^2 * B + Nx$</p>
<p>We can notice that the graph of this function is a parabola. Our best answer would be
$f(k) = h$</p>
<p>where the point <strong>(k,h)</strong> is the vertex of the parabola. It's well known that</p>
<p>$k = \frac{-b}{2a} $</p>
<p>for any parabola following the form $f(x) = ax^2 + bx + c$</p>
<p>So here : $k = \frac{N}{2*B}$</p>
<p>We can also deduce that from the derivative and find the local extrema of the function.</p>
<p>Since we can press the second button only integer number of presses so we must try,
$k1 = \lfloor \frac{N}{2*B}\rfloor$ <strong>AND</strong> $k2 = \lceil \frac{N}{2*B}\rceil$ and pick the better choice.</p>
<p>Ternary search is another possible solution for this problem.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><strong>AUTHOR's solution</strong>: Will be found <a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Setter/CALC.cpp">here</a> <br>
<strong>TESTER's solution</strong>: Will be found <a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Tester/CALC.cpp">here</a><br>
<strong>EDITORIALIST's solution</strong>: Will be found <a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Editorialist/CALC.cpp">here</a></p>deadwing97Sat, 15 Jul 2017 07:07:22 +0530https://discuss.codechef.com/questions/105179/calc-editorialeditorialsimple-mathjuly17easycalcmathIPCTRAIN - Editorialhttps://discuss.codechef.com/questions/105180/ipctrain-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/JULY17/problems/IPCTRAIN">Practice</a> <br>
<a href="https://www.codechef.com/problems/IPCTRAIN">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/admin2">Admin2</a> <br>
<strong>Primary Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>DIFFICULTY:</h1>
<p>Easy</p>
<h1>PREREQUISITES:</h1>
<p>Greedy,Heap</p>
<h1>PROBLEM:</h1>
<p>You have an upcoming camp. There are N trainers. The camp runs for <strong>D</strong> days.Each day,there can be at most one lecture. The <strong>i<sup>th</sup></strong> trainer arrives on day <strong>D<sub>i</sub></strong> and then stays till the end of the camp. He also wants to teach exactly <strong>T<sub>i</sub></strong> lectures. For each lecture that a trainer was not able to teach,his sadness level will be increased by <strong>S<sub>i</sub>.</strong>
You are the main organizer of the contest. You want to find minimum total sadness of the trainers.</p>
<h1>EXPLANATION:</h1>
<p>Let's assign our trainers starting from the first day of the camp. At each day adding arriving trainers to our set of trainers.</p>
<p>Each day should be assigned to only <strong>one</strong> trainer, it's obvious that we should assign the trainer with maximum sadness to this lecture, so our set (container) should be a heap sorting trainers by their sadness value. In fact we should know also the number of days each lecturer wants to serve in, so we take the lecturer with maximum sadness from our heap and decrease his demand by 1. In case he still has lectures he would like to do, we keep him in the heap, otherwise we just pop him out.</p>
<p>After finishing all days, some teachers may have some remaining lectures they wanted to teach but we couldn't find such days for them. Let's denote the number of lectures the <strong>i<sup>th</sup></strong> trainer couldn't teach by <strong>rem<sub>i</sub></strong> So our answer would be :</p>
<p>$answer = \sum_{i=1}^{i=N} rem_i * S_i$</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><strong>AUTHOR's solution</strong>: Will be found <a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Setter/IPCTRAIN.cpp">here</a> <br>
<strong>TESTER's solution</strong>: Will be found <a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Tester/IPCTRAIN.cpp">here</a><br>
<strong>EDITORIALIST's solution</strong>: Will be found <a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Editorialist/IPCTRAIN.cpp">here</a></p>deadwing97Sat, 15 Jul 2017 07:23:59 +0530https://discuss.codechef.com/questions/105180/ipctrain-editorialeasystlipctraingreedyjuly17heapeditorialPSHTTR - Editorialhttps://discuss.codechef.com/questions/105181/pshttr-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/PSHTTR">Practice</a> <br>
<a href="https://www.codechef.com/JULY17/problems/PSHTTR">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/fekete">Ivan Fekete</a> <br>
<strong>Primary Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>DIFFICULTY:</h1>
<p>Medium</p>
<h1>PREREQUISITES:</h1>
<p>Graph Theory,Sorting,Data Structures</p>
<h1>PROBLEM:</h1>
<p>Given a rooted weighted tree with <strong>N</strong> nodes and <strong>M</strong> queries of the form <strong>(u , v , K)</strong>. For each query, you must report to <strong>xor</strong> sum of edges which has weight less than or equal to <strong>K</strong> on the path from <strong>u</strong> to <strong>v</strong>.</p>
<p><strong>N,M ≤ 10^5</strong></p>
<h1>EXPLANATION:</h1>
<p>First of all let's solve the easier version of this problem. Queries which asks for the xor sum of edges on the path between 2 fixed nodes <strong>(without the restriction of K).</strong>
Let's choose an arbitrary root for our tree and call a Depth-First search starting from this node.Let's maintain a table <strong>S[N]</strong>, such that <strong>S<sub>i</sub></strong> denotes the <strong>xor</strong> sum of edges weights starting from the <strong>root</strong> and ending at node <strong>i</strong>. The answer of each query <strong>(u,v)</strong> would be <strong>(S<sub>u</sub> xor S<sub>v</sub>)</strong>. Edges of the chain starting from the root and ending at <strong>LCA(u,v)</strong> (lowest common ancestor) would be excluded because <strong>(V xor V = 0)</strong>.</p>
<p>Now let's solve our problem. First thing we should take advantage of, is that we can answer our queries offline (reading then processing all queries, after that reporting the answer of each one).
Each edge weighted <strong>W</strong> must be included in the answer of all queries with <strong>K ≥ W</strong>. For queries with <strong>K < W</strong> we can assume that this edge's weight is zero (so it won't affect the answers).</p>
<p>Let's sort our queries in ascending order according to their magic numbers <strong>K</strong>, and sort our edges in ascending order according to their weights <strong>W</strong>. Let's process our queries in ascending order, and maintain a pointer iterating on our sorted edges list. So before processing a query with magic number <strong>K</strong>, we add all edges with <strong>W ≤ K</strong> through our pointer.</p>
<p>Now Let's discuss adding edges, and how will we get our table S[].</p>
<p>Let's maintain a timer incremented by one every time we visit a new node in our Depth-First-Search, and keep for the <strong>i<sup>th</sup></strong> node a variable <strong>st<sub>i</sub></strong> (denoting the value of the timer once entering this node),and a variable <strong>en<sub>i</sub></strong> denoting the value of the timer after finishing this node's subtree (before exiting). This is a famous technique called euler tour on tree (dfs order). So we can represent nodes located in the subtree of the <strong>i<sup>th</sup></strong> node by interval <strong>[st<sub>i</sub> , en<sub>i</sub>]</strong></p>
<p>Regarding adding edges, each edge will link between 2 nodes <strong>(u,v)</strong> such that <strong>u = par[v]</strong>, this edge's weight will be added to the <strong>xor sum</strong> (cumulative xor sum from the root) of all nodes located in the subtree of <strong>v</strong>. That means we should apply the operation</p>
<p><strong>S<sub>i</sub> = S<sub>i</sub> xor V</strong> </p>
<p>for each <strong>i</strong> : <strong>(st<sub>v</sub> ≤ i ≤ en<sub>v</sub>)</strong></p>
<p>This can be done using a binary indexed tree, segment tree (with/without) lazy probagation. Since our modification query is done on a segment of array <strong>S</strong> and we are querying the value of only one element we can do the following:</p>
<p>Let's maintain an array <strong>X</strong> which is all zeros at the beginning. When handling an edge of weight <strong>W</strong> added to the results of nodes in node v subtree. </p>
<p><strong>X[st<sub>i</sub>] = X[st<sub>i</sub>] xor V</strong></p>
<p>This means that we are adding V to the <strong>xor</strong> sum of all nodes with enterance <strong>timer ≥ st<sub>v</sub></strong></p>
<p><strong>X[en<sub>i</sub> + 1] = X[en<sub>i</sub> + 1] xor V</strong></p>
<p>This means that we are excluding <strong>V</strong> from the <strong>xor</strong> sum of all elements with entrance <strong>timer > en[v]</strong> (since it was added in the first operation so doing <strong>xor</strong> again is equivalent to exclusion).</p>
<p>You can notice now that the value of <strong>S<sub>i</sub></strong> is:</p>
<p><strong>S<sub>i</sub> = X<sub>1</sub> xor X<sub>2</sub> xor X<sub>3</sub> xor X<sub>4</sub> xor X<sub>5</sub> xor ... X<sub>i</sub></strong></p>
<p>Now we can easily iterate through our queries, and for each one we should make sure that all edges with weight less than or equal to this query magic number are added. After that, each query can be solved in O(log N).</p>
<p>Total complexity <strong>O(N log N + M (log M + log N))</strong></p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><strong>AUTHOR's solution</strong>: Will be found <a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Setter/PSHTTR.cpp">here</a> <br>
<strong>TESTER's solution</strong>: Will be found <a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Tester/PSHTTR.cpp">here</a> <br>
<strong>EDITORIALIST's solution</strong>: Will be found <a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Editorialist/PSHTTR.cpp">here</a></p>deadwing97Sat, 15 Jul 2017 08:10:24 +0530https://discuss.codechef.com/questions/105181/pshttr-editorialmediumpshttrjuly17datastructuresortingeditorialEXPTREE - Editorialhttps://discuss.codechef.com/questions/105248/exptree-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/JULY17/problems/EXPTREE">Practice</a> <br>
<a href="https://www.codechef.com/problems/EXPTREE">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/melfice">Aleksandr Kulkov</a> <br>
<strong>Primary Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>DIFFICULTY:</h1>
<p>Medium</p>
<h1>PREREQUISITES:</h1>
<p>Combinatorics,Math,Number Theory</p>
<h1>PROBLEM:</h1>
<p>Consider an <a href="https://en.wikipedia.org/wiki/Tree_(graph_theory)#Ordered_tree">ordered</a> tree with <strong>N</strong> vertices. Your task is to calculate the expected value of the number of vertices having exactly <strong>one</strong> child in such tree assuming that it is uniformly chosen from the set of all ordered trees of size <strong>N</strong>.</p>
<p>Consider the answer to be a proper fraction <strong>P/Q</strong>, where <strong>gcd(P, Q) = 1</strong>. Then your task is to output two integers <strong>PQ<sup>-1</sup></strong> mod <strong>10<sup>9</sup>+7</strong> and <strong>PQ<sup>-1</sup></strong> mod <strong>10<sup>9</sup>+9</strong></p>
<h1>EXPLANATION:</h1>
<h1>OBSERVATION 1:</h1>
<p>The number of ordered trees consisting of <strong>n</strong> nodes is equal to the <strong>(n-1)<sup>th</sup></strong> <a href="https://en.wikipedia.org/wiki/Catalan_number"><strong>catalan</strong></a> number. Imagine the <strong>Depth-First-Search</strong> order of the nodes of the trees, entering each node corresponds to an open bracket <strong>(</strong> , and finishing each node corresponds to a closed bracket <strong>)</strong> . So if we represented the <strong>DFS</strong> order of a tree it will form a simple balanced bracket sequence. </p>
<p>Two different ordered trees must have different bracket representations. So we can say that the number of ordered trees consisting of n nodes is equal to the number of balanced bracket sequences consisting of <strong>(n-1)</strong> pairs of brackets. <strong>(n-1)</strong> because our tree is <strong>connected</strong> so we must fix the root (the first and the last bracket in the expression). If the subexpression (the expression excluding the first and last bracket) is balanced, that guarantees that we will never exit the root before the last bracket and our tree is connected. </p>
<p>It's well known that the number of balanced bracket sequences of <strong>n</strong> pairs of brackets is equal to the <strong>n<sup>th</sup> catalan</strong> number.</p>
<p>$C_n = \frac{(2n)!}{(n+1)!n!}$</p>
<p>Before reading the next observation you should be familiar with <a href="https://brilliant.org/wiki/linearity-of-expectation/">Linearity Of Expectation</a>.</p>
<h1>OBSERVATION 2:</h1>
<p>Let's consider all different <strong>(n-1)</strong> ordered trees, and think about applying this operation. Choosing an arbitrary node of a tree and linking it to a <strong>single child</strong> <strong>(n<sup>th</sup> node)</strong> and removing all edges between our chosen node and its children, then linking them to our new node. So our new node would serve as a single child of the chosen one.</p>
<p>A node having one child in a tree is equivalent to a pair of brackets, with a balanced expression between them and surrounded by a pair of brackets.</p>
<p>Observe that each node in a tree consisting of <strong>n</strong> nodes and having only <strong>one</strong> child can be formed by applying this operation to <strong>only one</strong> tree of <strong>(n-1)</strong> nodes. It's exactly the same as choosing an opened bracket and its corresponding closing bracket in a simple balanced bracket sequence framing the subexpression between by a pair of brackets (our new node).</p>
<p>Thus our nominator <strong>P</strong> would be</p>
<p><strong>P = ( number of trees of n-1 nodes * (n-1) )</strong> </p>
<p>We multiplied by <strong>n-1</strong> which denotes the number of ways to choose the vertex we decided to apply this operation on.</p>
<p><strong>Q = ( number of trees of n nodes )</strong></p>
<p>$answer = \frac{C_{n-2} * (n-1)}{C_{n-1}}$</p>
<p>According to the catalan number formula we wrote above, this can be reduced to:</p>
<p>$answer = \frac{n * (n-1)}{4n-6}$</p>
<p>This fraction can be reduced easily by calculating GCDs between the denominator and the nominator terms. We can calculate <strong>PQ<sup>-1</sup></strong> after calculating the modular inverse of <strong>Q</strong> considering each modulo.</p>
<h1>Note:</h1>
<p>It's true that this solution is given without a formal proof. But the idea is quite simple and correct. Actually its correctness can be proved by intuition. In real life contests you won't have the internet to read formal proofs and papers or search for formulas for a sequence. This solution is not hard to get from scratch and worths trying. </p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><strong>AUTHOR's solution</strong>: Will be found <a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Setter/EXPTREE.cpp">here</a> <br>
<strong>TESTER's solution</strong>: Will be found <a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Tester/EXPTREE.cpp">here</a><br>
<strong>EDITORIALIST's solution</strong>: Will be found <a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Editorialist/EXPTREE.cpp">here</a> </p>deadwing97Sun, 16 Jul 2017 08:48:19 +0530https://discuss.codechef.com/questions/105248/exptree-editorialeditorialcombinatoricsjuly17numbertheoryexptreemathSRVRS - Editorialhttps://discuss.codechef.com/questions/105585/srvrs-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/JULY17/problems/SRVRS">Practice</a> <br>
<a href="https://www.codechef.com/problems/SRVRS">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/alexvaleanu">Alexandru Valeanu</a> <br>
<strong>Primary Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>DIFFICULTY:</h1>
<p>Challenge</p>
<h1>PREREQUISITES:</h1>
<p>Data Structures,Randomized Algorithms</p>
<h1>PROBLEM:</h1>
<p>Given N servers, each server located on a point <strong>(x,y)</strong> in the plane. Each server has processing units. You will be given the number of seconds each processing unit needs to complete a task (they are not necessarily the same). At most one task can be assigned to a unit, and it cannot be used before it finishes the task.<strong>Q</strong> tasks are pushed one by one into your queue, you can also assume that each task is located on a point in the plane. You must assign each task to a processing unit of a server you choose. The cost would be the distance between the task's and the server's points plus the processing time of the unit you have assigned this task to. You must solve this problem <strong>ONLINE</strong>. Each task must be assigned immediately to a unit. The time interval between two tasks is exactly one second. The total cost of all assignments must be minimum.</p>
<h1>EXPLANATION:</h1>
<p>The problem is a combination of two simplified real-life problems, <strong>KNN</strong> <strong>and min-cost job-scheduling</strong>. </p>
<p>KNN (k-nearest neighbors) is an important algorithm used in pattern recognition. Here we only had 2 dimensions to deal with. This is not the case for real problems. There are a lot of variations of the job-scheduling problem. Here we had an interactive version that could be solved (not optimally) by a greedy strategy.</p>
<p><a href="http://www.ri.cmu.edu/pub_files/pub1/moore_andrew_1991_1/moore_andrew_1991_1.pdf">KD-Trees</a> are the perfect and most popular tool to solve the <strong>KNN</strong> part of the problems. Any other space partitioning data structure would do the job. Using any of them helps finding the closest server (or set of servers) to a particular task. Then one core had to be chosen only from that set of server(s). </p>
<p>An elegant approach is contracting the plane into a smaller one by scaling all points by some constant. </p>
<p>The other part of the question required a lot more creativity than data-structures. And there is no right answer. Most contestants used a priority-queue for each server in order to track the optimal core. Another option was to use a balanced binary-search tree (or even a sorted-array) in order to maintain the same set of cores. Choosing a core at random from the set of optimal (by distance) servers was another option. </p>
<p>A prospective approach was choosing servers at random (400 was the number used by quite good number of contestants) and assign the task to the optimal core of each of them. This approach is effective when you don't have enough memory to a store a complex data structure. A lot of people would try to come up with more strategies instead of implementing hard data structures.</p>
<h1>Notes:</h1>
<p>Exploit all available time for a testcase. Finishing a test in 0.5 seconds while you have one extra second is pointless. You can try a lot of random choices in the remaining time or maybe try additional strategies.</p>
<p>Although it's harder to code, it is better to find a bag of 'closest' servers, the expected outcome of the algorithm won't be that perfect if you always tend to few choices.</p>
<p>Trying random servers is not a bad idea (trying random solutions is not a bad idea in general). For some problems random solutions are easy to implement ,reliable and efficient. On the other hand deterministic solutions for them might be a nightmare. There is no guarantee that the <strong>(BEST)</strong> (again under some measure of performance) is the closest one to you. That is why the cost terms of the sum were so close to each other.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><strong>AUTHOR's solution</strong>: Can be found <a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Setter/SRVRS.cpp">here</a> <br>
<strong>TESTER's solution</strong>: Can be found <a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Tester/SRVRS.cpp">here</a></p>deadwing97Tue, 18 Jul 2017 09:01:58 +0530https://discuss.codechef.com/questions/105585/srvrs-editorialkdtreechallengejuly17srvrseditorialdatastructresTWOCOINS - Editorialhttps://discuss.codechef.com/questions/105597/twocoins-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/TWOCOINS">Practice</a> <br>
<a href="https://www.codechef.com/JULY17/problems/TWOCOINS">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/admin3">admin3</a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>DIFFICULTY:</h1>
<p>Easy-Medium</p>
<h1>PREREQUISITES:</h1>
<p>Dynamic Programming</p>
<h1>PROBLEM:</h1>
<p>You have a <strong>rooted</strong> tree of <strong>N</strong> nodes, you can place at most one coin in each node. Find a strategy with minimum number of coins, such it's possible to gather 2 coins in each node by performing at most 2 operations. In each operation you can move 1 coin from a node to one of its adjacent neighbors. There is a condition you must follow. If you use your 2 operations on the same coin, then the movement must be done in one direction ,either towards the root or away from the root.</p>
<h1>EXPLANATION:</h1>
<p>There is always a solution for any tree except trees consisting of a single node.</p>
<p>The problem smells like a Dynamic Programming on tree problem. It can be solved with many different recursive functions (with memorization of course). Let's tell some observations which lead us to a simple function.</p>
<p><strong>Observation 1:</strong> We must place one coin in each leaf (nodes without children). Also, either the parent of a leaf, or the second ancestor (parent of the parent) of a leaf must have a coin. For simplicity, let's denote nodes with coins by black nodes and nodes without coins by white nodes.</p>
<p><strong>Observation 2:</strong> Each white node must have at least 2 adjacent (nodes connected directly by one edge) black nodes.</p>
<p>A function that solves this problem efficiently:</p>
<p>$dp[Node][Color][ParentColor][SecAncestorColor]$</p>
<p>This function returns the minimum number of coins we need to construct a valid configuration of the subtree rooted at node $Node$ providing that its color must be $Color$ and its parent is colored $ParentColor$ and its second ancestor (parent of the parent) is colored $SecAncestorColor$. (Please note that we only care about the second's ancestor color when processing leaves).</p>
<p>Processing black nodes is quite easy, it doesn't matter how we color the children of a black node. According to our second observation each white node will have a black node within a distance of 1 edge, so gathering 2 coins would be always possible if our assumption is <strong>satisfied</strong>.</p>
<p>Let's get to white nodes, if the parent is black we must have at least one child colored, otherwise we must have at least 2. It's another <strong>(sub)</strong>-Dynamic Programming problem we should solve for each white node we process. For each child we have 2 choices either to have it black or white (and each choice has its cost) and we want to pick at least two/one black children with minimum total cost.</p>
<p>You can check my implementation for details.</p>
<p>This solution runs in <strong>O(N)</strong></p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><strong>AUTHOR's solution</strong>: Can be found <a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Setter/TWOCOINS.cpp">here</a> <br>
<strong>TESTER's solution</strong>: Can be found <a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Tester/TWOCOINS.cpp">here</a><br>
<strong>EDITORIALIST's solution</strong>: Can be found <a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Editorialist/TWOCOINS.cpp">here</a></p>deadwing97Tue, 18 Jul 2017 10:11:50 +0530https://discuss.codechef.com/questions/105597/twocoins-editorialtree-dptwocoinsjuly17dynamic-programmingeasy-mediumeditorialMULDIG - Editorialhttps://discuss.codechef.com/questions/106138/muldig-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/MULDIG">Practice</a> <br>
<a href="https://www.codechef.com/JULY17/problems/MULDIG">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/errichto">Kamil Debowski</a> <br>
<strong>Primary Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>DIFFICULTY:</h1>
<p>Medium-Hard</p>
<h1>PREREQUISITES:</h1>
<p>None</p>
<h1>PROBLEM:</h1>
<p>Problem is very long to describe here, kindly check contest/practice links.</p>
<h1>Explanation</h1>
<p>In this editorial I will describe the amazing library Kamil was able to build using a very simple function. Having this library coded would make solving the problem a matter of implementation and calling functions, because it allows various solutions to be applicable.</p>
<p>Our function is:</p>
<p>$f(a , b) = (a + b)\%mod \ \ ;\ a \neq 0$</p>
<p>$f(a , b) = (mod-b)\%mod \ \ ;\ a = 0$</p>
<p><strong>Copy Function:</strong> Copies a value $val$ to a cell in our array $tar$</p>
<p>$f(val , 0 , tar)$</p>
<p><strong>Substraction function:</strong> <strong>Sub(a,b) :: a = (a-b)%mod</strong></p>
<p>It's equivalent to performing <strong>f(a,mod-1)</strong> exactly <strong>b</strong> times</p>
<p><strong>Addition function</strong>: <strong>Add(a,b) :: a = (a+b)%mod</strong></p>
<p>It's equivalent to $f(sub(a,b),f(b,b))$</p>
<p>That's because our function f doesn't perform addition when a=0</p>
<p>Let's define:</p>
<p>$fhalf= \lfloor{\frac{mod}{2}} \rfloor$</p>
<p>$chalf=\lceil {\frac{mod}{2}} \rceil$</p>
<p><strong>Decrement function:</strong> <strong>Dec(a) :: a = max(a - 1 , 0)</strong></p>
<p>It's equivalent to $Add( f(a,fhalf) , fhalf)$</p>
<p>That's correct because $f(0,fhalf) = chalf$</p>
<p><strong>Sign Function</strong> returns 1 if the number is greater than zero, or zero otherwise</p>
<p>It's equivalent to:</p>
<p>$Sub( f(a,chalf) , sub(a,chalf) )$</p>
<p><strong>Case a = 0:</strong></p>
<p>$f(a,chalf) = fhalf$ , $sub(a,chalf) = fhalf$ , that means <strong>sign(0) = 0</strong></p>
<p><strong>Case a > 0:</strong></p>
<p>$f(a,chalf) = a-fhalf$ , $sub(a,chalf) = a - chalf$</p>
<p>$sign(a) = a - fhalf - a + chalf = 1$</p>
<p><strong>NOT Function</strong> :: <strong>Not(a) = (opposite of the sign)</strong></p>
<p>$sub(1,sign(a))$</p>
<p><strong>And Function</strong> :: <strong>And(a,b)</strong> returns 1 if both numbers are <strong>greater</strong> than 0</p>
<p>$dec(add(sign(a),sign(b)))$</p>
<p><strong>OR Function</strong> :: <strong>OR(a,b)</strong> returns 1 if at least one number is greater than 0</p>
<p>$Not(And(Not(a),Not(b)))$</p>
<p>You can implement operators < , > using loops. decrementing both numbers by 1 and returning the corresponding boolean value according to the sign at the time one of them is equal to 0. </p>
<p>Now we can implement a program that multiplies two numbers in the same way we do it by our bare hands. We may copy the first digit of the second number along with the first number and multiply our digit with the first number using some extra cells of our memory. After that we may add the result to our answer cells. The same applies to the second digit. Of course we must perform multiplication by repeated addition.</p>
<p>Repeated addition can be easily done by running a loop that terminates when our second multiplied number reaches zero, adding the first number to the answer by each iteration.</p>
<p>Using these functions we are able to perform any arithmetic operation and of course binary operators. Also we can easily make our simulator run into loops and stop it whenever we would like to. Coding this library would make us able to solve the way we would like to.</p>
<p>You can check Kamil's solution if we would like to</p>
<p><strong>AUTHOR's solution</strong>: Can be found <a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Setter/MULDIG.cpp">here</a> </p>deadwing97Sat, 22 Jul 2017 07:03:44 +0530https://discuss.codechef.com/questions/106138/muldig-editorialmuldigeditorialimplementationsimulationjuly17medium-hardAPRPS - Editorialhttps://discuss.codechef.com/questions/106139/aprps-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/APRPS">Practice</a> <br>
<a href="https://www.codechef.com/JULY17/problems/APRPS">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/chemthan">Trung Nguyen</a> <br>
<strong>Primary Tester:</strong> <a href="https://www.codechef.com/users/mgch">Misha Chorniy</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>DIFFICULTY:</h1>
<p>Hard</p>
<h1>PREREQUISITES:</h1>
<p>Advanced Math,FFT,Number Theoretical Transforms</p>
<h1>PROBLEM:</h1>
<p>It is well-known that $\sum_{}^{}\sqrt{a_i}$ where $a_i \in \mathbb{N}$ is a root of some integer-coefficient polynomial. Given n distinct prime numbers. Now, your task is to find not only such polynomial but also the minimal one such that $\sum_{i=1}^{i=n} \sqrt{a_i}$ is a root of this polynomial. When comparing two polynomials, firstly, we consider their degree and then the coefficient of the highest term, and then the second highest term and so on.</p>
<h1>EXPLANATION:</h1>
<h1>Theorem</h1>
<p>Let $x_1,x_2,x_3....x_n$ be <strong>n</strong> distinct square free integers. Then if $a_1,a_2,a_3,....a_n$ are rational numbers such that:</p>
<p>$\sum_{i=1}^{i=n} a_i * \sqrt{x_i} = 0$</p>
<p>Then:</p>
<p>$a_i = 0 \ for\ any\ (1\leq i \leq n)$ You can find the proof <a href="http://kam.mff.cuni.cz/~klazar/tomek_pr.pdf">here</a>.</p>
<p>Assume $f(x)$ is integer-coefficient polynomial with root $\sqrt{x_1} + \sqrt{x_2} + \sqrt{x_3} + ... \sqrt{x_n}$</p>
<p><strong>Lemma 1</strong>:
$f(x)$ is sum of terms, each term is in the form: $K * \sqrt{D}$, where $K$ is an integer, $D$ is free-square integer (product of some primes).</p>
<p><strong>Lemma 2:</strong></p>
<p>Changing any term $+\sqrt{x_i}$ to $-\sqrt{x_i}$ will result in changing sign of some above terms.
Using above theorem, we obtain that all $K$ coefficients in the <strong>Lemma 1</strong> must be 0. </p>
<p>From <strong>Lemma 2</strong>, we see that $f(x)$ will have $2^n$ roots.</p>
<p>All roots are following the form: $\sum_{}^{} sign_i * \sqrt{x_i}$ <strong>AND</strong> $sign_i = -1 \ or\ +1$</p>
<p><strong>Lemma 3</strong>:</p>
<p>The polynomial of degree $2^n$ with $2^n$ above roots is integer-coefficient.</p>
<p>This is easy to see by following recursive formula:</p>
<p><strong>Subtask 1:</strong></p>
<p>Using paper.</p>
<p><strong>Sub task 2:</strong></p>
<p>There are at most $2^n$ free-squre induce from <strong>n</strong> prime. So represent each coefficent in the form of $2^n$ free-square is easy to pass.</p>
<p><strong>Sub task 3:</strong>
.
Let's denote by $f_i(x)$ the sought polynomial which has $\sum_{k=1}^{k=i} \sqrt{x_k}$ as a root. It's clear that:</p>
<p>$f_{i+1}(x) = f_i(x + \sqrt{x_{i+1}}) * f_i(x - \sqrt{x_{i+1}})$ </p>
<p>It is a sought polynomial which has the roots of $f_i(x)$ shifted by $+\sqrt{x_i{+1}}$ and also the roots of $f_i(x)$ shifted by $-\sqrt{x_i{+1}}$. Having $2^{i+1}$ roots.</p>
<p>$f_{i+1}(x) = f_i(x + \sqrt{x_{i+1}}) * f_i(x - \sqrt{x_{i+1}})$ </p>
<p>$f_i(x + \sqrt{x_{i+1}}) = A(x) + \sqrt{x_{i+1}} * B(x)$</p>
<p>$f_i(x - \sqrt{x_{i+1}}) = A(x) - \sqrt{x_{i+1}} * B(x)$</p>
<p>$f_{i+1}(x) = (A(x) + \sqrt{x_{i+1}} * B(x)) * (A(x) - \sqrt{x_{i+1}} * B(x))$ </p>
<p>$f_{i+1}(x) = A^2(x) - x_{i+1} * B^2(x)$</p>
<p>Now will need to expand $f_i(x + \sqrt{x_{i + 1}})$ to $A(x) + \sqrt{x_{i + 1}} * B(x)$.
Then multiply polynomials to get $A^2(x), B^2(x)$.</p>
<p>the naive way O(n^2) easy to get 60 points.</p>
<p>Subtask 4:
Expanding $f(x + \sqrt{x_i})$ to $A(x) + \sqrt{x_i} * B(x)$ by FFT.
To deal with modulo $10^9 + 7$, we can use NTT with three large prime or <strong>Karatsuba</strong> (not intended), and normal FFT with $\sqrt{mod}$ technique. You can see in Author, tester solution</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><strong>AUTHOR's solution</strong>: Can be found <a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Setter/APRPS.cpp">here</a> <br>
<strong>TESTER's solution</strong>: Can be found <a href="https://s3.amazonaws.com/codechef_shared/download/Solutions/JULY17/Tester/APRPS.cpp">here</a> </p>deadwing97Sat, 22 Jul 2017 07:06:14 +0530https://discuss.codechef.com/questions/106139/aprps-editorialhardaprpsfftnttjuly17editorialmathRAINBOWA - Editorialhttps://discuss.codechef.com/questions/107967/rainbowa-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/RAINBOWA">Practice</a> <br>
<a href="https://www.codechef.com/AUG17/problems/RAINBOWA">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/berezin">Dmytro Berezin</a> <br>
<strong>Primary Tester</strong> <a href="https://www.codechef.com/users/prateekg603">Prateek Gupta</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>PROBLEM EXPLANATION</h1>
<p>A rainbow array of <strong>n</strong> elements follows the form </p>
<p><strong>{</strong> <strong>1</strong> (repeated <strong>a<sub>1</sub></strong> times), <strong>2</strong> (<strong>a<sub>2</sub></strong> times), <strong>3</strong> (<strong>a<sub>3</sub></strong> times), <strong>4</strong> (<strong>a<sub>4</sub></strong> times), <strong>5</strong> (<strong>a<sub>5</sub></strong> times), <strong>6</strong> (<strong>a<sub>6</sub></strong> times), <strong>7</strong> (<strong>a<sub>7</sub></strong> times), <strong>6</strong> (<strong>a<sub>6</sub></strong> times), <strong>5</strong> (<strong>a<sub>5</sub></strong> times), <strong>4</strong> (<strong>a<sub>4</sub></strong> times), <strong>3</strong> (<strong>a<sub>3</sub></strong> times), <strong>2</strong> (<strong>a<sub>2</sub></strong> times), <strong>1</strong> (<strong>a<sub>1</sub></strong> times) <strong>}</strong> </p>
<p>$2*(a_1+a_2+a_3+a_4+a_5+a_6)+a_7 = n$</p>
<p>Given an array consisting of <strong>n</strong> elements, check if it's a rainbow array or not.</p>
<h1>DIFFICULTY:</h1>
<p>cakewalk</p>
<h1>PREREQUISITES:</h1>
<p>None</p>
<h1>EXPLANATION:</h1>
<p>This problem is similar to checking if a given string is a palindrome or not. The simplest and most effective way to check if the array is rainbow, is by maintaining 2 pointers one iterating through elements starting from the beginning of our array, and the other one iterating through the elements in the reversed direction.</p>
<p>Both of the first and the last element of the array must be ones. In fact, there must be two blocks consisting of the same number of <strong>consecutive</strong> ones <strong>(1)</strong> one of them located at the beginning of the array, and the other one at the end.</p>
<p>Figuring out the number of consecutive ones at the beginning of our array can be done easily by moving our first pointer forward, and stopping when encountering a number not equal to 1 or reaching the end of our array. We can do the same on the other side by moving our second pointer backwards. After that, we should check that we had processed the same number of <strong>ones</strong> on both sides.</p>
<p>After processing elements equal to <strong>one</strong>, you can observe that we are still solving the same problem (in fact, it's a subproblem now). Both of our pointers must be referring to elements equal to <strong>2</strong>. Moving our pointers is equivalent to dropping elements, so if we consider that we have dropped processed <strong>ones</strong>, there must be two blocks consisting of the same number of <strong>consecutive</strong> twos <strong>(2)</strong> one of them located at the beginning of the array, and the other one at the end. Of course instead of using 2 pointers, maintaining a data structure which supports dropping elements from both ends of the array (Like C++ Deque) does the job perfectly.</p>
<p>After repeating the same procedure for <strong>{1,2,3,4,5,6}</strong> (considering that none of our conditions was violated, in case that happened we can report that our array is not rainbow and break) we would be finishing with a single block consisting <strong>only</strong> of elements equal to seven <strong>7</strong>. Reaching this point confirms that our array is rainbow.</p>
<p>You can check my implementation for better understanding.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><strong>AUTHOR's solution</strong>: Can be found <a href="http://www.codechef.com/download/Solutions/AUG17/Setter/RAINBOWA.cpp">here</a> <br>
<strong>TESTER's solution</strong>: Can be found <a href="http://www.codechef.com/download/Solutions/AUG17/Tester2/RAINBOWA.cpp">here</a><br>
<strong>EDITORIALIST's solution</strong>: Can be found <a href="http://www.codechef.com/download/Solutions/AUG17/Editorialist/RAINBOWA.cpp">here</a></p>deadwing97Fri, 11 Aug 2017 13:32:07 +0530https://discuss.codechef.com/questions/107967/rainbowa-editorialimplementationaug17editorialad-hocrainbowacakewalkGCAC - Editorialhttps://discuss.codechef.com/questions/107968/gcac-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/GCAC">Practice</a> <br>
<a href="https://www.codechef.com/AUG17/problems/GCAC">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/naksh9619">Naksh Arora</a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/prateekg603">Prateek Gupta</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>PROBLEM EXPLANATION</h1>
<p>There are a total of N candidates and M companies. Each candidate has a certain minimum expectation of salary. You will be given N*M numbers, such that for each pair (candidate,company) you will be given a value (0/1) telling if this company accepts this candidate. A company will provide a fixed salary to the candidates it employs (and it's the same for any candidate it employs). Also, a company has an upper bound on the number of candidates it can employ and finally give an offer to.</p>
<p>Each candidate from (1,2,3,...N) (in this order) would call all companies that accepts him, and check which of them still hasn't reached its job offers limit. Among which haven't,he picks the company which provides the maximum offered salary, provided that it is at least his demanded salary. You have to find the number of the candidates that will end up with a job, the total amount of salaries that the candidates will get, and the number of companies that won't be able to employ even a single candidate.</p>
<p><strong>No two companies provide the same salary.</strong></p>
<h1>DIFFICULTY:</h1>
<p>simple</p>
<h1>PREREQUISITES:</h1>
<p>None</p>
<h1>EXPLANATION:</h1>
<p>According to our bolded constraint (which made the problem much simpler) you can observe that any candidate would always have one choice <strong>(only)</strong>, or he may not find a company at all (if all companies that he is interested in working at (and accepting employing him) reached their offers limit).</p>
<p>So turning the instructions written in the problem statement into a code (a straight forward simulation) is pretty enough to solve the problem. Process candidates in order, for each one iterate through all companies and check ones that accept this candidate, provides a salary that satisfies his demand and most importantly still have vacancies. Among these, pick the one with best salary, assign our candidate to this company and decrement its remaining vacancies by one. Calculating required values would be pretty easy. Check my implementation for better understanding.</p>
<p>Solution runs in <strong>O(N*M)</strong></p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><strong>AUTHOR's solution</strong>: Can be found <a href="http://www.codechef.com/download/Solutions/AUG17/Setter/GCAC.cpp">here</a> <br>
<strong>TESTER's solution</strong>: Can be found <a href="http://www.codechef.com/download/Solutions/AUG17/Tester2/GCAC.cpp">here</a> <br>
<strong>ADMIN'S Solutions</strong>: Can be found <a href="http://www.codechef.com/download/Solutions/AUG17/Admin/GCAC.cpp">here</a><br>
<strong>EDITORIALIST's solution</strong>: Can be found <a href="http://www.codechef.com/download/Solutions/AUG17/Editorialist/GCAC.cpp">here</a></p>deadwing97Fri, 11 Aug 2017 13:37:33 +0530https://discuss.codechef.com/questions/107968/gcac-editorialimplementationaug17editorialsimplegcacPALINGAM - Editorialhttps://discuss.codechef.com/questions/107969/palingam-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/PALINGAM">Practice</a> <br>
<a href="https://www.codechef.com/AUG17/problems/PALINGAM">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/dpraveen">Praveen Dhinwa</a> <br>
<strong>Primary Tester:</strong> <a href="https://www.codechef.com/users/prateekg603">Prateek Gupta</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>PROBLEM EXPLANATION</h1>
<p>Two players A,B are playing a game. Player A has a string <strong>s</strong> with him, and player B has string <strong>t</strong> with him (of the same length and may consist of lowercase english letters only). Each player knows the string of the other player. Player A makes the first move and they keep alternating turns.
Players are building another string w which starts empty. In each move, a player removes any single character from his string and inserts this character at any position in <strong>w</strong>. If at any stage of the game, the string <strong>w</strong> is a palindrome and its length is greater than 1, then the player who made the last move wins. If both players strings are empty and w is not a palindrome then player B wins. Find out the winner assuming that both of them are playing optimally.</p>
<h1>DIFFICULTY:</h1>
<p>Easy</p>
<h1>PREREQUISITES:</h1>
<h1>EXPLANATION:</h1>
<p>This problem is solved by breaking this game into few scenarios:</p>
<h1>Scenario 1</h1>
<p>If all of first player's letters are present into the second's string, then the second player wins after his first move (the first player picks any letter and the second appends the same letter to <strong>w</strong> achieving a palindrome of length 2).</p>
<h1>Scenario 2</h1>
<p>So the first player's move must be a unique letter (not present in the second's string). So his string must contain at least one unique letter. It's obvious that the second player must choose a unique letter (not present in the first player's string). Otherwise the first player would just choose the same letter the second player had chosen in his first move achieving a palindrome of length 3, and winning the game after his second move.</p>
<h1>Scenario 3</h1>
<p>In case both of them had at least one unique letter, if the first player had a unique letter occurring at least twice, he would win easily. Picking this letter in his first and third move would result into a palindrome of length 3 (regardless of the second player's move).</p>
<h1>Any Other Scenario</h1>
<p>If none of the above described scenarios is fulfilled, then player B would win for sure, that's because there will be at least 2 unique letters in the string after the second move (and the first player's letter) has no other copy (otherwise scenario 3 is fulfilled). And it's clear that no palindrome can contain 2 unique letters. So the game is in second player's control, he can just postpone placing the other copies (of his first played unique letter) or even place them arbitrarily so no palindrome is formed at any stage (Note that in some scenarios the second player may be able to form a palindrome but it doesn't matter because he is the winner anyway). If no other copies exist then no palindrome ever :D</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><strong>AUTHOR's solution</strong>: Can be found <a href="http://www.codechef.com/download/Solutions/AUG17/Setter/PALINGAM.cpp">here</a> <br>
<strong>TESTER's solution</strong>: Can be found <a href="http://www.codechef.com/download/Solutions/AUG17/Tester2/PALINGAM.cpp">here</a><br>
<strong>EDITORIALIST's solution</strong>: Can be found <a href="http://www.codechef.com/download/Solutions/AUG17/Editorialist/PALINGAM.cpp">here</a></p>deadwing97Fri, 11 Aug 2017 13:43:53 +0530https://discuss.codechef.com/questions/107969/palingam-editorialeditorialad-hocaug17gamepalingameasyCHEFMOVR - Editorialhttps://discuss.codechef.com/questions/107970/chefmovr-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/CHEFMOVR">Practice</a> <br>
<a href="https://www.codechef.com/AUG17/problems/CHEFMOVR">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/berezin">Dmytro Berezin</a> <br>
<strong>Primary Tester:</strong> <a href="https://www.codechef.com/users/prateekg603">Prateek Gupta</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>PROBLEM EXPLANATION</h1>
<p>Given an array consisting of <strong>n</strong> integers, Chef wants to make all elements of this array equal. He can apply the following operation:</p>
<p>Pick 2 numbers </p>
<p><strong>(i,j) :: j = i + D</strong></p>
<p>Decrementing $A_i$ <strong>OR</strong> $A_j$ by <strong>1</strong> and adding <strong>1</strong> to the other element. Please help chef by telling the minimum number of operations he needs to make all elements equal, or tell that such situation is impossible.</p>
<h1>DIFFICULTY:</h1>
<h1>PREREQUISITES:</h1>
<p>simple</p>
<h1>EXPLANATION:</h1>
<p>Applying our operation any number of times would keep the sum of elements in our array the same. (Since we are subtracting one from an arbitrary number and adding it to another one), so the <strong>sum of our numbers must be divisible by n</strong></p>
<p>The final value of each element would be equal to $\frac{sum}{n}$</p>
<p>In any operation chef would choose 2 numbers <strong>(i,j)</strong>:</p>
<p><strong>(i,j) :: j = i + D</strong></p>
<p><strong>j mod D = i mod D</strong></p>
<p>So you can notice that any pair of elements <strong>A<sub>i</sub> , A<sub>j</sub></strong> such that <strong>j mod D ≠ i mod D</strong> are independent from each other. (That's true).</p>
<p>That means that we should group our elements by the remainder of their indexes after dividing by <strong>D</strong>. (And of course) solve each one independently. In fact we will have <strong>D</strong> groups, the <strong>i<sub>th</sub></strong> group (0 ≤ i < D) contains all elements <strong>A<sub>j</sub> (j mod D = i)</strong></p>
<p>Let's tell now about handling each set, applying our operation any number of times would keep the sum of elements in our set the same. So the <strong>sum of elements in each set must be divisible by this set's size</strong> and of course the result of this division must be equal to $\frac{sum}{n}$ , having one set violating this condition would make Chef's mission impossible.</p>
<p>Let's now move to finding the minimum number of operations to fix each set, each set would have 3 kinds of numbers <strong>(numbers > $\frac{sum}{n}$)</strong> and <strong>(numbers < $\frac{sum}{n}$)</strong> and of course <strong>(numbers equal to $\frac{sum}{n}$) -that we can omit-</strong>.</p>
<p>Let's process numbers of each set in the same order of the array (from left to right) and separate them into 2 groups as described (first two types since we can omit the third). Maintaining 2 pointers each one iterating on the elements of one group, would just do the job, because if our processed element is less than $\frac{sum}{n}$ then optimal choice would be picking this number along with the closest number bigger than $\frac{sum}{n}$ to the right of it (the same when the opposite happens), and we should add the distance between them for each increment\decrement operation we apply (because we are using elements between them as mediators). After each iteration, one of the numbers referred to by out pointers would reach the desired value, so we move the pointer on. Practically, this part can be done in simpler way (like author's solution), but this is the detailed explanation. The implementation of this editorial can be found in my code.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><strong>AUTHOR's solution</strong>: Can be found <a href="http://www.codechef.com/download/Solutions/AUG17/Setter/CHEFMOVR.cpp">here</a> <br>
<strong>TESTER's solution</strong>: Can be found <a href="http://www.codechef.com/download/Solutions/AUG17/Tester2/CHEFMOVR.cpp">here</a><br>
<strong>EDITORIALIST's solution</strong>: Can be found <a href="http://www.codechef.com/download/Solutions/AUG17/Editorialist/CHEFMOVR.cpp">here</a></p>deadwing97Fri, 11 Aug 2017 14:17:03 +0530https://discuss.codechef.com/questions/107970/chefmovr-editorialad-hocaug17chefmovreditorialimplementationSTRINGRA - Editorialhttps://discuss.codechef.com/questions/108043/stringra-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/STRINGRA">Practice</a> <br>
<a href="https://www.codechef.com/AUG17/problems/STRINGRA">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/admin3">Arjun Arul</a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/kingofnumbers">Hasan Jaddouh</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>PROBLEM EXPLANATION</h1>
<p>Given an array consisting of <strong>N</strong> integers. Let's construct a directed acyclic graph of <strong>N+1</strong> nodes. If there is a subsequence <strong>S<sub>1</sub></strong> ending at position <strong>U</strong> which cannot be formed with all elements to the left of <strong>A<sub>U</sub></strong>, let's denote by <strong>S<sub>2</sub></strong> the subsequence resulting from appending <strong>A<sub>V</sub></strong> to <strong>S<sub>1</sub></strong> <strong>(U < V)</strong></p>
<p>An edge is added from node <strong>U</strong> to node <strong>V</strong> if and only if the subsequence <strong>S<sub>2</sub></strong> cannot be formed with all elements to the left of <strong>A<sub>V</sub></strong>. You are given a DAG with <strong>N+1</strong> nodes and <strong>M</strong> edges, you are asked to restore the lexicographically minimum array which this graph corresponds to or state that data is inconsistent. </p>
<p>Please note that node 0 represents the empty subsequence.</p>
<p><strong>(1 ≤ N,M ≤ 10<sup>5</sup>)</strong></p>
<h1>DIFFICULTY:</h1>
<p>easy-medium</p>
<h1>PREREQUISITES:</h1>
<p>Sortings</p>
<h1>EXPLANATION:</h1>
<h1>Observation 1:</h1>
<p>Let's denote by $L_i$ the adjacency list of the $i$-th node.
Note that the out degree of node $0$ (size of $L_0$) is equal to the number of distinct elements in our array (let's denote it by $K$). Because each position that presents in this list refers to the first occurrence of a <strong>(new)</strong> number since an edge from node 0 to other node corresponds to a subsequence of size 1.</p>
<h1>Observation 2:</h1>
<p>Consider an arbitrary position $P$, you can note that the subsequence containing all elements $A_i$ $(1 \leq i \leq P)$ cannot be formed without considering all elements till $A_P$ let's denote this subsequence by $S_1$. If there is an edge $(P \rightarrow Q)$, it means that $Q$ must be the first occurrence (to the right of $P$) of one of our numbers (Why?), because if there was an earlier occurrence $R (R < Q)$, then the subsequence $S_1 + A_Q$ (+ denotes concatenation) could be formed with the first $R$ elements, and that means an edge $(P \rightarrow R)$ must exist and the other edge $(P \rightarrow Q)$ mustn't <strong>(contradiction)</strong>. </p>
<h1>Observation 3:</h1>
<p>Let's consider the list $L_{P}$ and the list $L_{P - 1}$. The size of $L_{P}$ must be equal or less by one than the size of $L_{P - 1}$. Let's think about earliest occurrences of our $K$ numbers when looking to the right of $A_{P-1}$, you can see that all of them will remain the same (when looking to the right of $A_P$), <strong>EXCEPT</strong> for 1 element which is $A_P$. $P$ is present in $L_{P - 1}$ (clearly it's the earliest occurrence of $A_P$), but in $L_{P}$ it will be replaced by the first occurrence to the right of $P$ (so lists sizes will stay the same), or there may be no next occurrence (if $P$ was the last occurrence of $A_P$) then size of $L_{P}$ would be less by 1.</p>
<p>Let's assign numbers from 1 to K to all positions present in <strong>L<sub>0</sub></strong> (in increasing order of position). After that let's consider each 2 consecutive lists $L_{P}$, $L_{P - 1}$. All elements of $L_{P - 1}$ must be present in $L_{P}$ except for one element for sure which is equal to $P$. All elements of $L_{P}$ must be present in $L_{P - 1}$ except one number $X$ which is equal to $A_P$, so we should assign $A_X = A_P$ (if size of $L_{P}$ is less by one than the size of $L_{P-1}$ then we don't need to look for it.</p>
<h1>Corner Case</h1>
<p>While processing elements from left to right, if we come to an element which hasn't been processed then our data is inconsistent. Any position $P$ must exist in $L_{P-1}$ and reaching an unassigned number means that it's not existed in $L_{P-1}$ otherwise we would have assigned it to a value.</p>
<p>Solution runs in $O(M log M)$</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><strong>AUTHOR's solution</strong>: Can be found <a href="http://www.codechef.com/download/Solutions/AUG17/Setter/STRINGRA.cpp">here</a> <br>
<strong>TESTER's solution</strong>: Can be found <a href="http://www.codechef.com/download/Solutions/AUG17/Tester1/STRINGRA.cpp">here</a><br>
<strong>EDITORIALIST's solution</strong>: Can be found <a href="http://www.codechef.com/download/Solutions/AUG17/Editorialist/STRINGRA.cpp">here</a></p>deadwing97Mon, 14 Aug 2017 08:35:21 +0530https://discuss.codechef.com/questions/108043/stringra-editorialsortingad-hocgreedyaug17easy-mediumeditorialstringraCHEFFA - Editorialhttps://discuss.codechef.com/questions/108044/cheffa-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/CHEFFA">Practice</a> <br>
<a href="https://www.codechef.com/AUG17/problems/CHEFFA">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/berezin">Dmytro Berezin</a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/prateekg603">Prateek Gupta</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>PROBLEM EXPLANATION</h1>
<p>Chef has an array consisting of <strong>N</strong> elements. Chef may pick any <strong>2 adjacent</strong> elements which are both positive, decrement each of them by 1, and increment the next one (in front of them) by 1. (If those elements were the last two elements he appends 1 to the end of the array). Chef wants you to count the number of <strong>different</strong> arrays that he is able to reach via any sequence of moves. Since answer is large calculate it modulo <strong>10<sup>9</sup>+7</strong></p>
<h1>DIFFICULTY:</h1>
<p>easy-medium</p>
<h1>PREREQUISITES:</h1>
<p>Dynamic Programming</p>
<h1>EXPLANATION:</h1>
<p>According to the given constraints, chef won't be able to construct an array having more than <strong>60</strong> elements (this can be proved by paper or maybe be writing a greedy checker).</p>
<p>Observe that two different sequences of moves (without considering the order of the moves) will lead to different resulting arrays. That's because there will be at least one element which was variated differently between the two sequences of operations (You can prove that if you apply operations in order from left to right).</p>
<p>This problem is a Dynamic Programming exercise, let's define a function that solves this problem</p>
<p><strong>dp[pos][deltapos][deltanxt]</strong></p>
<p>which denotes the number of different arrays that could be obtained by performing operations on the subarray starting from the element having index <strong><em>pos</em></strong> assuming that this element was changed by <strong><em>deltapos</em></strong> and the next element to the right was changed by <strong><em>deltanxt</em></strong>.</p>
<p><strong>(1 ≤ pos ≤ 60)</strong></p>
<p><strong>(-50 ≤ deltapos,deltanxt ≤ 50)</strong></p>
<p>The base case of our function would be </p>
<p><strong>dp[61][0][0] = 1</strong></p>
<p>The recurrence formula of our function is kind of easy to figure out, we should try all different ways of changing the element at the index <strong><em>pos</em></strong>, and it's clear that we have <strong>min(arr<sub>pos</sub>+deltapos , arr<sub>nxt</sub>+deltanxt) + 1</strong> different ways (That's because all elements must be positive during any move and we are decrementing both of <strong>arr<sub>pos</sub> , arr<sub>pos+1</sub></strong>). </p>
<p>For each number of operations <strong>op</strong> <strong>(0 ≤ op ≤ min(arr<sub>pos</sub>+deltapos , arr<sub>nxt</sub>+deltanxt) + 1)</strong>, performing any of them would lead us to a different solution from all the others.</p>
<p><strong>For each (0 ≤ op ≤ min(arr<sub>pos</sub>+deltapos , arr<sub>nxt</sub>+deltanxt) + 1)</strong> </p>
<p> <strong>dp[pos][deltapos][deltanxt] += dp[pos+1][deltanxt-op][op]</strong></p>
<p>Performing <strong><em>op</em></strong> would substract <strong><em>op</em></strong> from the next element and add <strong><em>op</em></strong> to the element after the next and our current element won't be affected in future operations, so we may discard it from the state.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><strong>AUTHOR's solution</strong>: Can be found <a href="http://www.codechef.com/download/Solutions/AUG17/Setter/CHEFFA.cpp">here</a> <br>
<strong>TESTER's solution</strong>: Can be found <a href="http://www.codechef.com/download/Solutions/AUG17/Tester2/CHEFFA.cpp">here</a><br>
<strong>EDITORIALIST's solution</strong>: Can be found <a href="http://www.codechef.com/download/Solutions/AUG17/Editorialist/CHEFFA.cpp">here</a></p>deadwing97Mon, 14 Aug 2017 08:59:44 +0530https://discuss.codechef.com/questions/108044/cheffa-editorialdynamic-programmingcheffaaug17editorialeasy-mediumHILLJUMP - Editorialhttps://discuss.codechef.com/questions/108216/hilljump-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/HILLJUMP">Practice</a> <br>
<a href="https://www.codechef.com/AUG17/problems/HILLJUMP">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/kingofnumbers">Hasan Jaddouh</a> <br>
<strong>Primary Tester:</strong> <a href="https://www.codechef.com/users/prateekg603">Prateek Gupta</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>PROBLEM EXPLANATION</h1>
<p>There are <strong>N</strong> hills located on a straight line. The height of the <strong>i<sup>th</sup></strong> one is denoted by <strong>H<sub>i</sub></strong>. A participant standing at the top of the <strong>i<sup>th</sup></strong> hill jumps to the nearest hill to the right which is strictly higher than the one he is standing on. If the nearest one is further than 100 hills away, he doesn't move anywhere.</p>
<p>Giving Q queries of 2 types:</p>
<p>The first type is given by <strong>(P,K)</strong> , a participant standing on the <strong>P<sup>th</sup></strong> hill is willing to perform K successive moves, what hill he will be ending at?</p>
<p>The second type is given by <strong>(L,R,X)</strong>, for each hill between the <strong>L<sup>th</sup></strong> one and the <strong>R<sup>th</sup></strong> one (inclusive) should be increased by X (it may be negative).</p>
<h1>DIFFICULTY:</h1>
<p>medium</p>
<h1>PREREQUISITES:</h1>
<p>Complexity Analysis, Sqrt decomposition</p>
<h1>EXPLANATION:</h1>
<p>Let's define an array <strong>nxt[N]</strong> where <strong>nxt<sub>i</sub></strong> denotes the next hill the participant standing at the <strong>i<sup>th</sup></strong> hill is going to jump to (or <strong>nxt<sub>i</sub>=i</strong> if he cannot jump to any other hill).</p>
<p>Let's break our hills into blocks, each block consisting of exactly $S=\sqrt{n}$ hills.
As you can guess, keeping only the next hill we would jump to from each one, is not really effective. That's because jumping hills one by one will lead us to at least <strong>O(Q * K)</strong> solution which exceeds the time limit indeed. Maintaining a sparse table is not a really good idea also, because modifying an element in a sparse table may lead you modifying the whole table.</p>
<p>Let's make something similar to sparse table, Let's define a table <strong>F[N]</strong>. For the <strong>i<sup>th</sup></strong> hill let <strong>F<sub>i</sub></strong> denotes the furthest hill <strong>(which is located in the same bucket)</strong> that we can reach via successive jumps starting from the <strong>i<sup>th</sup></strong> hill (and how many jumps we need to reach it).</p>
<p>Assuming both of our tables <strong>F[],nxt[]</strong> are fixed, then answering queries of the first type would be quite easy. Let's repeatedly jump to the last hill in the current bucket as long as we are not exceeding the remaining jumps, after that moving 1 bucket forward via <strong>nxt[]</strong> table. So any number of jumps would be decomposed into at most $\sqrt{n}$ mass jumps. At a point if a bucket was longer to finish than the remaining jumps, let's just find our destination by processing it linearly. So the first query is answered in $O(\sqrt{n})$</p>
<p>Let's discuss modifying our arrays.</p>
<p>Regarding modifying heights, this is a naive application of sqrt decomposition which can be done in $O(\sqrt{n})$, by updating blocks which were included partially in the query in a linear search. Regarding blocks that were completely included into the query we may increment the variable denoting the sum of increments applied to this bucket (each bucket should have a variable).</p>
<h1>Observations:</h1>
<p>For each <strong>i</strong> such that <strong>(i > R) :: nxt<sub>i</sub></strong> will stay the same. </p>
<p>It's obvious because all participants are jumping to the right. Starting from the <strong>(R+1)<sup>th</sup></strong> hill, no hill will be changed.</p>
<p>For each <strong>i</strong> such that <strong>(i < L-100) :: nxt<sub>i</sub></strong> will stay the same, that's because a participant cannot skip more than 100 hills, so for each <strong>i</strong> in the previous range, <strong>(i+100 < L</strong>), so <strong>no</strong> participant would be allowed to jump to a hill that is modified through our query.</p>
<p>Consider the <strong>i<sup>th</sup></strong> hill, if <strong>nxt<sub>i</sub>=j</strong> and we apply the <strong>QUERY(L,R,X)</strong> for any <strong>(L ≤ i AND R ≥ j)</strong> then the value of <strong>nxt<sub>i</sub></strong> won't change, that's because the <strong>j<sup>th</sup></strong> hill is the closest strictly higher hill (to the <strong>i<sup>th</sup></strong> one), and applying the same query to all hills between won't change the relative order between any pair of them.</p>
<p>For each <strong>i</strong> such that <strong>(R-100 < i ≤ R) :: nxt<sub>i</sub></strong> will be modified and needs to be calculated again. </p>
<p>For each <strong>i</strong> such that <strong>(L-100 ≤ i < L) :: nxt<sub>i</sub></strong> will be modified and needs to be calculated again. </p>
<p>As a conclusion, you can see that the <strong>nxt</strong> value of around 200 hills will be changed. We can process this in nearly O(400) by maintaining a stack. Regarding our table <strong>F</strong> modification, we should process each bucket that contains at least one hill which has its nxt variable modified. We should process each bucket linearly from right to left and maintain a stack during that. All modified buckets should have its data refreshed. Modification query can be done in $O(400 + \sqrt{n})$</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><strong>AUTHOR's solution</strong>: Can be found <a href="http://www.codechef.com/download/Solutions/AUG17/Setter/HILLJUMP.cpp">here</a> <br>
<strong>TESTER's solution</strong>: Can be found <a href="http://www.codechef.com/download/Solutions/AUG17/Tester2/HILLJUMP.cpp">here</a> </p>deadwing97Fri, 18 Aug 2017 06:55:04 +0530https://discuss.codechef.com/questions/108216/hilljump-editorialmediumaug17sqrtbruteforceeditorialhilljumpWALKBT - Editorialhttps://discuss.codechef.com/questions/108219/walkbt-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/WALKBT">Practice</a> <br>
<a href="https://www.codechef.com/AUG17/problems/WALKBT">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/altruist_">Denis</a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>PROBLEM</h1>
<p>Given a full binary tree with height <strong>n</strong>, any binary number made up of <strong>n</strong> bits corresponds to a path in this tree (leading zeros are added if necessary). You start at the root and take each bit a 0 corresponds to left move, and a 1 corresponds to a right move. So each number represents a path that visits a chain of nodes. At the beginning you will have a starting given number <strong>X</strong>. </p>
<p>You will be asked queries of 2 types:</p>
<p>The first type is to increase the value of X by a given value V.</p>
<p>For queries of the second type, you must report that for all values that X was set to during our queries (consider the corresponding path to each single X of them), how many nodes in our binary tree was visited at least once <strong>(modulo 10<sup>9</sup>+7)</strong></p>
<h1>DIFFICULTY</h1>
<p>hard</p>
<h1>EXPLANATION</h1>
<p>An easier version of this problem would be by providing input data such that at <strong>no time</strong> the number representing our path is equal to or bigger than <strong>2<sup>n</sup></strong> (no modulo). According to this constraint, all numbers would be given in increasing order (because each one of them is a result of adding an integer value to the previous one and numbers are less than <strong>2<sup>n</sup></strong>). If our previous number was <strong>X</strong> and it turned to <strong>Y</strong> after performing the last query; Well, we have visited <strong>n-LCP(X,Y)</strong> new nodes. <strong>LCP(X,Y)</strong> is the longest common prefix of the binary representations of <strong>X</strong> and <strong>Y</strong>. (It's easy to prove by yourself).</p>
<p>The idea behind solving this problem is really tricky. Actually, you would think for the first while that storing all integer numbers we have processed while reading the input is impossible (due to huge constraints). Well, think again.</p>
<p>Well, let's check what happens to a number when we add <strong>2<sup>x</sup></strong> to this number. (Assume that bits are ordered from left to right, the most significant bit is the leftmost). We would look to the closest zero to the left of the <strong>x<sup>th</sup></strong> bit (including itself) and flip all bits between (including these 2 bits). If there's no zero to the left (then we just flip all ones starting from the leftmost bit and finishing at the <strong>x<sup>th</sup></strong>, and the modulo cancels the leading one that should appear).</p>
<p>Let's tell how can we store such all of these numbers, let's build a segment tree for our first number (which is given in the input). Now flipping a consecutive segment of bits in this number can be done using a segment tree, so how can we store our new number without consuming a linear block of memory. Well, we need a persistent data structure, all information about persistence can be found in <a href="https://discuss.codechef.com/questions/101647/persistence-made-simple-tutorial">this blog</a>. So each number consumes only <strong>(log N)</strong> memory. Our segment tree must support lazy propagation so that each flip query runs in <strong>O(log N)</strong>.</p>
<p>So we will keep our numbers into a balanced BST (C++ STL set would just do the job). After inserting a new number into an ordered set, calculating the new answer is not that hard.</p>
<p>Consider that our number is denoted by <strong>X</strong></p>
<p>The strictly larger number is denoted by <strong>nxt</strong></p>
<p>The strictly smaller number is denoted by <strong>prev</strong></p>
<p>Our current answer is denoted by <strong>A</strong></p>
<p>$$NewAnswer = A + (n-LCP(prev,X)) + (n-LCP(X,nxt)) - (n-LCP(prev,nxt))$$</p>
<p>We have subtracted the last term because (prev,nxt) are no longer successive numbers in our set.</p>
<p>The last part of our problem is implementing the LCP function, which is nearly the same as implementing the operator <strong><</strong> which our set sorts numbers according to. We have concluded that each number needs only additional <strong>log N</strong> memory to be stored (and we can have full feedback about this number and perform queries on its sub-segments). Comparing 2 numbers is not that hard, each node in the segment tree of any of them is responsible for storing specific data about the bits covered by this node. Maintaining a hash value for each sub-segment of our numbers (my hash was to store the sum of values of bits in each interval modulo 2 big primes instead of normal hashing and worked fine). So when we compare 2 numbers, we are kind of doing a binary search for the first mismatch between these two numbers. At the first step while we are processing both roots of our segment trees, we would either step to the right child to find the first mismatch and adding the whole left part as a part of the LCP (if both left children hashes were identical) or look for the mismatch in the left part (so after the first step eliminating half of the bits), continuing using the same approach by going left or right according to the position of the mismatch (similar to binary search in a binary tree) would end us with the first mismatched position in <strong>log n</strong> steps. Turning the LCP to an operator is quite easy, just look for the first mismatched bit between our numbers and report according to which is smaller than the other.</p>
<p>The most important detail we should take care of while implementing is that persistence means creating new nodes whenever we update a node. For lazy propagation, we are postponing some updates to parts of the tree so we can do them later while going down, well pushing old updates to deeper nodes in our tree obligates us to create new versions (the same situation holds when we use comparator/operator or the LCP function). Anyway, this problem is a really cool exercise if you haven't tried lazy propagation with persistent data structure before.</p>
<p>Solution runs in $O(Q*log^2 (n))$</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><strong>AUTHOR's solution</strong>: Can be found <a href="http://www.codechef.com/download/Solutions/AUG17/Setter/WALKBT.cpp">here</a> <br>
<strong>TESTER/EDITORIALIST's solution</strong>: Can be found <a href="http://www.codechef.com/download/Solutions/AUG17/Editorialist/WALKBT.cpp">here</a></p>deadwing97Fri, 18 Aug 2017 08:10:32 +0530https://discuss.codechef.com/questions/108219/walkbt-editorialaug17hardlazypropagationsegment-treedata-structureeditorialwalkbtpersistencePROBSET Editorialhttps://discuss.codechef.com/questions/134390/probset-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/PROBSET">Practice</a> <br>
<a href="https://www.codechef.com/LTIME63A/problems/PROBSET">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/kingofnumbers">Hasan Jaddouh</a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>PROBLEM</h1>
<p>Chef wrote a problem for his contest. He prepared the test-set. Initially he has solutions for his problem (some correct and some incorrect solutions). For each solution he knows the judge verdict (correct/incorrect) and also the feedback (which cases it passed and which it failed).
You need to help him decide the state of his test-set.
A test-set is invalid if some correct solution fails.
A test-set is weak if it's valid but some incorrect solution passes all the tests.
A test-set is fine if it's not weak and valid.</p>
<h1>DIFFICULTY</h1>
<p>Cakewalk</p>
<h1>EXPLANATION</h1>
<p>This is a straightforward implementation problem where you need to implement what's written in the problem statement.
Read the information given to you, (each solution and its verdict). Count the number of zeroes (failed tests) and ones (passed tests) from each solution feedback. After that you can decide the state of the test-set by checking each the conditions stated above.
It's highly recommended to check the implementation in the solutions below if you have any problems.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p><strong>AUTHOR's solution</strong>: Can be found [here][] <br>
<strong>TESTER/EDITORIALIST's solution</strong>: Can be found [here][]</p>deadwing97Sun, 26 Aug 2018 06:57:39 +0530https://discuss.codechef.com/questions/134390/probset-editorialimplementationltime63EID Editorialhttps://discuss.codechef.com/questions/134491/eid-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/EID">Practice</a> <br>
<a href="https://www.codechef.com/LTIME63A/problems/EID">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/kingofnumbers">Hasan Jaddouh</a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>PROBLEM</h1>
<p>Chef has <strong>N</strong> coins. Each coin has a value. Chef has 2 children whom he will give 1 coin to each. He wants the difference between this two coins to be minimum possible. You need to help Chef and check what's the minimum possible difference.</p>
<h1>DIFFICULTY</h1>
<p>Easy</p>
<h1>EXPLANATION</h1>
<p>If you suppose that you are giving 1 coin to one of the children. To make the difference minimum as possible you need to give the other child the smallest coin which has a bigger value than the first, or the biggest coin which has a smaller value. (Of course there maybe 2 coins with the same value then the answer is zero).</p>
<p>Sort the coins according to their values, and check the difference between every 2 consecutive coins in the sorted array. To fit into the time limit you need to use a fast sorting algorithm (Quicksort , MergeSort). You can also use built-in sort functions in some languages (C++,Java...).</p>
<p>Complexity : <strong>O(N log N)</strong></p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME63/setter/EID.cpp">here</a>.</p>
<p>Tester's/Editorialist's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME63/tester/EID.cpp">here</a>.</p>deadwing97Mon, 27 Aug 2018 05:21:50 +0530https://discuss.codechef.com/questions/134491/eid-editorialsortingltime63greedyJAGAM Editorialhttps://discuss.codechef.com/questions/134492/jagam-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/JAGAM">Practice</a> <br>
<a href="https://www.codechef.com/LTIME63A/problems/JAGAM">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/allllekssssa">Aleksa Plavsic</a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>PROBLEM</h1>
<p>Vanja and Miksi are playing a game on <strong>N</strong> integer numbers. There is a counter <strong>S</strong> which is equal to <strong>0</strong> at the beginning. At each turn, each player picks a number from the array and either subtract it or add it to <strong>S</strong>. You are given also 2 numbers <strong>Z1, Z2</strong>. Whenever the counter is equal to one of them the player who played the last move wins. At least one turn should be played.</p>
<p>Assuming both players are playing optimally you have to determine the winner. In some cases, none of the players can win the game and if they are playing optimally it may last for more than <strong>10<sup>10</sup></strong> turns. In such case, you need to tell that the game ends in a tie. Vanja starts the game.</p>
<h1>DIFFICULTY</h1>
<p>EASY </p>
<h1>EXPLANATION</h1>
<p>If our array contains any of these values <strong>{Z1, Z2, -Z1, -Z2}</strong>, then the first player can win by 1 move.</p>
<p>Let's introduce the term dead end. Whenever a player has his turn and he is not able to win in 1 move and no matter what number he chooses the other player can pick a number and make <strong>S</strong> equal to <strong>Z1</strong> or <strong>Z2</strong>, then our player is in a dead end.</p>
<p>We need to check if Vanja's first move is a dead end. In case it's, then Miksi is the winner. Otherwise, we are sure that the game will last for more than 2 turns.</p>
<p>In such case (more than 2 rounds), we can prove that the game ends in a tie. No matter which player is taking the turn (since each player knows the numbers given and <strong>Z1, Z2</strong>), he can determine whether he is in a dead end or not. In case he is, he can just play exactly the opposite of the move the last player did and avoid losing the game (and since the previous player couldn't win at his previous turn, the game lasts forever).</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME63/setter/JAGAM.cpp">here</a>.</p>
<p>Tester's/Editorialist's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME63/tester/JAGAM.cpp">here</a>.</p>deadwing97Mon, 27 Aug 2018 05:38:08 +0530https://discuss.codechef.com/questions/134492/jagam-editorialad-hocgameltime63GHMC Editorialhttps://discuss.codechef.com/questions/134608/ghmc-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/PROBSET">Practice</a> <br>
<a href="https://www.codechef.com/LTIME63A/problems/PROBSET">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/allllekssssa">Aleksa Plavsic</a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>PROBLEM</h1>
<p>Professor Gukiz has <strong>N</strong> students number <strong>1</strong> through <strong>N</strong>. Let's denote the number of candies given to the <strong>i-th</strong> student by <strong>P<sub>i</sub></strong>. As GukiZ has a lot of students, he does not remember all the exact numbers of candies he gave to the students. He only remembers the following properties of the sequence <strong>P</strong>.</p>
<ul>
<li>The numbers of candies given to each of the first <strong>K</strong> students <strong>P<sub>1</sub>, P<sub>2</sub> ... P<sub>K</sub></strong> are known exactly.</li>
<li>All elements of the sequence <strong>P</strong> are distinct and positive.</li>
<li>GukiZ didn't give more than <strong>X</strong> candies to any student (the maximum value in the sequence <strong>P</strong> is not greater than x).</li>
<li>For each student <strong>i</strong> , there is at least one other student <strong>j</strong> such that <strong>| P<sub>i</sub> − P<sub>j</sub> | ≤ D</strong>.</li>
<li>The professor gave out the biggest possible total number of candies. The sum of elements of sequence <strong>P</strong> is the maximum possible.</li>
</ul>
<p>Given the </p>
<h1>DIFFICULTY</h1>
<p>Easy</p>
<h1>EXPLANATION</h1>
<p>Let's read the numbers remembered by GukiZ and sort them in increasing order. Let's start with the smallest number in the array. Let's suppose that for each number given the forth condition holds. That means that we can add numbers greedily starting from maximum possible value (and ignoring numbers given so we don't add them twice).</p>
<p>Let's suppose that this condition isn't satisfied for some numbers. That means we need to add at least one number (maybe more) so each number has another one in the set with difference no more than <strong>D</strong>. The optimal approach is to add the biggest possible numbers. So we should start from the smallest given number and check the number immediately after it, if the difference is no more than <strong>D</strong> then we can include them both. We apply the same operation for each number afterwards, checking the immediately previous and the immediately next number. If at least one of them has difference no more than <strong>D</strong> we don't need to add anything. </p>
<p>If we had a situation where there's a number <strong>A</strong> with no match, the optimal situation is to add <strong>A+D</strong> to our set (we added the biggest value that satisifies the condition and also covers as many as possible from the upcoming numbers). We continue with this operation till we finish the array.</p>
<p>A case that we should be careful about, is that we have a number <strong>A</strong> with no match (again by match we mean such <strong>B</strong> that <strong>|A - B| <= D</strong>) and we can't add <strong>A+D</strong> because it exceeds the maximum. We just add the maximum possible number <strong>X</strong>. There is a case where our number <strong>A=X</strong> we just add <strong>X-1</strong>.</p>
<p>Uptill now , we completed the list of our number such that each number has a match. If the number of needed numbers insertions is less than <strong>N-K</strong> then our answer is <strong>-1</strong> for sure.</p>
<p>Now, we need to complete our set till it has exactly <strong>N</strong> numbers. We need only to handle the case which we have only 1 number remaining. Then we should add a number that has a match within the set we completed. In this case let's say <strong>MX = the maximum number in our array</strong>. start from <strong>min(X , MX + D)</strong> in decreasing order, and find the maximum number that doesn't exist in our array.</p>
<p>In cases we have more than 1 number to add. We can start adding values from <strong>X</strong>. Let's add <strong>X</strong> to our set. After that, let's look at our set. By simple observation, we can see that we must start from last 2 biggest numbers, and add all numbers between them. After that we skip to 2nd biggest and 3rd biggest and add all numbers between them and so on, until we complete our set.</p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME63/setter/GHMC.cpp">here</a>.</p>
<p>Tester's/Editorialist's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME63/tester/GHMC.cpp">here</a>.</p>deadwing97Wed, 29 Aug 2018 19:31:44 +0530https://discuss.codechef.com/questions/134608/ghmc-editorialltime63greedyXTGR Editorialhttps://discuss.codechef.com/questions/134626/xtgr-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/XTGR">Practice</a> <br>
<a href="https://www.codechef.com/LTIME63A/problems/XTGR">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/allllekssssa">Aleksa Plavsic</a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>PROBLEM</h1>
<p>You are given two integer sequences <strong>S<sub>1</sub>, S<sub>2</sub>, S<sub>3</sub>...S<sub>N</sub></strong>, and <strong>T<sub>1</sub>, T<sub>2</sub>, T<sub>3</sub>...T<sub>M</sub></strong> and an integer <strong>X</strong>.</p>
<p>You are allowed to perform the following operation any number of times:</p>
<p>Choose an element of <strong>S</strong> and an element of <strong>T</strong> (let's denote them by <strong>S<sub>i</sub></strong> and <strong>T<sub>j</sub></strong> respectively), then decrease both <strong>S<sub>i</sub></strong> and <strong>T<sub>j</sub></strong> by <strong>X</strong>, i.e. replace <strong>S<sub>i</sub></strong> by <strong>S<sub>i</sub>-X</strong> and <strong>T<sub>j</sub>-X</strong>.</p>
<p>Let's denote the minimum and maximum value in the sequence <strong>S</strong> after performing the chosen operations (possibly none) by <strong>minS</strong> and <strong>maxS</strong> respectively. Similarly, let's denote the minimum and maximum value in <strong>T</strong> after performing the chosen operations by <strong>minT</strong> and <strong>maxT</strong> respectively. The goal is minimizing the expression <strong>(maxS+maxT)−(minS+minT)</strong>. Compute the minimum value of this expression.</p>
<p>PREREQUISTES:</p>
<p>Basic Number Theory</p>
<h1>CONSTRAINTS</h1>
<p><strong>N,M <= 5*10<sup>5</sup></strong></p>
<p><strong>All other values don't exceed 10<sup>9</sup></strong>.</p>
<h1>DIFFICULTY</h1>
<p>Medium</p>
<h1>EXPLANATION</h1>
<p>A very important observation:</p>
<p>The answer is always no more than <strong>2*X</strong>. Let's try first to make all the values of one array in the range <strong>[0,X-1]</strong>.</p>
<p>Let's introduce:</p>
<p>$sum_1 = \sum_{i = 1}^{N} \lfloor \frac{A_i}{X} \rfloor$</p>
<p>$sum_2 = \sum_{i = 1}^{M} \lfloor \frac{A_i}{X} \rfloor$</p>
<p>For simplicity let's assume that $sum2 > sum1$. We need to apply this operation <strong>sum1</strong> times to the first array to make all values in the range <strong>[0..X-1]</strong>. Since <strong>sum2 > sum1</strong> then we can pick <strong>sum1</strong> pairs from both arrays and apply the operation.</p>
<p>The second array won't be in the range <strong>[0...X-1]</strong> necessarily. We need to apply a few more <strong>sum2-sum1</strong> operations to transform all numbers into that interval. Actually, we can do that, by picking each time a number from the second array with the maximum number in the first array (doing this operation <strong>sum2 - sum1</strong> times). You can see that the difference between the maximum number and the minimum in the first won't ever exceed <strong>X</strong> (Try to prove it, it's easy).</p>
<p>Now we have the first array with <strong>maximum - minimum <= X</strong> and the second array has all numbers in the range <strong>[0...X-1]</strong>.</p>
<p>By observing the problem a little bit, we can see that the optimal solution is to apply the same operation $N*M$ times always by picking the maximum number in the first array and the maximum number in the second array. This will be enough to solve 2 subtasks. (because it's the only way to keep the difference in each array no more than <strong>X</strong>) and we can prove that there is no optimal scenario where the difference between the max and the min in one of the arrays is more than <strong>X</strong>. It's also obvious that $N*M$ operations are enough because it's the number of all rotations of first multiplied by the number of all rotations of the second.</p>
<p>If <strong>GCD(N,M) = 1</strong>, we can prove that for any pair of indices (the first index is from the first array and the second index from the second array), we can prove that we can fix them as the starting elements of our arrays by applying this operation a finite number of times <strong>(because GCD(N,M)=1)</strong>. (Try the proof yourself).</p>
<p>Then the answer can be calculated easily. Let's take the difference between every 2 consecutive elements in both arrays (take into account that last and first element are equal), our answer would be the sum of the minimum difference in the first + the minimum difference in the second. </p>
<p>If <strong>GCD(N,M)!=1</strong> . We must group our numbers by their modulo to <strong>G (by G we mean GCD(N,M))</strong>. It would be possible also to fix any pair of elements ( <strong> S<sub>i</sub>, T<sub>j</sub> </strong> each of them to be the starting number of its corresponding array) if and only if <strong>i Modulo G = j Modulo G</strong>.</p>
<p>As a conclusion, we take the differences between every 2 consecutive elements in both arrays, group them by modulo. For each group take the minimum possible difference. Check each modulo, and calculate the sum of the best differences (in both arrays). Our answer would be the minimum cost of all modulos.</p>
<h1>Complexity</h1>
<p><strong>O(n log n + m log m)</strong> for sorting.</p>
<p>Rest of calculations can be done in <strong>O(n + m)</strong></p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME63/setter/XTGR.cpp">here</a>.</p>
<p>Tester's/Editorialist's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME63/tester/XTGR.cpp">here</a>.</p>deadwing97Wed, 29 Aug 2018 22:18:40 +0530https://discuss.codechef.com/questions/134626/xtgr-editorialnumbertheoryltime63greedyeditorialSPOOL Editorialhttps://discuss.codechef.com/questions/134634/spool-editorial<h1>PROBLEM LINK:</h1>
<p><a href="https://www.codechef.com/problems/SPOOL">Practice</a> <br>
<a href="https://www.codechef.com/LTIME63A/problems/SPOOL">Contest</a> </p>
<p><strong>Author:</strong> <a href="https://www.codechef.com/users/kingofnumbers">Hasan Jaddouh</a> <br>
<strong>Tester:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a> <br>
<strong>Editorialist:</strong> <a href="https://www.codechef.com/users/deadwing97">Hussain Kara Fallah</a></p>
<h1>PROBLEM</h1>
<p>Chef has a swimming pool. The swimming pool is <strong>N</strong> metres in length (long course) and a fixed width <strong>1</strong> metre. Its long course is split into <strong>N</strong> equal parts, with possibly different depths. For each valid <strong>i</strong>, the <strong>i-th</strong> part has depth <strong>D<sub>i</sub></strong> metres.</p>
<p>You should process <strong>Q</strong> queries. There are two types of queries:</p>
<ul>
<li><strong>1 x v</strong> pour <strong>v</strong> cubic metres of water into the <strong>x<sub>th</sub></strong> part of the pool</li>
<li><strong>2 x</strong> find how much metres deep is the water surface from the ground in the <strong>x<sub>th</sub></strong> part of the pool.</li>
</ul>
<p>Water level obeys the following rules. As long as the water level in some part of the pool is higher than the water level in at least one of the adjacent parts, the water from it will move to adjacent parts with lower water levels until water levels become equal or there is no water left in this part. If the adjacent part from both sides (left and right) have lower water level then the half of the quantity of water in the current part will move to left and the other half will move to the right. The water on the leftmost part can't move to the left, and the water on the rightmost part can't move to the right.</p>
<p>When the water level reaches the surface of the pool (i.e. its depth become 0), the pool overflows and the water level does not increase anymore. </p>
<p>Please refer to the problem samples for better understanding.</p>
<h1>PREREQUISTES:</h1>
<p>Disjoint sets</p>
<h1>CONSTRAINTS</h1>
<p><strong>N,Q <= 10<sup>5</sup></strong></p>
<h1>DIFFICULTY</h1>
<p>HARD</p>
<h1>EXPLANATION</h1>
<p>Suppose we poured water on the <strong>x<sub>th</sub></strong> part of the pool. Think where the water would go.</p>
<p>Let's suppose that the water will move to the left. Where will it stop?</p>
<p>It will stop at the <strong>A<sub>th</sub></strong> part which is the first part the satisfies:</p>
<ul>
<li><strong>D<sub>i</sub> >= D<sub>i+1</sub></strong> for each <strong>i in range [y,x-1]</strong></li>
<li><strong>D<sub>y</sub> >= D<sub>y-1</sub></strong> <strong>(if y > 1)</strong></li>
</ul>
<p>Let's put it in words (should be the first part such that the parts starting from the <strong>x<sub>th</sub></strong> one till the <strong>y<sub>th</sub></strong> forms a non-decreasing sequence <strong>AND</strong> the <strong>y<sub>th</sub></strong> part is deeper than the part to its left.</p>
<p>By the same logic we can deduce the position of the part that the water will stop at while moving right. (of course it will not stop forever there, because after filling these parts the water may continue flowing <strong>BUT</strong> at least some water will residue there.</p>
<p>Let's suppose that at each query we could know these parts quickly (just assume that). Solving the problem would be easy. After figuring the part that water will residue at (from the left side and right side). The water would keep residing there (in half) until one of these parts become on the same level with the one to its left or to its right (after that the water will behave differently).</p>
<h1>IMPORTANT OBSERVATION</h1>
<p>Whenever a part of our pool becomes on the same level with one of its adjacent neighbor parts we can treat them as the same part with the same level and their levels must keep growing together (till the pool overflows). So we will have at most <strong>n-1</strong> merges. This will allow us to use the disjoint set union.</p>
<p>So now for each pouring query, we can figure out where the water will stop from left and from the right. We can also determine the amount of water that will move until the current scenario changes (one of these 2 parts become on the same level with one of its neighbors). We keep pouring water until that moment and after that merge the parts that became on the same level. After that, we can call the function recursively to continue pouring (Since there will be no more that <strong>n-1</strong> merges it will be ok).
I will not explain how to handle cases of pouring water (left finish first, right finish first, none is finished....) because it's not hard to come with.</p>
<p>Now we should think what we should keep for each disjoint-set union structure. Since we merge neighboring parts with the same level we should keep the <strong>leftmost part</strong> and the <strong>rightmost part</strong> in each union. Of course along with the <strong>level</strong> of this union. </p>
<p>We still need to know one more thing, how to get the parts that water will stop at quickly?</p>
<p>We just need to maintain 2 sets. The first set contains the indices of parts such that each part is deeper than the part on its right. The second set contains the indices of parts such that each part is deeper than the part on its left.</p>
<p>So when pouring on some part just find the nearest one to its right deeper than its right neighbor and the same for the left. When some part has its level increased we can just delete it from one of the sets (or both) if necessary.</p>
<h1>Complexity</h1>
<p><strong>O(n log n)</strong></p>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME63/setter/SPOOL.cpp">here</a>.</p>
<p>Tester's/Editorialist's solution can be found <a href="http://www.codechef.com/download/Solutions/LTIME63/tester/SPOOL.cpp">here</a>.</p>deadwing97Thu, 30 Aug 2018 01:44:00 +0530https://discuss.codechef.com/questions/134634/spool-editorialdsultime63editorial