Unofficial Editorials NOV17

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 .

Link : https://www.codechef.com/viewsolution/16101208

5 Likes

How did you observe the trend for CHEFPALIN ? By your observation or by some brute force program?

Asking cause its damn tough thinking it that way. Everybody goes to “It must be logN” into these questions- especially after seeing initial pattern. It takes skill to come up with correct string and pattern manually. :slight_smile:

Actually I used a similar approach for CHEFPAL. First ‘a’ then ‘bb’ then check what was last, it was ‘b’ so this time it is ‘a’ but check how many consecutive ‘a’ did you print last(1 for this case), so print ‘aa’. Now it is b’s turn by checking how many b’s did we print last time(2) so append single ‘b’. Continue this and you will see a pattern “abbaab”. This string will continue forever. So append this string for all (n>8) n/6 times and lastly append n%6 characters to complete it.

Consider it my own version of kolakoski sequence. It took me 2 days to manually get to this solution. I was just going through different strings and I was like Eureka. And when I found it and the solution got accepted, I was so happy.

@trashmaster in question CHEFHPAL when the size of the string which is to be formed >=9 we have to use the optimal string build till 8 which is aaababbb but we modify this to include the MAGIC PATTERN

THAT IS: ababba
so the optimal string till 8 now becomes aaababba which is used for generating the future optimal strings . for n>=9

simply all those strings start from the above string aaababba and when the MAGIC PATTERN IS NOT INCLUDED due to size shortage irrespective of inserting additional ‘a’ char to the remaining places we can insert the front char from the MAGIC PATTERN ITSELF to make it more optimal but oen have to include the special cases till 8 manually BY OBSERVATION .This is purely an observation question .
link:my solution

Nice editorials! mate. :slight_smile:

Thanks . Inspired by you :slight_smile:

Time to place bets. Which of you is gonna cross 1k views first ? :stuck_out_tongue:

No idea @vijju123 !!

My second one will be posted soon…

Really appreciate the work you guys do. Especially when official editorials come out so late.

1 Like

Let’s see HAHAHAA :stuck_out_tongue:

Let the fun begin!!

Plus the fact that most of official ones are almost un-understandable in first read. Observations dropping from sky, non-intuitive things written just like that

"You can observe that we can express the graph completely in just log(M+20) spanning trees and- "

I still couldnt get the editorial of MARRAY, and was doomed w/o any unofficial explanation XD

3 Likes

Glad u found both our (me and trashmaster’s) editorials helpful @vijju123

1 Like

Of course, they are. Plus, I get to learn some nice tricks as well. Like, from your MARRAY editorial I found that my brute force got TLE cause it was recursive. Used the knowledge in SEGPROD and avoided recursion- last hour AC XDXD

U mean u owe an AC to me. !!! (just joking mate, noting personal).

PS:help someone on my post. He’s asking me about c++, which i don;t know much, i have mentioned u there. PLEASE!!

It was actually a brute force program , which checked for all the strings for particular value of n with a=2 and gave me the best solution for it . I saw the pattern above upto n~=24 after which it was taking way too much time. After this I verified my method manually for longer strings and finally came to this solution . Had a hackerkid feeling after this :stuck_out_tongue:

I didn’t “manually verified for strings longer than 24”. Rest same.

1 Like

XDXD. Looks like everybody thought in the same direction then :stuck_out_tongue:

1 Like

(Deeper of Fact) Everyone had to. :stuck_out_tongue:

Good approach mate.