2011 May CookOff Contest Problems Editorial

Problem Tester for the contest was 'Harsha S'

---

Popular Rice Recipe [TIDRICE] (written by Anil Kishore aka flying_ant )

We are given the votes of many users in the order they arrived and we are asked to calculate the correct final score. The only thing we need to worry about is, how to handle multiple votes by the same user. The statement says, "If a user votes more than once, the user's previous vote is first nullified before the latest vote is counted". Given the votes of a particular user in the order he voted, we need to process them one by one and update the final score, as shown in the explanation of Case 1.

But wait, do we really need to count each vote only to nullify it again ? The answer is No. If we are going to nullify a vote, why to count it at all ? Lets count only the votes that are not going to be nullified. It should be easy to observe that such votes are nothing but the last votes of each user. So, all we need to do is count the last vote of each user. The low constraints allowed codechefs to use any bruteforce method. As its been quite long since I coded in plain C, you can refer my C code below. For C++ / Java coders, a Map ( string → int ) will do, as it replaces the old value with the new value, when a new (key, value) is put with the same key.

{ Those of you who didn't observe , TID RICE is an anagram of DIRECTI :) }

Problem Setter Solution
Problem Tester Solution

Distribute idlis Equally [EQIDLIS] (written by Anil Kishore aka flying_ant )

This is supposed to be an easy problem, and all you have to do is simulate the given step. If there are T idlis in total and at the end of the distribution, each of the N students gets equal number of idlis, then each should get ( T / N ) idlis. So, if ( T % N ) != 0, then it is not possible to distribute equally and you should print -1. If T % N == 0, then it is always possible to distribute equally in a finite number of steps. Lets see an informal proof of the same.

Lets consider only the cases when T % N == 0. Let D = ceil( ( max - min) / 2 ). If ( max - min ) == 0, we are done. If ( max - min ) == 1, the array would look like {a, a,..., a, a+1, a+1,..., a+1} with some x number of (a+1)'s ( x >= 1 ) and N - x number of (a)'s ( N - x >= 1 ). We can see that for any possible x, T % N == x ( != 0 ), hence there will never be a case where ( max - min ) == 1 ( while having T % N == 0 ). For ( max - min ) >= 2, D >= 1 and max = max - D, min = min + D and the difference between these two numbers strictly decreases. So, in some finite number of steps, all the numbers will become equal.

A simple solution performing a O(n) search to find minimum and maximum in each step should be enough to pass in the given time.

{ As described in the problem statement, ACM-ICPC world finals opening ceremony was actually happening while you were reading this problem in the contest. I'm not sure if Dexter Murugan was there ;) }

Exercise 1: Find the maximum value of the answer for 1 <= N <= 3000 and 0<= A[i] <= N,or at least a good upper bound
Exercise 2: If the maximum answer can be R, think of how to solve the problem in O( N + R logN )

Problem Setter Solution
Problem Tester Solution

Packing the Golden Triangles [PACKBAND] (written by Anil Kishore aka flying_ant )

This problem can be solved using a greedy strategy. We are given that a (R1,R2) rubber band can be used to pack a cubical box of side length L, only if 2 * 22/7 * R1 <= 4 * L <= 2 * 22/7 * R2. To avoid working with floating point numbers, we can multiply the equation with (7/4) on all sides and we get 11*(R1) <= 7L <= 11*(R2). Taking A = 11*(R1), B = 11*(R2) and C = 7*L, we have A <= C <= B. So the problem is, given some intervals [A_i, B_i] (0<=i<M) and some points C_j (0<=j<N), we can make a pair (interval_i,point_j) if point j lies in the closed interval i. We need to make maximum number of (interval,point) pairs where each interval and point appears in at most one pair. This is like Maximum Bipartite matching. But the graph is not any arbitrary graph and has some properties, which can be used to design a more efficient algorithm. This new problem is very similar to the standard Interval Scheduling Problem, which has a nice greedy strategy ( Choose the earliest finishing time first ).

We sort the points in ascending order and process them from left to right. We will try to assign an interval to the current point under consideration. If there are many intervals that can be assigned, which one to choose ? This is where the need of a good greedy strategy is. If we assign an interval which finish earliest ( i.e., smallest Bi), then there is a good chance that more intervals will be available for the points on the right. Even in the optimal assignment if we take the left most point that is paired with an interval which is not the earliest finishing interval, reassigning the point to the earliest finishing interval will not make the answer worse. This is just for intuitive understanding and a formal proof will be similar to that of the Interval Scheduling Problem.

{ I hope the reason why some of you couldn't solve the problem is because you were not able to code while thinking of Samosa :) }

Exercise : Though we kept the constraint on N very low ( 1 <= N <= 1000 ) to allow O(N²) to pass, getting a simple O(N logN) is also easy. Think of how to solve this in O(N logN)

Problem Setter Solution
Problem Tester Solution

Socializing Game around Pizza [BIGPIZA] (written by Anil Kishore aka flying_ant )

This problem needs very basic knowledge of Game Theory, particularly Nim and Grundy. If you are not familiar with these terms, you can refer ( TopCoder tutorial on Algorithm Games here ) and for many interactive games online with good introduction, you can refer ( cut-the-knot here ).

The game here is joining some of the N points on a circle with chords such that, no two chords intersect each other, not even at their end points. Take a game with N points on a circle, if we make one move in this game ( i.e., draw a chord ), then two points are taken by this chord and depending on which two points are selected, the remaining N - 2 points are split in to two sub-games ( possibly empty ) and more over, they are independent of each other. We have to find the grundy value for the game with N points. A position is losing if the grundy value is zero and it is winning if its non-zero. Grundy value is the minimum excluded value among all the grundy values of the subgames that can be reached from the current game. For a game with N points, let the two subgames formed have X and Y points. All possible (X,Y) non-negative integer pairs such that X + Y = N - 2 can be reached. The low constraint on N ( 2 <= N <= 10000 ) allowed coders to try all possible subgames, leading to a O(N²) solution. Note that the number of test cases are 1000, so you can precompute the grundy values for all possible N, either bottom-up ( dynamic programming ) or top-down ( memoization ). You can refer my well commented solution below to understand it better and to see how simple the code is.

{ I hope Alice & Bob can rest for some time at least in India and Arjuna & Bhima can play games from now on. By the way, they are from the Elephant city ( Hasthinapur ) :) }

Problem Setter Solution
Problem Tester Solution

Preferred Cooking Schools [CKSCHOOL] (written by Anil Kishore aka flying_ant )

This problem can be solved using a suitable data structure and it can be built to support online queries. There are at least a couple of ways to solve this, here we explain a solution using segment trees, which is simple to understand and answers each query in O(log²N). The most important step in solving this problem is, understanding the problem itself and abstracting it in a simple way. Imagine a 2D plane, where you mark a point for each school, taking fee on X axis and distance on Y axis, as shown in the figure below. Each query can be seen as a 3 sided range query, as shown by the thin blue line in the figure. The first step is to realize that, if we have many schools with the same fee, we can just keep the one among them having minimum distance and can completely ignore the other schools ( eg: the point striked off in red in the figure ). School X is preferred over school Y, if Y is strictly in the top-right quadrant, as seen from X. For example, P2 is preferred over P3 and P5. Now, how does the subset 'Max Special S' actually look like ? If you consider all the given points, then it contains the points on the green line {P1, P2, P4, P6}. The union of the top-right quadrants of these points cover all the points present. We refer this line as Special line.

Note that the points that are not present in the global Special line can be part of a query special line, eg: P3 is not on the global Special line ( green color ), but is on the thick blue line, which is the Special line for the query shown in blue border. We sort all the points on X in increasing order and make them the leaves of our segment tree. Each internal node is associated with a set of points, which is the set of points present in the leaves of the subtree rooted at this internal node. We build the segment tree and store the Special line at each node, of the points associated with that node. To store the special line, we can just store the Y coordinates in the descending order and if the points are sorted already, we can just find the special line by doing a O(N) traversal at each node. Now, given a query (maxD, minF, maxF), we traverse the segmentree starting from root and with (minF,maxF) and identify the set of nodes that exactly covers the interval [minF, maxF]. We know that there can be at most O(logN) such nodes. Also, we have the Special lines computed already for each of them. All that is left is, to stitch these individual special lines, to get the special line for the given query.

Consider two adjacent intervals [a,b] and [b+1,c]. If we have computed the Special lines for [a,b] and [b+1,c] already, can we find the Special line for [a,c] using them ? Yes, if you observe carefully, as we move from left to right, the points on the right side doesn't influence the Special line for the points on the left side. So, the Special line of [a,c] starts exactly with the Special line of [a,b]. Lets say the special line of [a,b] = {Y11,Y12,...,Y1m} and that of [b+1,c] = {Y21,Y22,...,Y2n}. Take the y-coordinate of the last point on the special line [a,b] i.e., Y1m and find the largest y-coordinate on the special line of [b+1,c] that is smaller than Y1m and say its Y2k, then the special line for [a,c] = {Y11, Y12, ..., Y1m, Y2k, Y2k+1, ..., Y2n}. We can find this by a simple binary search for Y1m in {Y21,Y22,...,Y2n}. A picture is worth a million words, take a look at the figure on the right. The thick green interval is split in to some continuous light-green intervals, for which we have computed the individual Special lines already ( light-blue ). We start with the left-most interval and count its Special points and binary search for its last point ( shown with red line ) in the interval adjacent to it and count its special points starting from there. We continue this O(logN) search for each pair adjacent of O(logN) intervals, leading to O(log2N) per query.

{ I hope my dad doesn't kick me for using his name in this problem :) }

Exercise : Think of a method to solve the problem in O( N logN + Q logN )

Problem Setter Solution