Codechef Dec’15 Challenge

1. Chef and the stones [Problem link]
The greedy approach is to select the largest possible number in each move. Because if you start from 1, at the end it may happen that 1 is left in both boxes. But you can’t select 1 again as you have already selected it.
Next, Binary search is required for fast calculation of the moves along with arithmetic series sum formula.
My code

2. Oracle Devu and Longest Common Subsequence [Problem link]

Small constraint on n and m and description about LCS made the problem quite deceiving to apply DP algorithm. A fact that you need to observe in solving this problem is that all the given input strings will consist of only ‘a’ and/or ‘b’. Let’s say, you have n input strings. In each string, number of occurrences of ‘b’ is greater than number of occurrences of ‘a’. So in this case, will you choose a hidden string that consists of ‘b’ mostly? No. Because it will create a LCS which would be larger. Instead you should choose a hidden string that consists of ‘a’ mostly. Then you will get least LCS length.
My code

3. Plane Division [Problem link]
Among all the lines, largest subset of lines is the one which has most number of distinct visible parallel lines. Distinct visible lines in a sense that sometimes two seemingly different tuples represent same line. (3,4,5) and (30,40,50) represent same line.
The basic idea to solve this problem is to store the group of parallel lines according to their same slope. When a single slope contains most number of lines, it makes the answer to this problem.
My code

4. Chef and Filters [Problem link]
This is a kind of subset dp problem. In my opinion, the main trick in this problem is to realize that there are 210 i.e 1024 distinct filters although in the input you will be given up to 105 filters. This fact reduces the dp state space from 100000 x 1024 to 1024 x 1024 and overcomes TLE.
I have used bitwise-xor operation to calculate the final photo status according to different subsets of filters.
My code

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s