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.