MAXPALI - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Practice

Setter: Daanish Mahajan
Tester: Tejas Pandey and Utkarsh Gupta
Editorialist: Taranpreet Singh

DIFFICULTY

Easy

PREREQUISITES

Observation

PROBLEM

You are given an integer N \geq 2. Construct string S of length N containing only lowercase Latin alphabets, such that

  • S contains at least 2 distinct characters.
  • The number of circular shifts of S which are palindromes is maximum among all strings of length N containing at least 2 distinct characters.

If there are multiple possible strings satisfying this condition, you may print any of them.

Note that a string of length N has exactly N circular shifts - even if some of them might be equal as strings, they are considered to be different shifts as long as they are obtained by shifting S by different amounts. For example, \verb+ababab+ has 6 circular shifts even though they only form 2 distinct strings between them (namely \verb+ababab+ and \verb+bababa+).

QUICK EXPLANATION

  • If N is a multiple of 4, we can repeat string 'abba' N/4 times, to obtain N/2 cyclic shifts which are palindrome.
  • Otherwise, if P \gt 2 is the smallest factor of N, then we can repeat string 'abbb... (P-1) times' N/P times, leading to N/P palindromic cyclic shifts of string.
  • For N = 2, we can choose string 'ab'

EXPLANATION

Draft proof that string with at least 2 distinct characters cannot have more than N/2 palindromic cyclic shifts.

Firstly, the fact that the string S must contain at least 2 distinct characters. For a string to be palindromic, each position p in the string is paired to position N-p+1 (excluding middle character for odd N). Considering each cyclic shift, the position p will be paired to each other position exactly once for odd N, and at least N/2 of the positions for even N.

So, we can prove that for any string containing at least 2 distinct characters, we cannot obtain more than N/2 palindromic shifts.

Idea

Now that we know that we cannot obtain more than N/2 palindromic cyclic shifts, let’s see for which N we can.

If N = 2, then only string 'ab' can be chosen, with no palindromic cyclic shifts.

If N is a multiple of 4, then we can choose string S as repeating string 'abba' N/4 times. This string would have exactly N/2 palindromic cyclic shifts.

One other approach we have for odd prime N is to choose the middle character 'b' and the rest all 'a'. We can see that it has exactly one palindromic cyclic shift, which would be the maximum possible.

For general N, we can find smallest prime P \gt 2 which divides N. We can repeat the above string exactly N/P times to obtain N/P palindromic cyclic shifts.

If getting WA, try N = 12. The correct string would be 'abbaabbaabba', not 'abaabaabaaba'.

TIME COMPLEXITY

The time complexity is O(N) per test case.

SOLUTIONS

Setter's Solution
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define F first
#define S second
int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t; cin >> t;
    while(t--){
	    int n; cin >> n;
	    if(n == 2)cout << "ab" << endl;
	    else{
		    if(n % 4 == 0){
			    string s = "aabb", ans = "";
			    for(int i = 0; i < n / 4; i++)ans += s;
			    cout << ans << endl;
		    }else{
			    for(int i = 3; i <= n; i += 2){
				    if(n % i == 0){
					    string s = "a", ans = "";
					    for(int j = 1; j < i; j++)s += "b";
					    for(int j = 0; j < n / i; j++)ans += s;
					    cout << ans << endl;					
					    break;	
				    }
			    }
		    }
	    }
    }
    return 0;
}
Tester's Solution 1
#include <bits/stdc++.h>
#include <stdlib.h>
using namespace std;


/*
------------------------Input Checker----------------------------------
*/

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;
            }

            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }

            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,' ');
}


/*
------------------------Main code starts here----------------------------------
*/

const int MAX_T = 1000;
const int MAX_N = 200000;
const int MAX_SUM_LEN = 200000;

#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)

int sum_len=0;

char use[2] = {'t', 'p'};

char get_random_char() {
    return use[(rand()%2)];
}

string generate_random_palindrome(int n) {
    string ad = "", ans = "";
    for(int i = 0; i < (n + 1)/2; i++) {
        char now = get_random_char();
        ans += now;
        if(n - 1 - i != i) ad += now;
    }
    if(ans[0] == ans[ans.size() - 1]) {
        if(ans[0] == 't') ans[ans.size() - 1] = 'p';
        else ans[ans.size() - 1] = 't';
        if(!(n&1)) ad[ad.size() - 1] = ans[ans.size() - 1];
    }
    reverse(ad.begin(), ad.end());
    ans += ad;
    return ans;
}

void solve()
{
    int n;
    n = readIntLn(1, MAX_N);
    sum_len += n;
    assert(sum_len <= MAX_SUM_LEN);
    if(n == 2) cout << "pt\n";
    else if(n%4 == 0) {
        string res = generate_random_palindrome(4);
        for(int i = 0; i < n/4; i++) cout << res;
        cout << "\n";
    } else {
        int found = 0;
        for(int i = 3; i < n; i += 2) {
            if(n%i == 0 && !found) {
                string res = generate_random_palindrome(i);
                for(int j = 0; j < n/i; j++) cout << res;
                found = 1;
            }
        }
        if(!found) cout << generate_random_palindrome(n);
        cout << "\n";
    }
}

signed main()
{
    srand(23957032);
    //fast;
    #ifndef ONLINE_JUDGE
    //freopen("input.txt", "r", stdin);
    //freopen("output.txt", "w", stdout);
    #endif


    int t = readIntLn(1, MAX_T);

    for(int i=1;i<=t;i++)
    {
        solve();
    }

    assert(getchar() == -1);
}
Tester's Solution 2
#include <bits/stdc++.h>
using namespace std;
 
 
/*
------------------------Input Checker----------------------------------
*/
 
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;
            }
 
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }
 
            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,' ');
}
 
 
/*
------------------------Main code starts here----------------------------------
*/
 
const int MAX_T = 1000;
const int MAX_N = 200000;
const int MAX_SUM_LEN = 200000;
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)


 
void solve()
{
    int n=readInt(2,MAX_N,'\n');
    if(n==2)
        cout<<"ab\n";
    else
    {
        if(n%4==0)
        {
            for(int i=1;i<=n/4;i++)
                cout<<"abba";
            cout<<'\n';
        }
        else
        {
            string s="";
            for(int i=3;i<=n;i++)
            {
                if((n%i)==0)
                {
                    for(int j=1;j<=i;j++)
                    {
                        if(j==1 || j==i)
                            s+='a';
                        else
                            s+='b';
                    }
                    for(int j=1;j<=n/i;j++)
                        cout<<s;
                    cout<<'\n';
                    return;
                }
            }
        }
    }
}
 
signed main()
{
    fast;
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #endif
    
    
    int t = readInt(1,MAX_T,'\n');
    
    for(int i=1;i<=t;i++)
    {    
        solve();
    }
    
    assert(getchar() == -1);
}
Editorialist's Solution
import java.util.*;
import java.io.*;
class MAXPALI{
    //SOLUTION BEGIN
    void pre() throws Exception{}
    void solve(int TC) throws Exception{
        int N = ni();
        if(N == 2){
            pn("ab");
            return;
        }
        int P = -1;
        if(N%4 == 0)P = 4;
        for(int p = 3; P == -1 && p <= N; p++){
            if(N%p == 0){
                P = p;
                break;
            }
        }
        char[] ch = new char[P];
        Arrays.fill(ch, 'a');
        ch[P/2] = 'b';
        ch[(P-1)/2] = 'b';//Only useful for P = 4, forming string abba
        StringBuilder ans = new StringBuilder();
        for(int i = 0; i< N; i++)ans.append(ch[i%P]);
        pn(ans.toString());
    }
    //Calculate the number of palindromic cyclic shifts in O(N^2)
    int count(String S){
        int N = S.length(), cnt = 0;
        S += S;
        for(int i = 0; i< N; i++){
            boolean good = true;
            for(int l = i, r = i+N-1; l< r; l++, r--){
                good &= S.charAt(l) == S.charAt(r);
            }
            if(good)cnt++;
        }
        return cnt;
    }
    //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 MAXPALI().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;
        }
    }
}

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

6 Likes

HI, so why we have to do this specific abba thing for those number which is divisible by 4?

Because it has N/2 cyclic shifts palindrome, which is the maximum number of cyclic shifts palindrome any string can have

1 Like

As another route the N/2 maximum possible palindromes, you can show that if a string is a palindrome, and the same string with a single-character shift is also a palindrome, all characters in the string must be the same. Thus in a string which is not all the same character, any shift that produces a palindrome must have an adjacent shift (say, one greater) that is not palindromic, giving the N/2 maximum.