THREE - Editorial

editorial
, , ,
12

What is Ur answer for??
1
aaaabcccc

2 Likes
13

My code says answer is 2.

14

Ans should be 3

15

Yea, you are right.

1 Like
16

why am I getting WA on subtask 3 task 4
code : CodeChef: Practical coding for everyone

17

Hello can anybody point out where is the problem in my approach-
-First, added 1 coins for each 3 consecutive characters.
-Second, take the remaining characters from the previous operation (1s and 2s) added the minimum of them to the answer.

         cin>>str;
    	M mp;
    	LP(i,str){
    		mp[i]++;
    	}
    	cnt=0;
    	V v;
    	LP(i,mp){
    		cnt+=i.second/3;
    		if(i.second%3)v.pb(i.second%3);
    	}
    	joker(v)
    	cnt1=0,cnt2=0;
    	LP(i,v){
    		if(i==1)cnt1++;
    		else cnt2++;
    	}
    	cout<<cnt+min(cnt1,cnt2)<<endl;
18

In your code, one part is
int x = s.length()-(2cnt);
int y = cnt-x;
y = (2y)/3;
cout<<min(cnt, x+y)<<e;

Can you please tell me what is the happening when cnt<x? what is the significance of x+y at the time?

20

3

21

can anyone please give some edge test case for this problem if there are any. my code is giving correct output for different input string but after getting it submit i am getting WA.

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