Writing the last set of editorials, I present the biggest set of unofficial editorials of mine till date with 8 editorials. Hope you like them. As always, please give your review.
This is part one of set, containing editorials for CHEFCHR, CHEFPTNT and PERMPAL.
For other editorials, refer CARPTUN, BROCLK and POINPOLY [here].
Without wasting much time, let’s start with editorials.
Problem : [CHEFCHR]
Problem Difficulty: Cakewalk
Given a String, find number of sub-strings of length 4, which can be reordered to form the word “chef”.
Well, we can calculate this using the simplest method- starting at each position, run a loop from current char to next 3 chars, and put them in a vector and check if Chef word can be made and get AC.
Time Complexity O(N*4).
Now, we can also learn the concept of sliding window from this problem.
In this problem, we are required to count instances, such that four characters starting from this position can be reordered to form chef.
One thing to note here is that, we can just check if frequency of c, h, e and f should be 1, to be able to reorder.
Also, window size given in problem is 4 (We need to check 4 characters only).
So, we make a frequency array, and increase frequency of first 4 characters in this array. Now, we need to see that, for moving one position forward, we need to delete the leftmost character and add current character. This is simply increase frequency of current character and reducing frequency of (i-4)th character.
Time Complexity Now becomes O(N).
That’s all. For more details upon Sliding window Technique, refer [this].
Link to my
. ### Problem : [CHEFPTNT] #### Problem Difficulty: Simple ### Problem Statement: Given Number of patents, Number of workers, Number of months and X, we need to determine if we can complete the work, subject to following conditions. - Worker works on a project case once only - Some worker work only in odd months and some work only in even. - Every month, No more than X workers work on project. ### Solution: We can see that only the count of workers working in odd and even months respectively is relevant to our problem. We just need to check if N patent cases can be solved. We will determine the number of patent cases which can be solved using given workers satisfying above conditions. Suppose E denote no of workers working in Even months and O same for Odd months, We do the following. count = 0 loop from 1 to M: if i is odd: count += min(X, odd); odd -= min(X, odd); //No worker can work twice in same project, thus removing them. else: count += min(X, even); even -= min(X, even); if count >= N, "YES" else "NO" That's all. I know the problem statement seems scary at first sight, but we should try to reduce long statements into key points, just like the problem statement above. Link to my
Problem : [PERMPAL]
Problem Difficulty: Easy
Given a string, permute the string to form a palindrome, and print the permutation.
Well, let’s cover the impossible case first.
- If length of given string is odd, exactly one character must have odd frequency and all other characters should have even frequency.
- If length of given string is even, Every character should have even frequency.
If this condition is not satisfied, simply print -1.
By definition of palindrome, character at ith position should also be at (N-i+1)th position. This way, every character will have even frequency.
If length of string is odd, the middle character is the character with odd frequency.
Now, we are sure that a palindrome string can be formed by permuting the characters. Now, various strategies permuting the string will work. Following is mine.
Looping from ‘A’ to ‘Z’, say C, whenever frequency is greater than 0, assign one C, the leftmost unassigned position, say i, and another C, the position (N-i+1).
If ever the frequency of a character is odd, assign it middlemost position.
That’s all, print the permutation.
For implementation details, refer my
. This brings end to part 1, Hope you liked them. Feel free to post your queries. ### PS: Bonus question to second problem ### In same problem, There are three type of workers, one working only on odd months, one working only on even months and Third type of workers work in all months. Rest conditions of problem remains same. Enjoy coding!! : https://discuss.codechef.com/questions/122739/unofficial-editorials-february-long-challenge-part-2 : https://www.codechef.com : https://www.codechef.com/problems/CHEFCHR : https://www.geeksforgeeks.org/window-sliding-technique/ : https://www.codechef.com/viewsolution/17377447 : https://www.codechef.com/problems/CHEFPTNT : https://www.codechef.com/viewsolution/17360008 : https://www.codechef.com/problems/PERMPAL : https://www.codechef.com/viewsolution/17244549