Villages and Tribes
It is a straight forward implementation and problem and we just need to count the respective number of a and b respectively .
An empty village will be of tribe A if it is between two villages of tribe A no matter how far they are .
What we can do is to to take the input of the string and while traversing through the string we can maintain a flag to determine if the last occupied village was of tribe A or B and count the number of empty villages in between .
If we encounter a village of the same tribe as before , we add this count of empty villages to the count of the same tribe else these villages belong to none .
Also it i must that the empty villages must be surrounded by occupied villages on both sides failing which the villages belongs to none.
In my implementation , instead of taking input of the whole string , I took character by character input .
Link : https://www.codechef.com/viewsolution/16048683
Chef goes Left Right
In this problem we have to simply check for the scenario that the sequence of numbers in the array are such that the every succeeding number reduces the distance between Reziba and Chef on boththe left side and the right side.
-Say Chef is currently at the left side of Reziba and the difference between the rating of that person from whom he asked is ldif . If any rating of the array that comes in the sequence next is less than the rating of Reziba then
ldif > (The rating of Reziba ‘r’)-(new number)
This must be true , otherwise we simply have overshot on the left side and violated the sequence .
The same is the case on the right side where
rdif > (new number)-(The rating of Reziba ‘r’)
must always we true .
Finally we check if the last number of the array is equal to the rating of Reziba .
If all these cases are true , only then the answer is yes.
Link : https://www.codechef.com/viewsolution/16063924
Periodic Palindrome Construction
With careful observation , we can see that to construct a string which is palindrome and has a period less than 3 will be impossible.
The simple reason is that we can’t have a palindromic string having length less than 3 without having all a or all b.
The possible period with p=2 are ab and ba . No matter what value of N we have , we can’t have a plaindromic string .
For the case of p=1 , we have to repeat a single character again and agai whih violates the property that there shouldn’t be all a or all b in the string.
All the other cases are valid and we can generate a string for them.
One simple solution of this problem is to create palindromic strings of size p with alternating a and b and repeating them n/p times for the output .
A simple look of yours can verify that all the parameters of the problem will hold .
-They will have a period p
-Concatenation of palindromic strings which are equal is also palindrome.
Link : https://www.codechef.com/viewsolution/16064778
Chef Hates Palindromes
Let us start with same trivial cases.
(1) if a==1
We can only use a single character which means that the whole string would be palindromic . So the length of the longest palindromic substring is n and is made up of ‘a’ repeated n times.
(2) if a>=3
If a is greater than or equal to 3 we can generate a string whose longest palindromic string is of size 1 i.e a sinle character.
It is because , we can place those characters repeatedly from ‘a’ to upto char(‘a’+a-1).
Now the most difficult among these cases is when a==2 .
Now some observations that I made using a program I wrote to generate a string satisfying the constarints .
(i) if n<=2
The maximum size of palindromic string would be 1 as the string would simply contain one 'a' for n=1 or 'ab'/'ba' for n=2.
(ii) if n<=4 and n>2
By carefully generating a string with 2 'a' in the beginning or single or double 'b' at the end , we can have a max size of .
(iii) if n<=8 and n>4
The maximum size of such a substring will be .
By using the brute force solution , I arrived at thr following configuration where the string is
'aaaba'+(0-3 b)
(iv) For all the other values of n
In this case , I observed a trend. First of all , all the strings started with 'aaaababba'.
Then we repeated the string 'ababba' of length a gain and again until we had until there wasn't enough space to fit this string i.e. the remaining size of the string to be filled was less than 6.
In this case we had two subcases
---- the remaining size to be filled was less than or equal to 3. Then I simply put 'a' , remaining number of times.
---- else I put the characters of the above repeated string until the size of the generated string became n.
So in this case , the maximum size of the longest substring came out to be **4** no matter how big the value of n was . We didn't add 'a' in the else case because then the palindromic substring would have size of 5 .
