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.