Unofficial Editorials November Long Challenge (Part 1)

same approach @taran_1407 here’s the code in c++
https://www.codechef.com/viewsolution/16205791

It Took me 2 days to solve CHEFHPAL…and find the pattern for A = 2 and N > 8.

Here’s my soln - Soln

And Nice Editorial Bro!!!

I couldn’t solve the CHEFHPAL problem, I read your editorial and now I understand it!!

And @taran_1407 thank you so much for spending time to write these helpful editorials!!

For CHEFHPAL, the proof of correctness is by exhaustion. For any value of a but 2, the answer is trivially "aaa..." or "abcabc...".

For a = 2, let’s look at the possibilities. The length-two palindromes are aa and bb. All eight three-letter strings contain at least one two-letter palindrome, or are length-three palindromes themselves, so two is minimal. We can therefore return the strings aab and aabb.

The three-letter palindromes are aaa, bbb, aba and bab. All five-letter strings contain at least one of these, as we can see by noticing that any three-letter string that contains no three-letter palindrome is aab, either with as and bs switched, backwards, both or neither. So we can just look at one and our impossibility proof will apply to all four. (aab is to bba as aabb is to bbaa, to baa as aabb is to bbaa, etc.) We have to start from a string symmetric to that and try to add two more letters to it. If we add a, we get aaba, if we add ba, we get aabba. If we add bb, we get aabbb. Therefore, three is minimal, and we can return aaabb, aaabab, aaababb, and aaababbb.

For n > 8, there is no way to fit three more as or bs before, after, or between aaa and bbb without getting a palindrome at least four letters long. So, four is minimal. The way to verify that "abaabbabaabb..." is optimal is to list all the substrings of length five and length six, and verify that they are not palindromes. Any odd palindrome of length greater than five would need to have a palindrome of length five in the center, wrapped by a pair of symmetric segments like a...a or ab...ba. Any even palindrome of length greater than six would need to have a palindrome of length six in the center. Since no such segment of length five or six exists in the string, it cannot contain any palindromes longer than four letters. So it is optimal.

1 Like

Here is my simple approach to PERPALIN.
if(P>N || P<3){
“impossible”.
}
else{
1. generate a string of length P with all characters as same(let ‘b’). // string s(P,‘b’)
2. replace first and last characters with another character (let ‘a’). // s[0]=s[P-1]=‘a’
//Now we have a palindrome with length P;
3. print string s , N/P times. /* int r=N/P; for(int i=0;i<r;i++) cout<<s;*/
4. done // we generated string with period P… :slight_smile:

}
1 Like

I did it in complete lazy way just find out the pattern for the length of string 11,12,13,14,15 and 16 then i continued it then i noticed there was repetition of some pattern i.e., for 11 to 15,17 to 21,23 to 27 and so on add “bbaa” next 12 to 16,18 to 22 and so on add “baab” next 13 to 17,19 to 23 and so on add “aaba” next 14 to 18 ,20 to 24 and so on add “abab” similarly for 15 to 19 add “babb” and last 16 to 20 and so on add “abba”.you will get always ans 4 for string having only a & b for length having greater than 8.
Here is my solution link text
if you like please upvote me.

3 Likes

@taran_1407
Solution to problem PERPALIN can be simplified:

Create array[p] and a[0]=a[p-1]=‘a’
Then fill the rest of the elements with ‘b’
And finally print the array (n/p) times.

This saves some ‘increase’ hassle, probably a bit of memory too.

1 Like

i read ur tutorial for 1st problem…didn"t budge anything :frowning:

PS:2nd part will be posted soon, maybe within an hour Sorry for delay.
Second part May also include POLY as delay gift. :slight_smile:

Thanks for sharing… I had said, there are many strings that may work. I found the one mentioned above. :slight_smile:

1 Like

Like everytime , Nice work!

Thanks Mate!

Waiting for second part and delay gift:)

Glad u found them helpful. :slight_smile:

Polygon pl0x <3

1 Like

Not sure. I haven’t solved the problem myself…

Asking someone to explain it to me. (while giving credit)

Though i would try my best to convince that person.

aabbab also does the job. Link.

I have a doubt @taran_1407

I use the codeblocks ide

whenever i use this code snippet

ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);

Output is printed after I Give all the Inputs(if there are 4 testcases after i give all tc inputs o/p is printed)

But when i don’t use it Output is Printed after i give the each t.c i/p

Can you tell me why this happens ??

I’m sorry i can’t. I don’t code often in c++. Maybe @vijju123 may be able to help. :slight_smile:

I think you should google this out. That will be better than anything I can explain :smiley: