Unofficial Editorials February Long Challenge (Part 1)

editorial
, , , , ,
1

Hello Guys,

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][1].

Without wasting much time, let’s start with editorials.

Problem : [CHEFCHR][3]

Problem Difficulty: Cakewalk

Problem Statement:

Given a String, find number of sub-strings of length 4, which can be reordered to form the word “chef”.

Solution:

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][4].

Link to my


[5].


### Problem : [CHEFPTNT][6]
#### 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

[7].

Problem : [PERMPAL][8]

Problem Difficulty: Easy

Problem Statement:

Given a string, permute the string to form a palindrome, and print the permutation.

Solution:

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.

Proof:
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


[9].

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!!


  [1]: https://discuss.codechef.com/questions/122739/unofficial-editorials-february-long-challenge-part-2
  [2]: https://www.codechef.com
  [3]: https://www.codechef.com/problems/CHEFCHR
  [4]: https://www.geeksforgeeks.org/window-sliding-technique/
  [5]: https://www.codechef.com/viewsolution/17377447
  [6]: https://www.codechef.com/problems/CHEFPTNT
  [7]: https://www.codechef.com/viewsolution/17360008
  [8]: https://www.codechef.com/problems/PERMPAL
  [9]: https://www.codechef.com/viewsolution/17244549
1 Like
2

Hi,
I tried solving PERMPAL. My approach to solving it:
Create a function that will return a list with final indexing of the string as question required for only EVEN string i.e. length of the string is even.
If the string is even then print it.
If the string is odd then find the char that will come in the middle save it(it’s original index) and delete it from string and call the function on it. Increment by one in the ans for all position greater than equal to half of the length of the string.

My code

 

for _ in range(int(input())):
  a=list(input())
  flag=0
  mid=0
  if len(a)%2 == 1:
    flag=1
    for i in range(len(a)):
      if a.count(a[i])%2==1:
        mid=i
        del a[i]
        break
      
  
  def pal(a): #Return pllendrom for even 
    if (len(a))==1:
      print(1)
      return 0
    cunt=list() #Actual result list, also used to store count of ch in string 
    b=list() #Temp list ch,actual index,result index
    for i in range(len(a)):
      b.append([a[i],i,0])
    b.sort()
    i = 0
    
    while True:
      if i==len(a) :
        break
      cunt.append(a.count(b[i][0]))
      if (cunt[-1]%2 == 1) : # If bot pal
        print(-1)
        return 0
        break
        
      i=i+cunt[-1]
    
    for i in range(len(cunt)):
      for j in range(cunt[i]//2):
        b[sum(cunt[:i])+j][2]=j+(sum(cunt[:i])//2)+1
        b[sum(cunt[:i])+cunt[i]-j-1][2]=len(a)-j-sum(cunt[:i])//2
          
    cunt=[]  
    b=sorted(b,key=lambda x:x[1])
    for i in range(len(b)):
      cunt.append(b[i][2])
    return cunt
  R=pal(a)
  if R!=0:
    if flag== 0:
      for i in range(len(R)):
        print(R[i],end=" ")
    else:
      R.insert(mid,'_')
      for i in range(len(R)):
        if R[i]=='_':
          print((len(a)//2)+1,end=" ")
        elif R[i]>=(len(a)//2)+1:
          print(R[i]+1,end=" ")
        else:
          print(R[i],end=" ")
      print("\n")
      
</pre>

I was not able to find the mistake in this code, can anyone please help me here, the CodeChef IDE returned WA when I submit it.
Thank you

3

P.S. : I am a newbie and I didn’t know where to find the community discussion so I just posted my query here. Please don’t mind it.Thanks