THREE - Editorial

editorial
, , ,
22

CodeChef: Practical coding for everyone here is my code.

23

My code outputs 2 for this , which is wrong , thanks for helping out man !

24

https://www.codechef.com/viewsolution/40800660

Have a look at my solution

25

Wow I could not come up with logic that there will be always sufficient chars for middle position of palindrome.
I greedily distributed pair of same characters and odd characters and then took the min of both.
I just didn’t think of proving that we can always have sufficient odd chars to satisfy pairs of same chars.

26

Nice way to prove sufficiency condition. I could not think of this.

27

This Question sounds difficult but its very easy if we look out in view of math.
Lookout my approach - Solution

28

can i please get a code review : CodeChef: Practical coding for everyone

  1. I counted pairs

  2. then i counted singles from the remaining

  3. max palin = min (pairs, singles) [obvious]

  4. but for special cases as in aabbcc
    pairs =3, singles =0
    i break 1/3 of total pairs and form singles from them and satisfy the remaining pairs !!!

where did i mess up ??

29

@sar_1 you didn’t account for the left over pairs , for example take 6 pairs and 2 singles , we can form 2 palindromes from , 2 pairs and 2 singles. After that we still have 4 pairs left , which we can use to form 2 more palindromes.

Just checked your code , everything was ok , just update pairs value (pairs -= ans;) after the ans calculation.

Here is your modified code , just added a line.

www.codechef.com/viewsolution/40871938

1 Like
30

Hey, I have also think of the greedy approach. And from the author’s explanation I am able to understand that total number of unselected characters are N - 2 * Y , But can you pls explain why there are sufficient single characters available to use as middle one in palindromes.

31

from the author’s explanation I am able to understand that total number of unselected characters are N - 2 * Y , But can someone pls explain why there are sufficient single characters available to use as middle one in palindromes.

32

@priyanshi_garg

Y = min( X , N/3 ) where , N is the length of string

=> Y max value is N/3

=> remaining characters , let’s call it R = N - 2 * Y .

=> min value of R occurs when Y is max , because we are subtracting 2*Y.

=> min value of R = N - 2Y = N - 2 * (N/3) = N - (2N)/3 = (3N - 2N)/3 = N/3

=> So , there are atleast N/3 characters remaining in any case.

1 Like
33

What will be the number of pairs formed according to the editorial?
For this case: ‘cccaabdd’.
How it will give 3 when only 2 can be formed ‘ccc’ and ‘aba’ or ‘dbd’

34

Thankyou @infinite_king for explanation, finally it becomes clear to me.

1 Like
35

@numberdaar
According to editorial for string “cccaabdd”,

No. of pairs are 3
1st pair = “cc”
2nd pair = “aa”
3rd pair = “dd”

So palindromic strings are 2 but the number of pairs that we can extract from input string is 3.

36

One way of thinking is as follows:
Number of pairs can either be greater than *N/3* or less than or equal to it.
Case I: #of Pairs <= N/3,
Then clearly, we have (2*(#of Pairs)) involved in pair and we will, guarenteed, have at least N/3 “orphaned-characters”. So each of the pairs can grab one such orphaned character, hence complete the requirement to earn a gold coin each. Therefore number of pairs is the number of golds. Note that, to get a gold a pair(of same characters) is a MUST. Since, by now we will have exhausted all the pairs, hence will not be able to withdraw anymore gold. So in this case the answer will be the #of Pair.
Case II: #of Pair > N/3,
number of character involed in pairs > 2N/3
So after N/3 pairs have grabbed their third wheel, we will not be left with any characters at all. (2*(N/3) + N/3 = N) , therefore we will have exhausted all the characters in our string. Hence in this case the answer will be N/3.

One last question, why choose N/3 as a parameter to form cases? This should be clear by now, since we can have at max N/3 pairs.

37

Yes, pairs are 3 but the palindromic strings are only 2 with 3 characters in each, so to earn a coin first need to select the 3 characters from the string and try to form a palindrome if it forms then a coin is earned.
So earning of a coin depends on the 3 letters palindromic string but on the pairs.

39

Nice Approach and clean code.

40

yes i found that out… thanks a lot bro :smiley: :smiley:

1 Like
41

how it is 3 can you please explain

1 Like
42

aaa
cbc
cac

Therefore , ans is 3