Questions Tagged With cook42https://discuss.codechef.com/tags/cook42/?type=rssquestions tagged <span class="tag">cook42</span>enMon, 24 Mar 2014 00:22:17 +0530SIGSEGV in COOK42 - ABCSTRhttps://discuss.codechef.com/questions/40370/sigsegv-in-cook42-abcstr<p>I've employed the same method described in the editorial just the implementation is a bit different.
For each index calculate the no. of A's, B's, and C's till that index. Then calculate A[i]-B[i], B[i]-C[i] for each index. Store them in a structure. Sort them out. If there are X continuous pairs for which these are equal, add C(x,2) to the final count.
I am getting SIGSEGV and am not able to spot out the error. Any help would be appreciated.</p>
<p>Link for the code : <a href="http://www.codechef.com/viewsolution/3641333">link text</a></p>eh2archMon, 24 Mar 2014 00:22:17 +0530https://discuss.codechef.com/questions/40370/sigsegv-in-cook42-abcstrabcstrcook42sigsegvCAKE2AM - Editorialhttps://discuss.codechef.com/questions/37281/cake2am-editorial<h1>PROBLEM LINKS</h1>
<p><a href="http://www.codechef.com/COOK42/problems/CAKE2AM">Contest</a><br>
<a href="http://www.codechef.com/COOK42/problems/CAKE2AM">Practice</a></p>
<p><strong>Author</strong>: <a href="http://www.codechef.com/users/satej">Abdullah Al Mahmud</a><br>
<strong>Tester</strong>: <a href="http://www.codechef.com/users/gerald">Gerald Agapov</a><br>
<strong>Editorialist</strong>: <a href="http://www.codechef.com/users/vaka">Praveen Reddy Vaka</a></p>
<h1>DIFFICULTY:</h1>
<p>medium-hard</p>
<h1>PREREQUISITES:</h1>
<p>Graph Theory, Maximum Independent Set in Bipartite Graphs, Max Flow/Min Cut, Geometry</p>
<h1>EXPLANATION</h1>
<p>Consider the following diagram as an example. The several polygons (there are four in total) represent the cuts made and the numbered regions denote the pieces formed as a result.
<img src="https://codechef_shared.s3.amazonaws.com/download/cake2-cake.png" width="100%">
We can denote the cake as graph where each piece is a node and and two nodes will be connected if the corresponding pieces share an edge in the cake. In the original problem we have to choose cake pieces such that no two cake pieces have a side in common and the total volume of the cake pieces selected is maximum. If we denote the volume of each piece as a weight in the corresponding graph node. Our problem reduces to finding the set of nodes in the graph such that no two nodes are connected and the sum of weights is maximum. This is the maximum weighted independent set problem. This is a NP- Complete problem for general graphs but it can be solved in polynomial time for bipartite graphs. If we observe carefully the graph that we constructed will always be bipartite, due to the constraints placed on cuts (We will present a proof later). First let us see the graph representation of the cake shown above.
<img src="https://codechef_shared.s3.amazonaws.com/download/cake2-graph.png" width="100%">
The complement of a independent set in a graph is a vertex cover. So the complement of maximum weighted independent set in a graph will be its minimum weighted vertex cover. We can construct a new graph G' such that the the value of minimum weighted vertex cover in our graph will be same as the weight of minimum cut in G'. The construction is as follows. If our original graph is G and since G is bipartite we can divide the vertices into two sets R and B such all edges are between R and B only (we can use a simple dfs/ bfs to do this classification). Our G' will be a edge weighted graph with all the vertices of G intact and all edges are given a weight of infinity. We add two new vertices source and sink. for every i in R we add an edge from source to i with a weight oght of area(i). for every j in B we add an edge from j to sink with a weight of area(j). Minimum vertex cover in the original graph is same as minimum cut in G' which we can find using max flow. The answer will be (total area - obtained value for min cut).</p>
<h1>SOLUTIONS</h1>
<p><strong>Setter's Solution</strong>: <a href="http://www.codechef.com/download/Solutions/COOK42/Setter/CAKE2AM.cpp">CAKE2AM.cpp</a><br>
<strong>Tester's Solution</strong>: <a href="http://www.codechef.com/download/Solutions/COOK42/Tester/CAKE2AM.cpp">CAKE2AM.cpp</a><br></p>vakaMon, 20 Jan 2014 01:18:52 +0530https://discuss.codechef.com/questions/37281/cake2am-editorialeditorialgeometrycook42medium-hardmaxflowbipartitemax-indep-setCAKE1AM - Editorialhttps://discuss.codechef.com/questions/37269/cake1am-editorial<h1>PROBLEM LINKS</h1>
<p><a href="http://www.codechef.com/COOK42/problems/CAKE1AM">Contest</a><br>
<a href="http://www.codechef.com/COOK42/problems/CAKE1AM">Practice</a></p>
<p><strong>Author</strong>: <a href="http://www.codechef.com/users/satej">Abdullah Al Mahmud</a><br>
<strong>Tester</strong>: <a href="http://www.codechef.com/users/gerald">Gerald Agapov</a><br>
<strong>Editorialist</strong>: <a href="http://www.codechef.com/users/vaka">Praveen Reddy Vaka</a></p>
<h1>DIFFICULTY:</h1>
<p>cakewalk</p>
<h1>PREREQUISITES:</h1>
<p>Basic Coordinate Geometry</p>
<h1>EXPLANATION</h1>
<p>Restated in simple terms the problem asks for the area of the union of rectangles. Let us call the rectangles R1 and R2. A rectangle is represented by two points (x1, y1) its bottom left point and (x2, y2) its top right point.</p>
<p>If the rectangles don’t intersect the answer would be simply sum of areas of the individual rectangles. If they intersect then we need to subtract the intersecting area as we account for this area twice in the sum. So the answer is simply area(R1) + area(R2) - intersectingArea(R1, R2).</p>
<p>Let us now look at how to find if the two rectangles are intersecting and the area of their intersection. First let us consider just the case when the rectangles intersect. Here is a diagram showing some possibilities of rectangles intersecting.</p>
<p><img src="https://codechef_shared.s3.amazonaws.com/download/Rectangle%20Intersection.png" width="100%"></p>
<p>Based on these figures it can be easily observed and also proved for any general case that if the rectangles intersect the lower left point of the rectangle representing the intersecting area is (max(R1.x1, R2.x1), max(R1.y1, R2.y1)) and the top right point is (min(R1.x2, R2.x2), min(R1.y2, R2.y2)). Once we find these points we can find the area of the intersecting region also. Note that the rectangles R1 and R2 are interchangeable it doesn’t matter which one is seen as the first rectangle. </p>
<p>To check if the two rectangles intersect in the first place it is as simple as finding these two points and see it they form a well defined rectangle. If they form a well defined rectangle they intersect otherwise they don’t. Let us call the two points (R3.x1, R3.y1) and (R3.x2, R3.y2), they form a well defined rectangle only if (R3.x1 < R3. x2) and (R3.y1 < R3. y2) as both coordinates of bottom left point have to come before the corresponding coordinates of top right point.</p>
<h1>SOLUTIONS</h1>
<p><strong>Setter's Solution</strong>: <a href="http://www.codechef.com/download/Solutions/COOK42/Setter/CAKE1AM.cpp">CAKE1AM.cpp</a><br>
<strong>Tester's Solution</strong>: <a href="http://www.codechef.com/download/Solutions/COOK42/Tester/CAKE1AM.cpp">CAKE1AM.cpp</a><br></p>vakaMon, 20 Jan 2014 01:07:28 +0530https://discuss.codechef.com/questions/37269/cake1am-editorialgeometrycook42editorialcakewalkGANGAAM - Editorialhttps://discuss.codechef.com/questions/37266/gangaam-editorial<h1>PROBLEM LINKS</h1>
<p><a href="http://www.codechef.com/COOK42/problems/GANGAAM">Contest</a><br>
<a href="http://www.codechef.com/problems/GANGAAM">Practice</a></p>
<p><strong>Author</strong>: <a href="http://www.codechef.com/users/satej">Abdullah Al Mahmud</a><br>
<strong>Tester</strong>: <a href="http://www.codechef.com/users/gerald">Gerald Agapov</a><br>
<strong>Editorialist</strong>: <a href="http://www.codechef.com/users/vinodreddy@iitb">Vinod Reddy</a></p>
<h1>DIFFICULTY:</h1>
<p>easy</p>
<h1>PREREQUISITES:</h1>
<p>Greedy Algorithms</p>
<h1>EXPLANATION</h1>
<p>We will solve the problem using greedy approach. We will traverse the events occurring(Entering and exit of a gangster) according to increasing time and greedily select which gangster to interrogate and finally we proove the optimality using an exchange argument.</p>
<p>We can visualize the traversing time as taking snapshots of the party at each enter and exit of a gangster(We sort these events in increasing order of time and loop through). After each entering of a gangster if there are K gangsters(K > X-1) unmarked gangsters we pick the K-X+1 gangsters whose exit times are farthest and mark them for interrogation. We continue this process for the whole events and finally we get the required no minimum count. The total algorithm can be implemented in O(NlogN). The logN factor here is for maintaining the end points of unmarked gangsters who are present in the party. </p>
<p>Proof :
Let O be an optimal solution for picking gangsters for interrogation.Let the solution given by above algo is P. When we are traversing the events let t be the first snapshot of party where there are K > X-1 unmarked gangsters. According to O some(at least K-X+1) of these K gangsters are marked. lets take the gangster whose exit time is farthest. P picks this guy for marking but if O doesn’t pick this guy then we can make a change in O by unmarking the gangster with smallest exit time and marking the one with the farthest. We can easily see that this doesn’t cause any problems.
Similarly we can do this for all the K-X+1 gangsters picked by our algo. So at this snapshot we can say that the set of gangsters marked by P is subset of that of O. We can extend the argument to all snapshots and this employs that P is at least as good as O but O being the best so should be P.</p>
<h1>SOLUTIONS</h1>
<p><strong>Setter's Solution</strong>: <a href="http://www.codechef.com/download/Solutions/COOK42/Setter/GANGAAM.cpp">GANGAAM.cpp</a><br>
<strong>Tester's Solution</strong>: <a href="http://www.codechef.com/download/Solutions/COOK42/Tester/GANGAAM.cpp">GANGAAM.cpp</a><br></p>vinodreddy@iitbMon, 20 Jan 2014 01:02:46 +0530https://discuss.codechef.com/questions/37266/gangaam-editorialcook42easygreedyeditorialORDERAAM - Editorialhttps://discuss.codechef.com/questions/37299/orderaam-editorial<h1>PROBLEM LINK:</h1>
<p><a href="http://www.codechef.com/problems/ORDERAAM">Practice</a> <br>
<a href="http://www.codechef.com/COOK42/problems/ORDERAAM/">Contest</a></p>
<p><strong>Author:</strong> <a href="http://www.codechef.com/users/satej">Gerald Agapov</a>
<strong>Tester:</strong> <a href="http://www.codechef.com/users/gerald">Abdullah Al Mahmud</a>
<strong>Editorialist:</strong> <a href="http://www.codechef.com/users/vinodreddy@iitb">Vinod Reddy</a></p>
<h1>DIFFICULTY:</h1>
<p>HARD. </p>
<h1>PREREQUISITES:</h1>
<p>Flow,Greedy</p>
<h1>PROBLEM:</h1>
<p>We are given orders of the form (Si,Di,Xi,Pi) where Si and Di and starting and ending time slots and Xi is the number of the items to be prepared and Pi is the penalty for leaving out a single item of the order. We need to fill the time slots with items so that penalty is minimized.</p>
<h1>QUICK EXPLANATION:</h1>
<p>There are two approaches to the problem one min-cost flow which is a bit risky with time limits since you need the best implementation and another easily implementable greedy solution.</p>
<p><strong>FLOW SOLUTION : </strong>
In the flow solution you have time slots on the left and orders on the right. for every order you will have an edge between order and the time slots it is given and the edge cost will be the penalty of the order and capacity 1. Here the no of slots are large. So you can divide total no of slots into ranges of slots such that every range can either be part of a order totally or not. This can be achieved easily and using them as nodes we can run the min-cost flow algorithm.</p>
<p>We approach a greedy solution where we process the tasks in order of decreasing penalty and at each step we try to accommodate maximum number of the items of the present order.
The second step(accommodating maximum number of items) can be solved using another greedy approach.Details are given below.</p>
<h1>EXPLANATION:</h1>
<pre><code> First lets solve the following sub problem which will be used in the subsequent main solution.
Lets say we have k orders each with penalty 1. We need to know the minimum penalty now. this can be solved easily using a greedy approach. I will build the greedy approach in two steps.
**Step 1 :** Suppose now additionally let the Xi of all the orders be 1. Now if have to find the minimum penalty we can model it by finding a maximum matching in a bipartite graph where orders are nodes in the left side and slots are in the right side and range of every vertex in left is a contiguous number of nodes in right. This can be done very easily through greedy approach(I leave the actual algo for reader).
**Step 2 :** Now if we try to do it for orders where Xi can be anything we can emulate the above algorithm except only here the groups of nodes in right are allocated to a node in left. Though not practically feasible if it helps, you can visualize an order of Xi items as Xi orders with 1 item and same ranges and apply above algorithm.
**Main Solution :** In the main solution we process the orders in the order of their decreasing penalty. Lets say for the first k orders we didn't require to get any penalty. Now we are trying to allocate items of the (k+1)th task.For this we solve the above sub problem specified above for the k+1 tasks i.e assume penalty is 1 for all the tasks and get the penalty for first k+1 orders. Let this penalty be p. So the maximum matching will leave out p items. We can construct the new matching where the p items returned are only the items of order k+1 because when we trim the items of order k+1 to X_k+1-p and apply the algorithm the returned value will be 0.
Now we want the p items to be of order k+1 because order k+1 will have least penalty. We trim down the items of order k+1 to X_k+1-p and add the p items to global penalty and do this process for order k+2 and so on. Finally we will get the total minimum penalty.
</code></pre>
<h1>AUTHOR'S AND TESTER'S SOLUTIONS:</h1>
<p>Author's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK42/Setter/ORDERAAM.cpp">here</a>. <br>
Tester's solution can be found <a href="http://www.codechef.com/download/Solutions/COOK42/Tester/ORDERAAM.cp">here</a>. </p>
<h1>RELATED PROBLEMS:</h1>vinodreddy@iitbMon, 20 Jan 2014 04:36:39 +0530https://discuss.codechef.com/questions/37299/orderaam-editorialorderaammin-cost-flowhardgreedycook42editorialGAMEAAM - Editorialhttps://discuss.codechef.com/questions/37284/gameaam-editorial<h1>PROBLEM LINKS</h1>
<p><a href="http://www.codechef.com/COOK42/problems/GAMEAAM">Contest</a><br>
<a href="http://www.codechef.com/COOK42/problems/GAMEAAM">Practice</a></p>
<p><strong>Author</strong>: <a href="http://www.codechef.com/users/satej">Abdullah Al Mahmud</a><br>
<strong>Tester</strong>: <a href="http://www.codechef.com/users/gerald">Gerald Agapov</a><br>
<strong>Editorialist</strong>: <a href="http://www.codechef.com/users/vaka">Praveen Reddy Vaka</a></p>
<h1>DIFFICULTY:</h1>
<p>easy</p>
<h1>PREREQUISITES:</h1>
<p>Combinatorial Game Theory, Sprague Grundy Theorem</p>
<p>Go through these tutorials to understand or refresh the above topics<br>
<a href="http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=algorithmGames">http://community.topcoder.com/tc?module=Static&d1=tutorials&d2=algorithmGames</a><br>
<a href="http://www.codechef.com/wiki/tutorial-game-theory">http://www.codechef.com/wiki/tutorial-game-theory</a><br>
<a href="http://www.codechef.com/wiki/tutorial-coin-game">http://www.codechef.com/wiki/tutorial-coin-game</a></p>
<p>If you are totally new to these topics it is suggested you go through these notes <a href="http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf">http://www.math.ucla.edu/~tom/Game_Theory/comb.pdf</a></p>
<h1>EXPLANATION</h1>
<p>Through out this problem we will consider number pairs of the form (a,b) such that a <= b. If the input contains a pair in reverse order we can just swap them. The game can be viewed as a directed graph where a pair denotes a node and each node has outgoing edges to all the pairs which can be obtained by the constraint in the problem. We consider (a,a) to be a losing position for all a, so the target of any player to reach a pair.</p>
<p>If we can solve the question for a single pair (a,b) we can use the Sprague Grundy Theorem to solve the composite game involving multiple such pairs by computing the grundy function g(a,b).</p>
<p><strong>Solving a single game (a,b)</strong></p>
<p>For a given position (a,b) we can move to the following positions (we will call this next positions)
(a, b - k*a) for all 1 <= k < floor(b/a) - 1
and (b%a, a)</p>
<p>i.e., if we are at position (5, 26) we can move to (5, 21), (5, 16), (5, 11), (5, 6), (1, 5)</p>
<p>A position (a,b) is winning if among all its next positions there exists at least one position which is losing position.
A position (a,b) is losing if all its next positions are winning positions, since no matter what the current player does the next player gets a winning position.</p>
<p>Since our graph is huge (numbers can be as big as 10^8) we can't compute the win loss values of target position by exploring all possible paths to terminals. Even we can't pre compute values for the same reason as the size of the graph is very huge. We shall look at an efficient way of finding out if a position (a, b) is winning or losing.</p>
<p>Let us define f(a,b) to be 0 if the position (a,b) is losing and 1 if it is winning.</p>
<p>We have already seen the next positions for a given (a,b) and it is a simple linear path always, we can exploit this to find out win loss values efficiently.</p>
<p>For a given (a,x) and x >= a we can group the number in the following way.</p>
<p>For all 0 <= i < a group i will contain all the number pairs [(a, a+i), (a, 2*a+i), (a, 3*a+i), (a, 4*a+i), (a, 5*a+i), .....]</p>
<p>For a given element in the list it will be the next position of all other elements coming after that in the list. Additionally except for the case i != 0 (i,a) will be a next position for all the pairs in the list. This is illustrated in the diagram below.</p>
<p><img src="http://codechef.com/download/euclid-game-graph.png" width="100%"></p>
<p>when i=0 the node (i,a) will not be present in the graph. By our construction for a node (a,a*k+i) all its next positions have to occur in the sub graph shown above.</p>
<p>when i != 0<br>
If f(i,a) = 1 then f(a, a+i) = 0 and for all k > 1 f(a, k*a+i) = 1 since they can move to (a, a+i).<br>
If f(i,a) = 0 then f(a, a+i) = 1 and also for all k > 1 f(a, k*a+i) = 1 as all (a, a*k+i) have (i,a) as their next position.<br>
when i = 0<br>
we have f(a,a) = 0 by definition. So for all k > 1 f(a, k*a) = 1 since they can move to (a, a).</p>
<p>So our algo to determine if (a,x) is winning or not in the case of a single game is pretty simple.</p>
<pre><code>f(a,x):
if (x == a) return 0;
if (x >= 2*a) return 1;
return 1 - f(x%a, a);
</code></pre>
<p><strong>Computing Grundy function g(a,b)</strong><br>
g(a,b) is defined as the minimum non negative number which is not present in the set {g(c,d) | (c,d) is next position to (a,b)}. Terminal nodes have values of 0. All other nodes can be given values based on the criteria since our graph representing the game is a directed acyclic graph. g(a,b) will be 0 if and only if it is a losing position.
Extending on the ideas to compute f(a,b) we can also compute g(a,b) efficiently.</p>
<p>If b = a*k for some k All its next positions are [(a, a*(k-1)), (a, a*(k-2)), ..., (a,a)]. Since (a,a) is a terminal node g(a,a) = 0. The pairs are connected as shown in the figure above. So we can only give the grundy numbers to them in a linear order. g(a, 2a) = 1, g(a, 3a) = 2 and so on. So for g(a,b) = g(a, a*k) = k -1 = (b/a) - 1;</p>
<p>If b = a*k + r for k>=1 and 1<= r < a the next positions are [(a, a*(k-1) + r), (a, a*(k-2) + r), ..., (a,a + r), (r,a)]. Again connectivity among the pairs is as shown in the figure. The value of g(r,a) governs the grundy value of other numbers in the list. <br>
If g(r,a) = 0 i.e., it is a losing position, then g(a, a+r) = 1 g(a, a+2r) = 2 .... g(a, b) = g(a, a*k + r) = k = floor(b/a)<br>
If g(r, a) != 0 then g(a, a+r) = 0 and we can give values to the pairs in a linear order as before but the value g(r, a) cannot be assigned to any position as (r, a) is a neighbor to all of these.
If g(r, a) = 2 the we will have g(a, a+r) = 0, g(a, a+2r) = 1, g(a+3r) = 3, g(a+4r) = 4, .... refer to tester's solution to how to simply compute this.</p>
<p>Once we can compute the grundy number for a single game all we need to do is find the grundy numbers of all the games and xor them together. If the result is 0 second player wins and if it is 1 the first player wins.</p>
<p>The single game happens to be a well studied game and goes by the name Euclid Game. There even exists a closed form solution for finding the grundy number for a given single game. Refer to <a href="http://www.sciencedirect.com/science/article/pii/S0012365X06003505">http://www.sciencedirect.com/science/article/pii/S0012365X06003505</a>. Setter's solution uses this.</p>
<h1>SOLUTIONS</h1>
<p><strong>Setter's Solution</strong>: <a href="http://www.codechef.com/download/Solutions/COOK42/Setter/GAMEAAM.cpp">GAMEAAM.cpp</a><br>
<strong>Tester's Solution</strong>: <a href="http://www.codechef.com/download/Solutions/COOK42/Tester/GAMEAAM.cpp">GAMEAAM.cpp</a><br></p>vakaMon, 20 Jan 2014 01:28:32 +0530https://discuss.codechef.com/questions/37284/gameaam-editorialgame-theorycook42easyeditorialsprague-grundy