August CookOff Contest Problem Editorials

CodeChef August 2011 Cook-Off : Editorials

Problem Tester for the contest was Harsha S

Problem Setter for this contest was Anil Kishore

I hope you liked the problems of this cook-off. Though they may be relatively easier than usual cook-offs, this time I thought a few more people should solve more number of problems and give problems that are more idea centric and needs less code. In Short - contests with relatively easier problems, all levels of coders can test their skills, be it speed or solving more number of problems than before. Hope these are satisfied tonight. For some problems, I'll write just the idea in short, and a more detailed explanation will be provided if needed. Please do comment below.

--------------------------------------------------------------------------------------------------------------

NDLVOTE : Vote for the Noodle Soup

The score starts with 0 and we are given total score after each of Po's clicks and we need to find the minimum number of users other than Po that could have possibly voted. The important thing to notice is, we just need to maintain the total number of users so far that have voted at least once, and we have the freedom to assign +1 or -1 to each of them :). We can get the total score of users other than Po by just subtracting Po's vote,

which is just the vote he clicked now. Also, if we can reach a score of S, we can also reach -S ( all votes reversed ). So, we will try to get the score T = abs(S). If we have N users already and to get a total score of T,

1.) T >= N : All N users vote +1, still we need score of (T-N) more, so we need (T-N) more users

2.) T < N : Let some T out of N users vote +1. The remaining (N-T) users should contribute zero, which is possible only if (N-T) is even, else we need just one more user.

Problem Setters Solution

Problem Testers Solution

--------------------------------------------------------------------------------------------------------------

DRAGNXOR : Open the Dragon Scroll

We need to make A^B maximum by shuffling the 1 bits within A and B. As 1 ^ 0 = 0 ^ 1 = 1, we need to make maximum number of (1,0) or (0,1) pairs, where a pair means the corresponding bits from A and B at a particular bit position. Also, to make the result maximum, we want all the ones towards the most significant side (left). Lets pair each 1 bit of A with a 0 bit of B. There can be at max x = minimum_of( number of 1s in A, number of 0s in B). Similarly, pair each 1 bit of B with a 0 bit of A. There can be at max y = minimum_of( number of 1s in B, number of 0s in A). Rest of the pairs are either (1,1) or (0,). So, the number of ones in the result is at max P = x + y. The answer is (1111...) : P times followed by (...000) : N-P times, which is nothing but the integer ( ((1<<P)-1) << (N-P) ).

Problem Setters Solution

Problem Testers Solution

ROTSTRNG : Rotate the String

We are given a string S and we keep rotating it till we get back to the string S. Note that this can always be possible, if we rotate S a multiple of N times, where N is the length of S. But, we are more concerned if it can be reached before that. Let S(i) = S[i..N-1] + S[1...i-1]. So S(0) = S. Once we know for each i, if S(i) equals S, then we can simulate the rotations of Monkey and Po, as any rotation will result in a string which is one of S(i). We can use KMP here :). Consider a string S2 = S + S and find the KMP Failure Function F for S2. F[i] denotes the length of the maximum proper-suffix that is also prefix of S2.

If F[i] = N, then N length suffix of S2[0,..,i], i.e., S2[i-N+1,..,i] = N length prefix of S2[0,..,i] = S2[0..N-1] = S. So, we can find all such indices using O(n) KMP and then just simulate the rotations by just going through the S(i)s in order. Note that answer will always exist and there is never a -1 case.

Problem Setters Solution

Problem Testers Solution

TKCHOCS : Collect the Chocolate Chips

After reading the problem, you may feel its a Dynamic Programming (DP) problem. Yes, it is.. but there are few more things to consider. Po moves down and Mantis moves left and they need to maximize the choco chips they collect. You can run a dp normally, but the problem with this is, you also need to remember the cells visited by Po and do not add that when Mantis visits it again. That doesn't sound good. If you observe carefully, Po should always move down and Mantis should always move left, and they both should reach (N,1). Both of them can not cross the diagonal ! So, they can only meet on the diagonal. We can as well try all possible cells at which both of them reach the diagonal ( refer setters solution ), or you can do a O(n) method going from bottom-top on the diagonal ( refer testers solution ). Complexity is O(n^2).

Problem Setters Solution

Problem Testers Solution

KCHIPS : Angry Chefs - Crispy Chips

We can answer queries off-line. A very high-level explanation is below.

Let's have a S ( data structure ) where we store some indices, one for each village. We process villages in increasing order of indices ( as will be explained below ) and in S we just store the Kth most recent index of that village ( if it exists i.e., it occurred more than K times already ) so far, for each of the villages.

We have villages ( indices i ) and queries ( intervals [a,b] ). We take all indices i and all end points of intervals i.e., b's and sort them and process in increasing order.

When you process an element

- If its a village index, note it down under the indices of this village. Update S accordingly i.e., remove old Kth recent index and insert new Kth recent index

- If its a query interval end b, get the corresponding a, and the answer for this query is just the number of integers in S that are greater than equal to a. Store the answer at the query index in ans[] array.

Finally, print ans[] array.

We can use a BIT ( Binary Indexed Tree ) as S. If you are a Java fan, you will love to see the nicely written very abstract solution of the tester.

Problem Setters Solution

Problem Testers Solution