MAY17 solutions

  1. CHEFROUT (Chef and his daily routine): This problem simply asks if a given string matches a C*E*S* regex. There are multiple ways by which this problem can be solved:
    • You can sort the string and check if the sorted string matches with the original one.
    • Iterate over string till there are C and then till E and then till S, if we don’t reach the end of the string we can say the result is no. Code
  2. UNICOURS (Courses in an university): This problem asks to minimize the number of courses that are prerequisite to any other course. Since all courses are in sorted order of difficulty, to minimize the courses which aren’t prerequisite to any other course, we must start assigning prerequisites from the very first course provided in input. Thus, for each i, the first i courses from A0, A1, … , Ai will become the prerequisites for the i’th course. Hence, the number of courses that won’t be the prerequisite of any course will be n – maximum element of the array. Code
  3. MXMEDIAN (Median of adjacent maximum numbers): The problem asks to find maximum median of array B. Since an element of B is maximum of adjacent elements of A, you can couple the maximum element of A with minimum element of A, thus the array B that will be generated will become the first n/2 elements of array A, and it’s median will be the median of the second half of sorted array A. Code
  4. CHEFSUBA (Chef and Sub Array): The problem asks to find the length of longest contiguous sub array of all 1’s. What we can do is we create an array double in size and populate the new array in the form: A A. Then we can apply maximum sum subset like algorithm which calculates sum till k elements and till element of array not become zero and precompute the maximum sum for array for each index from that index i to i+n(n being the size of array). For example,K = 3, n = 5A =                              1 0 0 1 1

    A A =                          1 0 0 1 1 1 0 0 1 1

    S(till K) =                   1 0 0 3 2 1 0 0 2 1

    Max Sum(for n) =    3 3 3 3 2 2 2 2 2 1

    From the last array we can take the last fifth element and print that element if ‘?’ is there and shift to previous element when a shift operator is found. Code

  5. WSITES01 (Blocked websites): The solution to this problem requires to build a tree of strings that represents all the strings in the input, parsing down on one of it’s branches would generate all the strings in the input. Also, keep a count of how many (+) and (-) strings pass through a particular node. Now all we need to do is to implement a recursive approach where we parse down all (-) branches and return all the possible strings generated. If we find any (-) string that is a substring of any (+) string, we should print -1. Code
  6.  CHEFCODE (Chef and Subsequences): This problem asks for number of subsequences that have product less than K. If you people remember sum subset problem which asks a similar thing but instead of product it asks for sum. We should implement a similar algorithm for this problem too. But, in that problem we use an array where we store how many times a sum(product for this problem) is generated and iterate over that. But, the space requirement of this problem does not allow us to solve using arrays and instead of arrays, we use map data structure to solve this problem. Code

Leave a Reply

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

WordPress.com Logo

You are commenting using your WordPress.com 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 )

Google+ photo

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

Connecting to %s