You are not logged in. Please login at www.codechef.com to post your questions!

×

Unofficial Editorials November Long Challenge (Part 1)

11
1

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.

  1. Ith character is C
  2. 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

  1. countA means number of '.' characters being controlled by 'A'
  2. countB means number of '.' characters being controlled by 'B'
  3. A means No of 'A' in input
  4. B means No of 'B' in input
  5. 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 Code

Problem CLRL

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 code

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. :D

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 Code

Problem CHEFHPAL

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 Code.

As always, i wholeheartedly invite your suggestions and thank for your response to my previous editorials.

asked 13 Nov, 19:38

taran_1407's gravatar image

6★taran_1407
1.3k216
accept rate: 17%

edited 14 Nov, 00:03

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

(13 Nov, 19:45) taran_14076★

Like everytime , Nice work!

(13 Nov, 19:50) trashmaster4★

Thanks Mate!

(13 Nov, 19:51) taran_14076★

Waiting for second part and delay gift:)

(13 Nov, 19:53) droy05284★
1

Polygon pl0x <3

(13 Nov, 19:56) vijju123 ♦5★

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.

(13 Nov, 19:59) taran_14076★

@droy0528, second part posted. There's a bit of delay even in delay gift :)

(14 Nov, 00:03) taran_14076★

For PERPALIN if(N % P != 0) impossible...

(14 Nov, 17:01) vatsalsura3★

It is given in problem, that N%P = 0

(15 Nov, 00:41) taran_14076★
showing 5 of 9 show all

In 4th Ques: For A=2 & N>8 we can also repeat the string "aababb" and mod out extra characters to get a string of exactly N length with maximum palindrome sub-string length = 4 My Code

link

answered 13 Nov, 19:48

noxious_av's gravatar image

4★noxious_av
614
accept rate: 0%

edited 13 Nov, 19:53

1

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

(13 Nov, 19:50) taran_14076★

aabbab also does the job. Link.

(13 Nov, 20:02) ayan_nitd4★

There are total of 8-10 such patterns which do it. Though half are asymmetric reflections of each other.

(13 Nov, 20:16) vijju123 ♦5★

I have tested many strings using a tester program, generating strings using two characters 'a' and 'b', and found this.

Finally someone who took same approach :p

I was having difficulty in verifying my claim of-

The length is $\lceil{Log_2 N}\rceil$ string of length $N$ . Trouble because, well, testing for length around 16,17 was tedious.

I wrote a brute force program which checked for all strings of length 25,28,18 etc. I saw that strings of length 5 were possible, but the next part of proof is to prove its minimum.

And POOF, proof failed. I saw 4 was always the answer. Lol, just noted down the pattern and AC :p

Moral of the story: ITS GOOD TO BE LAZY SOMETIMES AND LET COMPUTER DO STUFF FOR YOU XDXD

link

answered 13 Nov, 20:11

vijju123's gravatar image

5★vijju123 ♦
11.1k314
accept rate: 18%

edited 13 Nov, 20:15

I too wrote a brute force algotihm which tested all substrings of length N in 2^N time (bitmask dp, 0 for 'a', 1 for 'b') and tested upto 24 using manacher's algorithm for palindrome string length)

(13 Nov, 20:17) taran_14076★

After ${2}^{N}$ thing in complexity, I didnt care for anything else and just wrote a $O({N}^{2})$ code snippet for palindrome detection.

It was still slow af....(13sec for length of 26) XD

(13 Nov, 20:21) vijju123 ♦5★

Hahaha I thought the same thing too ⌈Log2N⌉.. I got irritated and randomly kept pressing 'a' and 'b' and I got a huge string with maximum value four ..XD

(14 Nov, 00:14) simha3★

You were lucky. I decided spending half an hour messing with random string till i accepted defeat and made tester program :D

(14 Nov, 00:16) taran_14076★

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.

link

answered 14 Nov, 22:14

gautamcse27's gravatar image

3★gautamcse27
193
accept rate: 0%

Nice approach mate. I said there are many approaches, but saw first submission, that didn't use a string precomputed.

(15 Nov, 00:35) taran_14076★

for the CHEFHPAL problem I tried writing the possible palindrome of length 16 and found a pattern

A short Pythonic code
My code

link

answered 13 Nov, 21:05

skyhavoc's gravatar image

4★skyhavoc
1116
accept rate: 0%

edited 13 Nov, 21:25

Nice way. I had said there are many solution to this problem.

(13 Nov, 21:18) taran_14076★

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.

link

answered 14 Nov, 07:53

davislor's gravatar image

3★davislor
213
accept rate: 0%

edited 14 Nov, 21:01

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.. :-)


}
link

answered 14 Nov, 10:25

bhuvan9's gravatar image

2★bhuvan9
91
accept rate: 0%

@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.

link

answered 2 days ago

theintel's gravatar image

3★theintel
477
accept rate: 0%

Yes, if u take care of corner cases like P==2 or N == 1.

(2 days ago) taran_14076★

I wasn't able to solve CHEFHPAL and by the way it's a nice editorial bro and your approach is also simple and easy to understand

link

answered 13 Nov, 19:51

sagijagadish's gravatar image

3★sagijagadish
01
accept rate: 0%

Glad u found them helpful. :)

(13 Nov, 19:54) taran_14076★

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

(13 Nov, 20:04) sagijagadish3★

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

(13 Nov, 20:07) taran_14076★

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

(13 Nov, 20:13) vijju123 ♦5★

Ok Bro and keep up your Good work

(13 Nov, 20:14) sagijagadish3★
2

@sagijagadish when you write cin.tie(NULL) at the beginning of the code, compiler doesn't clear the output buffer every time it prints something. Whatever you try to print is stored in the output buffer and printed only once, when the execution of code is finished.

Bonus : Try using endl instead of '\n' in your code. 'endl' clears the buffer and add new line at the end.

(13 Nov, 20:25) priyanshukm6★

Thanks Mate. @sagijagadish

(13 Nov, 20:59) taran_14076★

Bonus: endl slows down execution a bit, try to use \n if possible xD

(14 Nov, 00:09) swetankmodi5★
showing 5 of 8 show all

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

link

answered 13 Nov, 21:17

mohit9999's gravatar image

3★mohit9999
213
accept rate: 0%

edited 13 Nov, 21:19

Sorry, but I'll see solutions later mate. Writing second part (even longer than the first. Though i hope anyone else on forum might be able to help you even before me.

(13 Nov, 21:22) taran_14076★

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

link

answered 13 Nov, 21:36

avik26091998's gravatar image

3★avik26091998
11
accept rate: 0%

Thanks Mate. Glad u liked.

(13 Nov, 21:40) taran_14076★

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

link

answered 14 Nov, 05:13

kunnu120's gravatar image

2★kunnu120
4558
accept rate: 6%

Glad u found them helpful!!.

(14 Nov, 19:27) taran_14076★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×11,984
×247

question asked: 13 Nov, 19:38

question was seen: 1,487 times

last updated: 9 hours ago