Hello Guys
I have divided problems into posts according to difficulty. Hope u all don’t mind this. 
This is the part 1 of two posts of unofficial editorials for November Long Challenge.
For editorials of problems CSUBQ and SEGPROD, click here.
This post has editorials for problems VILTRIBE, CLRL, PERPALIN and CHEFHPAL (so many in single post 
).
Problem VILTRIBE
Problem Difficulty : Cakewalk
Problem Explanation
Given a string consisting of characters ‘A’, ‘B’ and ‘.’, Output number of characters controlled by A and B. Character C controls ith character if either of following condition is true.
- Ith character is C
- Ith character is ‘.’ and the character on both side is C (jumping all the ‘.’ characters in between)
Solution
Just do as they asked in the problem.
Maintain a character C (initialised to any other character of your choice other than ‘A’, ‘B’ and ‘.’) which denote the previous controlling character encountered.
Here, we are going to count characters satisfying above of the two conditions separately Beacuse if we choose to count them together, there’s a risk of counting characters satisfying first condition twice, which is certainly not what we want.
For example of this, try input A.A.A…B.B.B
Maintain counter variables countA, countB, A, B and last where
- countA means number of ‘.’ characters being controlled by ‘A’
- countB means number of ‘.’ characters being controlled by ‘B’
- A means No of ‘A’ in input
- B means No of ‘B’ in input
- last means index of last controlling character. (Initialised to -1)
After all this, I guess my solution is straight forward to understand. In case you feel i should clarify any doubt, Just drop a comment.
Here’s a link to my
[3]
### Problem [CLRL][4]
#
### Problem difficulty:Simple
#
#### Problem Explanation
Given an array of numbers, we are supposed to verify whether the array is valid based on given condition.
#### Solution
The most simple way to think about this as following:
Here, Ri denote ith element of given array.
**The given array is valid if and only if:**
For every pair of consecutive numbers R(i-1) and Ri:
If R(i-1) < Ri : R(i-1) < all elements after ith index. (type 1)
If R(i-1) > Ri : R(i-1) > all elements after ith index. (type 2)
That's it. we just need to implement it.
I have used two boolean to check if any pair of type 1 and type 2 is found.
Basic case : N <= 2 Answer is "YES" No matter what the elements are. (Be sure to input them or you'll get WA) For explanation, i set reward if anyone finds such a case with N <= 2 where answer is NO, He or she'll be appreciated in my next post. Good Luck :)
Use max and min variable to keep record of upper and lower bound.
loop from start+1 to end
compare elements (i-1) and ith position.
if (i-1)th < ith
if(type1 is not found yet) found1 = true. min = ith element
if type 2 is found && ith element > max, valid = false
min = Math.min(min, prev)
Other case works the same way. Just swap type 2 with type 2, min and max and invert the inequalities. if valid print "YES" else "NO"
Link to my
Problem PERPALIN
Problem Difficulty : Simple
Problem Explanation
Given two integers N and P, construct a palindrome string of length N in which every ith character is same as (i+P)th character using only characters ‘a’ and ‘b’. If not possible, print impossible.
Further, String should not contain all a or all b.
Solution
First thing to observe is that in case P == 1 OR P == 2, ans is impossible.
Reason
if P == 1, valid strings are only aaaaa… (upto N times) or bbbbb… (upto N) times. But as Chef dislikes these strings, ans is impossible.
if P == 2, the only valid strings can be abababab or babababa. Since N is always divisible by P, N is not odd in this case, and when N is Even, first and last character of string is never same. So we cannot get a palindrome of period length 2. ans is impossible.
In all other cases, Answer always exist.
Here, there exists many solutions for this problem. But I’m gonna tell which approach i used.
Small string of length P will be repeated N/P times to generate the required string of length N.
I generated small string as:
In case P is odd, just make string ababababa till length P
If P is even: (P+2)/4 times ‘a’ + (P/4)*2 times ‘b’ + (P+2)/4 times ‘a’ (Integer division)
You may ask why i chose such a complex way to generate this string for even P. The reason is, My Choice. 
It always make palindrome string for even length >= 4.
First few strings for even P would be abba, aabbaa, aabbbbaa, aaabbbbaaa
Just see first half of strings => ab, aab, aabb, aaabb. My pattern make strings like that, increasing a and b one by one and then reverse it and append it to original one.
Hope i didn’t confused you with my small rant. Feel free to ask.
Here’s a link to my
[7]
### Problem [CHEFHPAL][8]
#
### Problem Difficulty : Easy
#
#### Problem Explanation
Given two integers N and A, construct a string of length N using only first A characters, minimizing length of longest palindrome substring. 2<=A<=26
#### Solution
First thing to observe here is that for A > 2, One of the correct answer is "1 abcabcabc..." upto N characters because this string cannot have any palindrome of length greater than one.
So that just leaves **A == 2, The Special Case**
Here, I am making a statement, Do tell me any counter example and you will be appreciated.
**For N > 8, there is always a string whose maximum palindrome sub-string length is exactly 4**.
I have tested many strings using a tester program, generating strings using two characters 'a' and 'b', and found this. An alternative solution is most welcome. (If you want the tester program i used, I'd recommend you to make it yourself, it would boast your skills. :) )
The reason that this works is that for a palindrome of length >= 4, we need two pair of character matching (first with last, second with second last), so we are creating a single mismatch every time.
We can't avoid palindrome length 4 after N >= 8 because consider a string aaababbb, now if we append 'a', palindrome length is 5, if you append 'b', palindrome length becomes 4.
See string babbaababbaa. This string always create exactly one mismatch for substring of length > 4. (You can always find such a string with hit and trial).
So, I simply stored results for N <= 8 in an array.
So, i just check A>2, if yes, print abcabcabc... upto n characters.
else if N <= 8, print answer pre-calculated (Or calculate using program if you can)
else append above string repeatedly to output string till output length is exactly N. Remove extra characters in case length > N.
Here's a link to my
9.
As always, i wholeheartedly invite your suggestions and thank for your response to my previous editorials.
