THREE - Editorial

PROBLEM LINK:

Practice
Contest: Division 1
Contest: Division 2

Setter: Sahil Chimnani
Tester: Rahul Dugar
Editorialist: Taranpreet Singh

DIFFICULTY

Simple

PREREQUISITES

Observations.

PROBLEM

Given a string S of lowercase English characters, you can obtain a coin by choosing and removing three characters from the string, if the three characters can be reordered to form a palindrome.

Find the maximum number of coins you can obtain.

QUICK EXPLANATION

The only condition removed characters should satisfy is that at least two of them must be the same. So the answer is bounded by X = \sum_{c} \lfloor \frac{f_c}{2}\rfloor where f_c denote frequency of character c in S. Also, for a string of length N, there cannot be more than N/3 operations.

So the number of gold coins obtained is min(X, |S|/3)

EXPLANATION

To get a gold coin, we always remove three characters from S, so we cannot obtain more than \displaystyle \Big \lfloor \frac{|S|}{3} \Big \rfloor. So \displaystyle \Big \lfloor \frac{|S|}{3} \Big \rfloor is an upper bound on answer.

Now, let’s see palindrome condition implies. Since we can rearrange three characters in any order, and then we need first character to be same as third character, this means that all three characters cannot be distinct.

This is it, every time we select three characters, atleast 2 of them must be same. Lets ignore middle character for now and consider counting the number of pairs of same characters they can form if no element appears in more than one pair. If a character c appears f_c times, we can form \displaystyle \Big \lfloor \frac{f_c}{2} \Big \rfloor pairs. Each of these pairs can be pick with any third character and this would form a valid triplet.

Hence, the number of pairs also impose an upper bound on the maximum number of gold coins attainable. Formally, if \displaystyle X = \sum_{c \in A} \Big \lfloor \frac{f_c}{2} \Big \rfloor denotes the total number of pairs of same characters, Then we cannot obtain more than X coins. Here A denotes the set of characters.

Considering both conditions, the maximum achievable gold coins is given by \displaystyle \text{min}\Big( \sum_{c \in A} \Big \lfloor \frac{f_c}{2} \Big \rfloor, \frac{|S|}{3}\Big)

There exists an easy construction to actually find triplets.

Construction

Select P = \displaystyle \text{min}\Big( \sum_{c \in A} \Big \lfloor \frac{f_c}{2} \Big \rfloor, \frac{|S|}{3}\Big) pairs, and add rest of the characters into a reserve. Now for each pair, pop out one character from reserve, and each pair along with popped character forms a valid pair.

Figure out why reserve contain sufficient characters.

Fun fact: Prove why printing |S|/3 gets accepted for first subtask.
Bonus: Does there exist a lower limit C such that the answer is always |S|/3 for fixed A = 26 and |S| \geq C

TIME COMPLEXITY

The time complexity is O(|S|+A) where A = 26

SOLUTIONS

Setter's Solution
Tester's Solution
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
const int mod=998244353;
//const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
 
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
	uniform_int_distribution<int> uid(0,lim-1);
	return uid(rang);
}
 
int powm(int a, int b) {
	int res=1;
	while(b) {
		if(b&1)
			res=(res*a)%mod;
		a=(a*a)%mod;
		b>>=1;
	}
	return res;
}
 
long long readInt(long long l, long long r, char endd) {
	long long x=0;
	int cnt=0;
	int fi=-1;
	bool is_neg=false;
	while(true) {
		char g=getchar();
		if(g=='-') {
			assert(fi==-1);
			is_neg=true;
			continue;
		}
		if('0'<=g&&g<='9') {
			x*=10;
			x+=g-'0';
			if(cnt==0) {
				fi=g-'0';
			}
			cnt++;
			assert(fi!=0 || cnt==1);
			assert(fi!=0 || is_neg==false);
 
			assert(!(cnt>19 || ( cnt==19 && fi>1) ));
		} else if(g==endd) {
			if(is_neg) {
				x=-x;
			}
			assert(l<=x&&x<=r);
			return x;
		} else {
			assert(false);
		}
	}
}
string readString(int l, int r, char endd) {
	string ret="";
	int cnt=0;
	while(true) {
		char g=getchar();
		assert(g!=-1);
		if(g==endd) {
			break;
		}
		cnt++;
		ret+=g;
	}
	assert(l<=cnt&&cnt<=r);
	return ret;
}
long long readIntSp(long long l, long long r) {
	return readInt(l,r,' ');
}
long long readIntLn(long long l, long long r) {
	return readInt(l,r,'\n');
}
string readStringLn(int l, int r) {
	return readString(l,r,'\n');
}
string readStringSp(int l, int r) {
	return readString(l,r,' ');
}
 
void solve() {
	string s=readStringLn(1,100000);
	vi cnt(256,0);
	for(char i:s) {
		assert('a'<=i&&i<='z');
		cnt[i]++;
	}
	int sol=0;
	for(int i:cnt)
		sol+=i/2;
	cout<<min(sz(s)/3,sol)<<endl;
}
 
signed main() {
	ios_base::sync_with_stdio(0),cin.tie(0);
	srand(chrono::high_resolution_clock::now().time_since_epoch().count());
	cout<<fixed<<setprecision(7);
	int t=readIntLn(1,10);
//	cin>>t;
	fr(i,1,t)
		solve();
	assert(getchar()==EOF);
#ifdef rd
	cerr<<endl<<endl<<endl<<"Time Elapsed: "<<((double)(clock()-clk))/CLOCKS_PER_SEC<<endl;
#endif
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class THREE{
	//SOLUTION BEGIN
	void pre() throws Exception{}
	void solve(int TC) throws Exception{
	    String S = n();
	    int A = 26;
	    int[] f = new int[A];
	    for(int i = 0; i< S.length(); i++)f[S.charAt(i)-'a']++;
	    int count = 0;
	    for(int freq:f)count += freq/2;
	    pn(Math.min(count, S.length()/3));
	}
	//SOLUTION END
	void hold(boolean b)throws Exception{if(!b)throw new Exception("Hold right there, Sparky!");}
	static boolean multipleTC = true;
	FastReader in;PrintWriter out;
	void run() throws Exception{
	    in = new FastReader();
	    out = new PrintWriter(System.out);
	    //Solution Credits: Taranpreet Singh
	    int T = (multipleTC)?ni():1;
	    pre();for(int t = 1; t<= T; t++)solve(t);
	    out.flush();
	    out.close();
	}
	public static void main(String[] args) throws Exception{
	    new THREE().run();
	}
	int bit(long n){return (n==0)?0:(1+bit(n&(n-1)));}
	void p(Object o){out.print(o);}
	void pn(Object o){out.println(o);}
	void pni(Object o){out.println(o);out.flush();}
	String n()throws Exception{return in.next();}
	String nln()throws Exception{return in.nextLine();}
	int ni()throws Exception{return Integer.parseInt(in.next());}
	long nl()throws Exception{return Long.parseLong(in.next());}
	double nd()throws Exception{return Double.parseDouble(in.next());}

	class FastReader{
	    BufferedReader br;
	    StringTokenizer st;
	    public FastReader(){
	        br = new BufferedReader(new InputStreamReader(System.in));
	    }

	    public FastReader(String s) throws Exception{
	        br = new BufferedReader(new FileReader(s));
	    }

	    String next() throws Exception{
	        while (st == null || !st.hasMoreElements()){
	            try{
	                st = new StringTokenizer(br.readLine());
	            }catch (IOException  e){
	                throw new Exception(e.toString());
	            }
	        }
	        return st.nextToken();
	    }

	    String nextLine() throws Exception{
	        String str = "";
	        try{   
	            str = br.readLine();
	        }catch (IOException e){
	            throw new Exception(e.toString());
	        }  
	        return str;
	    }
	}
}

VIDEO EDITORIAL (English):

VIDEO EDITORIAL (Hindi):

Feel free to share your approach. Suggestions are welcomed as always. :slight_smile:

5 Likes

If the answer for the problem is X and if X <= \frac{|S|}{3} and X <= \sum \frac {f_c}{2} ,
then why is either X = \frac{|S|}{3} or X = \sum \frac {f_c}{2} (and more specifically, minimum of those two) ?

I feel like I got next to zero help from the editorial; kindly explain the “figure out yourself” part of the editorial.

5 Likes

Pick Y = min(X, |S|/3) pairs from pairs found. It is guaranteed that the multiset of characters not selected is N-2*Y. Since Y \leq N/3, N/3 \leq N-2*Y guaranteeing availability of at least Y characters for each selected pair

5 Likes

Is the lower limit C = 26 * 3?

Damn! I am was solving a different form of the problem. I thought we can’t rearrange the chosen characters(order remains the same as in the given string) . I was doing something with prefix and suffix sums over the left and right subarray and then, pairing them together. Has anyone thought of this question?

My approach was kinda same.
https://www.codechef.com/viewsolution/40849316

I’ve used a different approach and got AC , please have a look on my solution and let me know if there are some test cases for which my solution gives WA .
Solution : Solution: 40836677 | CodeChef

Yes, from the question language it seemed like that

Almost got the question, missed some tiny details.
Submission-WA

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

can anybody tell me what’s wrong with my approach and the test cases for it will fail.

even I had used somewhat of your approach but got WA in some cases Solution: 40843081 | CodeChef
Could you help me in rectifying my code

What is Ur answer for??
1
aaaabcccc

2 Likes

My code says answer is 2.

Ans should be 3

Yea, you are right.

1 Like

why am I getting WA on subtask 3 task 4
code : Solution: 40835744 | CodeChef

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;

In your code, one part is
int x = s.length()-(2cnt);
int y = cnt-x;
y = (2
y)/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?

3

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.