NOPAL - Editorial

editorial
, , ,
1

PROBLEM LINK:

Practice
Contest: Division 3
Contest: Division 2
Contest: Division 1

Author: Jeevan Jyot Singh
Tester : Takuki Kurokawa
Editorialist: Aman Dwivedi

DIFFICULTY:

Simple

PREREQUISITES:

Palindromes

PROBLEM:

You need to construct the string of length N such that none of its substring of length \ge2 is a palindrome.

EXPLANATION:

Take any string of length 3 such that all the characters of this string are distinct. Now, just keep on repeating this string until you get the desired length N to get the desired string which is asked in the problem.

Why does this work?

Let’s say we have a string X of length 3 such that all the characters are distinct. That means:

X[0] \neq X[1] \\ X[0] \neq X[2] \\ X[1] \neq X[2]

Hence when we repeat this string we get:

X[0],X[1],X[2],X[0],X[1],X[2],.......
  • Observe that for any character, the character next to it and before to it is always different.

Now suppose we have generated the string of length N by repeating the string X. Now let’s consider any substring of length \ge2. Let’s say S[i, M] is the substring:

Now to be a palindromic substring the first and last character of this substring should be equal, let’s say :

  • S[i] = S[M]

  • Now can the characters S[i+1] and S[M-1] be the same ever. The answer is to this is NO as S[i] = S[M] and the characters next to it and before to it are always different.

Hence we can see there won’t be any palindromic substrings of length \ge2 in such construction.

TIME COMPLEXITY:

O(N) per test case

SOLUTIONS:

Author's Solution
Tester's Solution 
#include <bits/stdc++.h>
using namespace std;

int main() {
    int tt;
    cin >> tt;
    while (tt--) {
        int n;
        cin >> n;
        string t = "tabr";
        for (int i = 0; i < n; i++) {
            cout << t[i % 4];
        }
        cout << '\n';
    }
    return 0;
}
Editorialist Solution 
#include<bits/stdc++.h>
using namespace std;

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

    string s="abc";

    for(int i=0;i<n;i++)
      cout<<s[i%3];

    cout<<"\n";
}

int main()
{
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  int t;
  cin>>t;

  while(t--)
    solve();

return 0;
}
1 Like
2

Why can’t we use "abcdef… .?

3

You can !!

5

can’t we use string of length 4 ?

6

What’s wrong with my code?

#include <iostream>
using namespace std;

int main() {
	int t;
	cin>>t;
	while(t--){
	    int n;
	    cin>>n;
	    char arr[27];
        for(int i=0; i<26; i++){
            arr[i] = 'a'+i;
        }
        string s="";
        int i=n;
        while(n--){
            s=s+arr[i-1];
            i--;
        }
        cout<<s<<endl;
	    //cout<<endl;
	}
	return 0;
}
7

When n is say 100, your arr[i-1] will be out of bounds.

8

why my solution is wrong?

/* package codechef; // don’t place package name! */

import java.util.;
import java.lang.;
import java.io.*;

class Codechef
{
static class Reader {
final private int BUFFER_SIZE = 1 << 16;
private DataInputStream din;
private byte[] buffer;
private int bufferPointer, bytesRead;

    public Reader()
    {
        din = new DataInputStream(System.in);
        buffer = new byte[BUFFER_SIZE];
        bufferPointer = bytesRead = 0;
    }

    public Reader(String file_name) throws IOException
    {
        din = new DataInputStream(
            new FileInputStream(file_name));
        buffer = new byte[BUFFER_SIZE];
        bufferPointer = bytesRead = 0;
    }

    public String readLine() throws IOException
    {
        byte[] buf = new byte[64]; // line length
        int cnt = 0, c;
        while ((c = read()) != -1) {
            if (c == '\n') {
                if (cnt != 0) {
                    break;
                }
                else {
                    continue;
                }
            }
            buf[cnt++] = (byte)c;
        }
        return new String(buf, 0, cnt);
    }

    public int nextInt() throws IOException
    {
        int ret = 0;
        byte c = read();
        while (c <= ' ') {
            c = read();
        }
        boolean neg = (c == '-');
        if (neg)
            c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');

        if (neg)
            return -ret;
        return ret;
    }

    public long nextLong() throws IOException
    {
        long ret = 0;
        byte c = read();
        while (c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if (neg)
            c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        if (neg)
            return -ret;
        return ret;
    }

    public double nextDouble() throws IOException
    {
        double ret = 0, div = 1;
        byte c = read();
        while (c <= ' ')
            c = read();
        boolean neg = (c == '-');
        if (neg)
            c = read();

        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');

        if (c == '.') {
            while ((c = read()) >= '0' && c <= '9') {
                ret += (c - '0') / (div *= 10);
            }
        }

        if (neg)
            return -ret;
        return ret;
    }

    private void fillBuffer() throws IOException
    {
        bytesRead = din.read(buffer, bufferPointer = 0,
                             BUFFER_SIZE);
        if (bytesRead == -1)
            buffer[0] = -1;
    }

    private byte read() throws IOException
    {
        if (bufferPointer == bytesRead)
            fillBuffer();
        return buffer[bufferPointer++];
    }

    public void close() throws IOException
    {
        if (din == null)
            return;
        din.close();
    }
}
public static void main (String[] args) throws java.lang.Exception
{
	// your code goes here
//	Scanner sc = new Scanner(System.in);
	 Reader sc = new Reader();
	long T = sc.nextLong();
	while(T-->0)
	{
	   long n = sc.nextLong();
	  // for(int i=97;i<(97+n);i++)
	  // {
	  //    System.out.print((char)(i+1)); 
	  // }
	    
	  // System.out.println();
	   // create a string of all characters
String alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

// create random string builder
StringBuilder sb = new StringBuilder();

// create an object of Random class
Random random = new Random();

// specify length of random string
for(int i = 0; i < n; i++) {

  // generate random index number
  int index = random.nextInt(alphabet.length());

  // get character specified by index
  // from the string
  char randomChar = alphabet.charAt(index);

  // append the character to string builder
  sb.append(randomChar);
}

String randomString = sb.toString();
String original = randomString; 
String reverse = " ";
  int length = original.length();   
  for ( int i = length - 1; i >= 0; i-- )  
     reverse = reverse + original.charAt(i); 
     if (!(original.equals(reverse)) ) 
     System.out.println(randomString);  
	}
	sc.close();
}

}

9

Why my code is wrong

#include
using namespace std;
int main()
{
int t;
cin>>t;
while(t–)
{
int N;
cin>>N;
if(N<=26)
{
for(int i=0; i<N; i++)
{
char c=‘a’+i;
cout<<c;
}
}
else {
int p =N%26;
int k=(N-p)/26;
for(int i=0; i<k; i++)
{
for(int i=0; i<26; i++)
{
char c=‘a’+i;
cout<<c;
}
for(int i=0; i<p; i++)
{
char c=‘a’+i;
cout<<c;
}

}
}
cout<<endl;
}
return 0;
}

10

Accepted approach

import java.util.*;
class Main {
	public static void main(String args[]) {
		Scanner sc = new Scanner(System.in);
		int t = sc.nextInt();
		while(t-->0){
			String s = "abcdefghijklmnopqrstuvwxyz";
			int n = sc.nextInt();
			String ans = "";
			if(n<=26)
			System.out.println(s.substring(0,n));
			else{
				while(n>0){
                     if(n>26){
						 ans+=s.substring(0,26);
						 n-=26;
					 }
					 else{
						 ans+=s.substring(0,n);
						 break;
					 }
				}
				System.out.println(ans);
			}
		}
	}
}
11

The main mistake in the code is that for n>26. The logic is correct but the error is in implementation.
According to the logic, if n is divisible by 26, the characters a to z must be printed exactly k times and if n is not divisible by 26, in addition to printing characters k times, the remaining p characters (the first p characters from ‘a’ to ‘z’) must be printed.
So the error is “including the second loop printing p characters in the the loop executing k times.” If you just bring the loop running p times out, the answer be correct :slight_smile:
Also, you may further shorten the code by removing the if and else checks, as you are calculating k and p, you can simply run the loop as mentioned above, the only thing to change is to make i=1 and i<=k in the first loop and i=1 , i<=p and c=‘a’ + i - 1in the second loop.
For reference for shortening the code , you may check this submission. It is based on your code only, I had just deleted some part and make the changes which are mentioned in the paragraph above. Hope that helps :slight_smile:
Link for the submission :
https://www.codechef.com/viewsolution/57023079

1 Like
12

you have defined your array for 27 elements, but for larger values of i, arr will be out of bounds

13

That’s literally what I did, I’m attaching my code for reference

#include <bits/stdc++.h>

using namespace std;

void notapalindrome(int n){
string s1=“abcdefghijklmnopqrstuvwxyz”;
string s="";
int i=0;
while(n–){
s=s+s1[i];
if(i==25){
i=0;
}
i++;
}
std::cout << s << std::endl;
}

int main() {
int t;
cin >> t;
while (t–) {
int n;
cin >> n;
notapalindrome(n);
}
return 0;
}

14

I did my code this way
Please tell me what’s wrong.

#include <bits/stdc++.h>
using namespace std;

int main() {
// your code goes here
string g=“abcdefghijklmnopqrstuvwxyz”;
int t;
cin>>t;
while(t–){
int n,j;
cin>>n;
if(n>26){
int l=n/26;
for(int i=1;i<=l;i++){
cout<<g;
}
}
string s;
char a=‘a’;
j=((int)a)+(n%26);
int k=0;
for(int i=(int)a;i<j;i++){
s[k]=(char)i;
cout<<s[k];
k++;
}
cout<<endl;
}
return 0;
}