CodeChef: February Long Challange 2018

Chef And His Characters: Given a string, we need to find four contiguous characters that can make a string "chef". We need to print how many four contiguous characters ('c','e','f','h') we found. If we found any simply write "lovely (the number of contiguous four characters we found)" else print "normal" without the quotes.

Solution:  The easiest problem of the set. Simply bruteforce through the string from 0 to length-4 and each time see if four contiguous characters are found or not. If found, increase the counter. Finally output the result.

Chef and The Patents: Given N patents we need to complete all of them in M months with K workers. Also each worker can work only one patent at most, that is, if we use a worker for a patent, we can't use him anymore. Every single patent needs exactly one month to finish. And we are also given X, that is at most X workers can work in a month. We are finally given a string of length K denoting the workers. On odd month, workers with character 'O' can work and on even month, worker with character 'E' can work.

Solution: It's a greedy problem. Some key things to notice:

• Worker can work only one month (after working one month, current worker would no longer be available).
• Restriction in odd and even month.
• At most X workers can work on a single month.

We just need to calculate for each month, how many workers can be used to finish how many patents. As a single worker can finish single patent at a time and there is a restriction of even and odd month, we will simply iterate through all the months from 1 to M. Then for each month, we will select minimum(number of workers, X). This is the value of the number of patents we can get in a month. In odd month, the number of worker should be the number of 'O' in the string. Similarly for even month the number of workers would be the number of 'E' in the string. Every time we get minimum workers, we will discard that number from that particular type of worker as a worker can at most work 1 month, so he won't be available after he has done his part. We will store the value every time we count how many workers can work in every month, then simply check if the value is >= N or not. If >= N, then 'yes', else 'no'

Permutation and Palindrome: Given a string, we need to make that string a palindrome re-arranging it's characters and output the indices of those characters that made the palindrome string.

Solution: It's a greedy implementation problem. Some key things to notice:

• If the string length is even and at least one character has odd frequency, we can't make it a palindrome. ex: "aacb"; Here, 'c' and 'b' has frequency = 1, which is odd, and the string length is 4, which is even, so no palindrome can be made.
• If the string length is odd and at least two character has odd frequency, we can't make it a palindrome. ex: "acccb"; Here, 'a', 'b' and 'c' has frequency 1, 1 and 3 respectively, which is odd and the string length is odd. So we can't make a palindrome.

Now how to make the palindrome. We can simply check all the frequency of the characters. If frequency is even, then we will take first half of the position (index) in our first vector, say X.
And second half will go to vector Y. For even length, we won't have any odd frequency, so we will simply reverse Y and then merge it with X to get final output. For odd we need to get the odd element's index first. let's see for even length:

string = "abababab"
We will push the indices accordingly in a vector containing frequency of each character. So,

vector['a'] = 1 3 5 7
vector['b'] = 2 4 6 8

Now, we will iterate through the character's frequency. For 'a'
The first half will go to vector X, and second half will go to vector Y. So.
X = 1 3
Y = 5 7
Now, for 'b', similarly
X = 1 3 2 4
Y = 5 7 6 8

Now, reverse the Y and merge it with X to get the final result.
Final = 1 3 2 4 8 6 7 5

If we observe the indices, we can make this: "aabbbbaa"; which is a palindrome.}

Similarly, we can make this for odd length. There will be one character with odd frequency. we will take first index of that character from our vector[] array, then everything else follows exactly same.
Before merging Y with X, we need to push that odd frequency index to X first.

Car-pal Tunnel: In this problem we are given N tunnels and each consecutive tunnel has D meter distance. There are C cars each having same velocity S meter per second.

Each tunnel has a toll booth that takes Ai second to process a single car. At the time of processing one car, no car can come to that booth for processing. All the tunnels are linearly connected via these toll booths. We need to calculate the delay time between the first and last car after all of them is processed by all the toll booths.

Solution:

After a bit of observation, we will see that, the maximum time of a toll booth will be the distance between any two cars. So if there are C cars, then the answer will simply be (C-1)*maximum (Ai). Let’s see this case:

3
5 15 8
2 3 1

Here, 3 toll booth which have 5,15,8 second to process each car respectively. We have 2 cars each having velocity 1 meter per second. Each tunnel has 3 meter distance. So for a single car to cross a tunnel, it needs 3/1 = 3 second. Now let’s see, when the first car is being processed at the first booth, after 5 second, it will go out from the booth and second car will start processing. 

• 1 second goes, first car moves 1 meter, second car’s process time is also 1 sec.
• 2 second goes, first car goes 1 meter, second car’s process is 2 second.
• 3 second goes, first car is now at second booth for processing, second car’s 3 sec processing time is finished at first booth.

 So the distance between two cars will be 3 second.

Now, after 4,5,6 second, the second car will arrive at the second booth, but the first car is still being processed at that booth. So the second car will stop there. So our delay is now updated to 15 second,
as we clearly know, after processing of the first car (which will take 15 second for 2^nd booth) only then the second car can start processing. So the distance between them will be then 15 second. So the answer is 15*(2-1) = 15; [15 is the maximum toll booth time for a particular booth].

This observation is correct when C is equals to two. If there are more cars, then we need to keep the distance is calculation too. The delay is D/S for every car that takes D/S second to pass D meter distance. But if we happen to come to any case where D/S is greater than maximum of toll booth time, then we need to take the maximum (D/S, toll booth time). Notice this is applicable when there are cars more than two. If only two car is present, then maximum of toll booth is the correct solution.

CodeChef: January Long Challange 2018

Rectangle: Given four integers a, b, c and d, we have to determine if there's a rectangle such that the lengths of its sides are a, b, c and d (in any order) .

Solution: The easiest problem of this set. We just need to find 2 unique integer each having frequency 2. Or only a single integer having frequency 4, in case it is a square (also a rectangle).

Maximum Score: Given N integer sequences, each sequence having N integers, we need to find the maximum number we can get by taking only a single element from each sequence so that, element of i-th sequence is strictly greater than element of (i-1)-th sequence.

Solution: We will solve this in reverse order. First think, if we need to make out score maximum, we should always take the maximum number of the last sequence. After that we will take integer strictly less than that one from previous sequence. Say we have sequence:
1, 2, 10
9, 5, 12
2, 12, 8
We will take values from last sequence. First we took 12, maximum value of the last sequence. Then we come to previous sequence. We need to take value from this sequence which is strictly less than 12. Simple binary search using lower bound technique will give us the index of our desired value. If no such index is present then there is no solution. Of course we need to sort every sequence for this too.


K-Concatenation: Given an array A of size N, we need to make K copies of the array using concatenation of the array values, and then find the maximum subarray sum of that final array.

Solution: As N and K is so big, we can't simply concate  A by K times and then find the maximum subarray sum. So, what we can do? we can observe somethings.

First observation: If summation of every element of the array is positve, then the result is summation of all the elements * K.

Second observation:If all elements are negative, then the answer is the greatest number of all the elements.

Third observation: If there are mixed elements, then we can find largest subarray sum in 1-D space using Kadane's algorithm. Now for using Kadane, there is some observations too. If K == 1, we have simply array A, and with the help of Kadane, we can easily find largest subarray sum from there. Notice, if K > 2 what should we do? As we have mixed elements, no matter how large K is, only concatening 2 times is enough for us to find the largest sum. Ok, why 2 times? See a case A = 1 -2 1 and K = 4 suppose, then we get
1 -2 1 1 -2 1 1 -2 1 1 -2 1 ; if we use Kadane here, we will get 2 as our maximum sum.
1 -2 1 1 -2 1 ; if we use Kadane here, we will also get 2. As we are concatening, each time a new concatenation arises, it depends on the previous structure also. So by concatening 2 times, we will get what, by concatening K times, we will get same result.

Final observation: It is the most important of all. Notice these case: 

A = 1 1 -9 2 3 4, K =  3, so, we get:
B = 1 1 -9 2 3 4 1 1 -9 2 3 4 1 1 -9 2 3 4
Now, we will check first observation: total sum of A = 2, as K = 3 times, so we get = 6. We will store this value to storage1.
Now, for second observation, all elements are not negative, so we will store a big negative number like -9999999999999.... to storage2.
Third observation, as there are mixed elements, we will use Kadane's algo to find maximum subarray sum for 1 1 -9 2 3 4 1 1 -9 2 3 4  . And that is 11. So, storage3 = 11.
But let's see our final array : 1 1 -9 2 3 4 1 1 -9 2 3 4 1 1 -9 2 3 4; If we take this subarray, we get 13. So this is the final observation of this problem. We need to find two maximum values of our initial array A. We will call it forward_max and backward_max.
forward_max = 1 1 -9 2 3 4 = 9
backward_max = 1 1 -9 2 3 4 = 2
So, our storage4 will be:

forward_max+ S*(k-2) + backward_max ; S = summation of array A = 2

As, we took forward_max of our first part, backward_max of our last part, we are left with K-2 parts between. so we need to take all the remaining K-2 parts sum. Also notice, for final observation, K should be > 2
Our final result will be maximum of all the four storages.

Partition the numbers: Given N and X, we need to partition N numbers in such two sets, that both set will have equal sum after subtracting X from N elements(consider elements from 1 to N).

Solution: First we will calculate summation of N elements using series sum formula: N*(N+1)/2 . Now subtract X from this sum. So, sum = N*(N+1)/2 - X.
Now, if sum is odd then there is no solution, as we can't make an odd number partitioned in two disjoint sets. Also if N <= 3, there is no solution.
Now, when sum is even, we will make sum/2 using our 1 to N numbers without X. We will iterate from N to 1, each time we will check if needed sum is getting zero or not. if we can subtract a value, we will do that, and mark that value as set 1. One important thing is to notice that, while subtracting an integer, we need to check if the remaining sum can be represented by other available integers or not. There is may approach to solve this problem. Implement it however you want keeping some corner case in mind.

String Merging: You are given two strings A and B with lengths N and M respectively. You should merge these two strings into one string C with length N+M. Specifically, each character of C should come either from A or B; all characters from A should be in the same relative order in C as in A and all characters from B should be in the same relative order in C as in B.

Solution: This is a simple dynamic programming problem. Greedy solution won't help you there. What we need to do is simply find the longest_common_subsequence of String A and B. Then our result would be M + N - LCS(A,B). But first, finding LCS between A and B we need to modify A and B string in such a way that no same character right beside each other. If A = "aaaxyyyzza", we need to modify it as "axyza", as there is no same character right after one character. Then we will perform LCS operation in our modifued string and get the final result.