Official

C - racecar Editorial by en_translator


Basically, just follow the instruction in the problem statement. That is, it is sufficient to iterate all \(i\) and \(j\) such that \(1\leq i,j\leq N\) to:

  1. check if \(i\neq j\);
  2. if the condition 1. is satisfied, construct a string \(T_{i,j}\equiv S_i+S_j\) by concatenating \(S_i\) and \(S_j\);
  3. (if the condition 1. is satisfied), determine if \(T_{i,j}\) is a palindrome. Specifically, determine if the \(T_{i,j}\)-th and \((\lvert T_{i,j}\rvert+1-k)\)-th characters of \(T_{i,j}\) are equal for all integers \(k\) such that \(1\leq k\leq \lvert T_{i,j}\rvert\).

At least one \(T_{i,j}\) is a palindrome, print Yes; otherwise, print No.

If you know if statement, for statement, and how to obtain the length of a string and concatenate strings, then you can implement the procedure.

Even a naive implementation costs only about \(O(N^2\max(\lvert S_i\rvert))\) time, so the problem can be solved fast enough.

Sample code in C++:

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


int main() {
	int n,l;
	bool flag;
	string s[100];
	string t;

	cin>>n;
	for(int i=0;i<n;i++)cin>>s[i];

	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			if(i!=j){
				t=s[i]+s[j];
				l=t.size();
				flag=true;
				for(int k=0;k<l;k++)if(t[k]!=t[l-k-1])flag=false;
				if(flag){
					cout<<"Yes"<<endl;
					return 0;
				}
			}
		}
	}

	cout<<"No"<<endl;
	return 0;
}

Sample code in Python:

n=int(input())
s=[input() for i in range(n)]
ans="No"

for i in range(n):
    for j in range(n):
        if i!=j:
            t=s[i]+s[j]
            flag=True
            for k in range(len(t)):
                if t[k]!=t[-k-1]:
                    flag=False
            if flag:
                ans="Yes"

print(ans)

posted:
last update: