 # DISPAL Editorial

Setter: Kanhaiya Mohan
Tester: Nishank Suresh, Utkarsh Gupta
Editorialist: Pratiyush Mishra

To be Calculated

None

# PROBLEM:

Given integers N and X, generate a palindrome of length N consisting of lowercase English alphabets such that the number of distinct characters in the palindrome is exactly X.
If it is impossible to do so, print -1 instead.

# EXPLANATION:

Lets tackle this problem case by case:

• Case 1: When N = 1:
Here the answer can be any character, example ‘a’.
• Case 2: When N\lt(2 \times X) - 1:
Here it won’t be possible to construct the required string, since for X distinct characters we need to use at least (2 \times X - 1) characters.
• Case 3: When N = (2 \times X) -1:
Assuming s to be a string of length X having all distinct characters, we can construct the following string as our answer:
s_1s_2...s_{x-1}s_xs_{x-1}s_{x-2}....s_1
• Case 4: When N \gt (2 \times X) - 1:
Assuming s to be a string of length X having all distinct characters, we can have three parts as:
left = s \\ mid = A \;string \;of \;length \;(N - 2 \times X) \; having\; all\; characters\; as\; s_1 \\ right = reverse(s)
Thus our final answer for this case would then be:
ans = left + mid + right

# TIME COMPLEXITY:

O(N), for each test case.

# SOLUTION:

1 Like

Hey, can anyone tell why am i getting a TLE.
I am assuming that its a language problem as I use JAVA but still can anyone tell what changes can I do in my code to get an AC.
https://www.codechef.com/viewsolution/66963373
Also took care of the fact that :-

1. \n is faster than println for changing line.
2. AND is faster than MOD for checking even-odd.
3. Using the Reader class which is the fastest I/O for JAVA (according to a GFG article).
1 Like

Simple approach. Let me know if you find any difficulty in the code.

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
using ld = long double;
using str = string;
using vs = vector<str>;
using vi = vector<int>;
using si = set<int>;
using ii = pair<int, int>;
using vii = vector<ii>;
using vvi = vector<vi>;
using mii = map<int, int>;

#define endl '\n'
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define ins insert
#define mt make_tuple
#define mp make_pair
#define YES cout << "YES" << endl
#define NO cout << "NO" << endl
#define TEZ cin.tie(0)->sync_with_stdio(0)
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define len(x) (x).length()
#define rall(x) rbegin(x), rend(x)
#define what(x) cerr << #x << " is " << x << endl
#define uniq(x) (x).resize(unique(all(x)) - (x).begin())
#define decide(x) cout << (x ? "YES" : "NO") << endl
#define rep(i, x, y)                                                           \
for (__typeof(y) i = (x) - ((x) > (y)); i != (y) - ((x) > (y));            \
i += 1 - 2 * ((x) > (y)))
#define each(x, a) for (auto &x : a)
#define debug(args...)                                                         \
{                                                                          \
string _s = #args;                                                     \
replace(_s.begin(), _s.end(), ',', ' ');                               \
stringstream _ss(_s);                                                  \
istream_iterator<string> _it(_ss);                                     \
dbg(_it, args);                                                        \
}

void dbg(istream_iterator<string> it) {}
template <typename T, typename... Args>
void dbg(istream_iterator<string> it, T a, Args... args) {
cerr << *it << " = " << a << endl;
dbg(++it, args...);
}

template <typename T, typename U> void amax(T &x, U y) { x = (x < y ? y : x); }
template <typename T, typename U> void amin(T &x, U y) { x = (y < x ? y : x); }

const ld PI = acos(-1);
const int INF = 1e9 + 7;
const int MOD = 1e9 + 7;

const int dr4[] = {0, 1, 0, -1};
const int dc4[] = {1, 0, -1, 0};
const int dr8[] = {0, 1, 1, 1, 0, -1, -1, -1};
const int dc8[] = {1, 1, 0, -1, -1, -1, 0, 1};

void solve() {
int n, x;
cin >> n >> x;

int mid = (n + 1) / 2;
if (x > mid) {
cout << -1 << endl;
return;
}

str ans = "";
rep(i, 0, mid) ans += (char)('a' + min(i, x - 1));
rep(i, mid - (n & 1), 0) ans += (char)('a' + min(i, x - 1));

cout << ans << endl;
}

int main() {
TEZ;

int t = 1;
cin >> t;
while (t--) { solve(); }

return 0;
}


You should use PrintWriter instead of System.out and you should use StringBuilder instead of Strings when you are appending a lot.

Here would be a fix with both PrintWriter and StringBuilder: Solution: 66965931 | CodeChef

Explanation:
PrintWriter is faster, but not needed in your submission.
Appending a char to a String takes O(n) where n is the length of the String. The reason is simple: Strings in Java are immutable. Meaning the length is final and cannot ever be changed. If you append a char, Java will create a new String with adjusted length and copy the old content into your new String.
You did that inside a for-loop, making your code run in O(n²). I fixed it so it runs in O(n).
A String can be compared to Character[], StringBuilder can be compared to List< Character>.

1 Like

Nice, two loops. I was really proud of my Python find.

s = 'abcdefghijklmnopqrstuvwxyz'
for n, x in [map(int, l.split()) for l in open(0)][1:]:
if n<x+x-1:
print(-1)
continue
r = s[:x-1]
print(r, s[x-1]*(n-x-x+2), r[::-1], sep='')


Hey, thank you so much for helping.
Just one last question :- Should I always use PrintWriter to avoid such TLE’s or is it only for String purposes? And do we always have to flush & close the Writer?
If PrintWriter can be used for general purposes just like System then I will include it in my template.

yes, always use PrintWriter. It allows you to write code differently. Example my Code

public static void solve() throws IOException{
int n = sc.nextInt();
int x = sc.nextInt();

if(x * 2 > n + 1){
out.println(-1);
return;
}

char[] arr = new char[n];
for (int i = 0; i < (n+1)/2; i++) {
arr[i] = (char)('a'+min(i, x-1));
arr[n-1-i] = (char)('a'+min(i, x-1));
}

for (int i = 0; i < n; i++) {
out.print(arr[i]);
}
out.println();
}


this is one of many solutions, but it is one you can ONLY use with a PrintWriter. If the testcases are not weak, System.out.print would give you a TLE.

As for flushing/closing, it is enough if you .flush() and .close() at the end of your program. At least I have never run into a problem doing it that way.

1 Like

Ohk from now on I will use PrintWriter only instead of System.out.print/println.
And once again thank you very much.

1 Like

https://www.codechef.com/viewsolution/66898144
Please someone help me why I am i getting error in this code!!

void solve()
{

if (n == 1)
{
cout << "a\n";
return;
}
if (n % 2 == 0)
{
if (x > n / 2)
{
cout << -1 << endl;
return;
}
else
{
string ans(n, ' ');
char b = 'a';
for (int i = 0; i < n / 2; i++)
{
ans[i] = ans[n - i - 1] = b;
if (x > 0 && b != 'z')
{
b++;
x--;
}
}
cout << ans << endl;
return;
}
}
else
{
if (x > (n + 1) / 2)
{
cout << -1 << endl;
return;
}
else
{
string ans(n, ' ');
char b = 'a';
for (int i = 0; i <= n / 2; i++)
{
ans[i] = ans[n - i - 1] = b;
if (x > 0 && b != 'z')
{
b++;
x--;
}
}
cout << ans << endl;
return;
}
}


}

I have made 2 cases, one odd and another even, its only passing the Case-1, Can someone tell me the mistake, have been looking it for hours

Hi all!
I am getting a WA in task 2. I can’t find where it’s going wrong. Can anyone tell me where am i wrong??

Here’s my solution:-
https://www.codechef.com/viewsolution/66967081

Respected sir,
I had submitted the below code for starters 43 and i compared it when the solution came out but wasnt able to find any error,could you please help where i have gone wrong as it would be really helpful.

#include
using namespace std;

void palindrome(int N,int X);

int main()
{
int T,N,X;

cin>>T;

for(int i=0;i<T;i++)
{
cin>>N>>X;

palindrome(N,X);
}
return 0;


}

void palindrome(int N,int X)
{
if(N<(2*X-1))
cout<<-1;

else
{
char* A=new char[N];
int i,j;
i=0;
j=N-1;

int count=0;

while(i<=j)
{
A[i]='a'+count;
A[j]='a'+count;

if(count<(X-1))
count++;

i++;
j--;
}

cout<<A;
}

cout<<endl;


}
strong text