DISPAL Editorial

editorial
, , ,
1

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

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

DIFFICULTY:

To be Calculated

PREREQUISITES:

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:

Editorialist’s Solution
Setter’s Solution
Tester1’s Solution
Tester2’s Solution

1 Like
2

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.
Link to my submission :-
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
3

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

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: CodeChef: Practical coding for everyone

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
5

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='')
6

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.

7

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
8

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

1 Like
9

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

10

void solve()
{
read(n);
read(x);

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

11

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

12

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);
}
// your code goes here
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