10262 - Suffidromes

All about problems in Volume 102. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

10262 - Suffidromes

Post by Ivan Golubev »

Is empty word (i.e. with length == 0) palindrome or not?

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

yes, it is a palindrom

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev »

OK, thanks. And one more question -- can x be a zero-length word?

Adrian Kuegel
Guru
Posts: 724
Joined: Wed Dec 19, 2001 2:00 am
Location: Germany

Post by Adrian Kuegel »

Yes, for example input:
a
ab
Output:

(blank line)

Ivan Golubev
Experienced poster
Posts: 167
Joined: Fri Oct 19, 2001 2:00 am
Location: Saint Petersburg, Russia

Post by Ivan Golubev »

Thanks one more time!

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

Post by Yarin »

I keep getting WA, I'm not sure why the following algorithm doesn't work:

1) If strings equal, print "No solution."
2) If one string is empty:
2.1) If the other string is not a palindrome, print blank line
2.2) Otherwise either add 'a' or 'b' (just check which one makes the other string not a palindrome)
3) Let x be all prefixes of a and b (including whole a and b) and check whether it satifies the criteria. Select shortest and alphabetically first
4) If still no solution is found, let x be any lower case character (loop through a-z, maybe only a-b is necessary) plus the shortest of the two strings a and b. Break the loop if conditions are satisfied.
5) Print x or "No solution."

Where's the flaw!? Or have I simple missed something in the implementation of this algorithm?

Yarin
Problemsetter
Posts: 112
Joined: Tue Sep 10, 2002 5:06 am
Location: Ume
Contact:

Post by Yarin »

*sigh* I totally forgot that the string compare should be reversed since the prefix is appended backwards.

Whinii F.
Experienced poster
Posts: 151
Joined: Wed Aug 21, 2002 12:07 am
Location: Seoul, Korea
Contact:

What's my flaw?!

Post by Whinii F. »

I personally don't like posting long sources..
but anyway I'm getting too much WA :(

Where's my flaw? It passes every test cases I could think of.

[c]
#include <stdio.h>
#include <string.h>

#define max 2020

int al, bl;
char a[max], b[max];

void reverseString(int len, const char *from, char *to)
{
int i;
for(i = 0; i < len; i++)
to[len-i-1] = from;
to[len] = 0;
}

int isPalindrome(int len, char *str)
{
int i;
for(i = 0; i < len; i++)
if(str != str[len-i-1])
return 0;
return 1;
}

int Check(int cl, char *candidate)
{
int ap, bp;
strcpy(a+al, candidate);
strcpy(b+bl, candidate);
ap = isPalindrome(al+cl, a);
bp = isPalindrome(bl+cl, b);
a[al] = b[bl] = 0;
return ap ^ bp; /* xor */
}

void solve(void)
{
int i;
int xl = -1, cl;
char x[max], c[max]; /* c stands for Candidate */

al = strlen(a);
bl = strlen(b);

c[0] = 0;
if(Check(0, c))
{
printf("\n");
return;
}

c[1] = 0;
for(i = 'a'; i <= 'z'; i++)
{
c[0] = i;
if(Check(1, c))
{
printf("%s\n", c);
return;
}
}

reverseString(al, a, c);
cl = al;
while(cl >= 0)
{
if(Check(cl, c) && (xl == -1 || xl > cl || (xl == cl && strcmp(x, c) > 0)))
{
strcpy(x, c);
xl = cl;
}
for(i = 0; i < cl; i++)
c = c[i+1];
cl--;
}
reverseString(bl, b, c);
cl = bl;
while(cl >= 0)
{
if(Check(cl, c) && (xl == -1 || xl > cl || (xl == cl && strcmp(x, c) > 0)))
{
strcpy(x, c);
xl = cl;
}
for(i = 0; i < cl; i++)
c = c[i+1];
cl--;
}

if(xl > -1)
printf("%s\n", x);
else
printf("No solution.\n");
}

int main(void)
{
a[0] = b[0] = 0;
gets(a);
gets(b);
while(a[0] != 0 || b[0] != 0 || !feof(stdin))
{
solve();
a[0] = b[0] = 0;
gets(a);
gets(b);
}
return 0;
}[/c]

jingye
New poster
Posts: 21
Joined: Sat Sep 07, 2002 5:28 am

Post by jingye »

Try the test cases at the Waterloo ACM website

stcheung
Experienced poster
Posts: 114
Joined: Mon Nov 18, 2002 6:48 am
Contact:

10262 Time Limit Exceeded

Post by stcheung »

Hmm....any idea why I keep getting Time Limit Exceeded? I admit my algorithm is plain, but I think it's still acceptable. Is it that I used cin.eof() wrongly or something like that? THANKS.

[cpp]#include <iostream.h>
#include <stdlib.h>
#include <string>

string A, B, longer, shorter, x1, x2;

void findpalindromes(int len);
bool palindrome(string s);
string reverse(string s);
int main()
{
while(true)
{
getline(cin, A);
getline(cin, B);
longer = (A.length() >= B.length() ? A : B);
shorter = (longer==A ? B : A);
if(cin.eof())
break;
if(longer == shorter)
{
cout << "No solution.\n";
continue;
}
if((palindrome(longer) && !palindrome(shorter)) ||
(palindrome(shorter) && !palindrome(longer)))
{
cout << "\n";
continue;
}
else if(shorter=="")
{
if(!palindrome(longer))
{
cout << "\n";
continue;
}
for(int i=0; i<26; i++)
{
if(!palindrome(longer + (char)(i + 'a')))
{
cout << (char)(i + 'a') << "\n";
break;
}
}
continue;
}

for(int len=1; len<=shorter.length(); len++)
{
findpalindromes(len);
if(x1 != "" && x2 != "")
{
cout << (x1 < x2 ? x1 : x2) << "\n";
break;
}
else if(x1 != "")
{
cout << x1 << "\n";
break;
}
else if(x2 != "")
{
cout << x2 << "\n";
break;
}
}
}
return 0;
}

void findpalindromes(int len)
{
x1 = x2 = "";
int i,j;
/* if(len > shorter.length())
{
for(i=0; i<26; i++)
{
x1 = (char)('a' + i) + reverse(shorter);
if(palindrome(shorter+x1) && !palindrome(longer + x1))
break;
}
}
else */
{
x1 = reverse(shorter.substr(0,len));
if(!palindrome(shorter + x1) || palindrome(longer + x1))
x1 = "";
}
/*
if(len > longer.length())
{
for(j=0; j<26; j++)
{
x2 = (char)('a' + j) + reverse(longer);
if(palindrome(longer+x2) && !palindrome(shorter + x2))
break;
}
}
else*/
{
x2 = reverse(longer.substr(0,len));
if(!palindrome(longer + x2) || palindrome(shorter + x2))
x2 = "";
}
}

string reverse(string s)
{
string result="";
for(int i=0; i<s.length(); i++)
{
result = s + result;
}
return result;
}

bool palindrome(string s)
{
return s == reverse(s);
}[/cpp]

anisalamgir
New poster
Posts: 6
Joined: Sat Jul 09, 2005 10:18 am
Location: Daffodil International University,Dhaka
Contact:

10262 help...........

Post by anisalamgir »

hey...
any one give me this problem algorithm..........
i can't understood...................
ok... best of luck :roll:
anis alamgir

soth
New poster
Posts: 7
Joined: Tue Apr 17, 2007 1:22 am

Post by soth »

I have tried a lot of inputs including test cases like the ones posted before, but I still get WA.
Some rare I/O to check where my program fails?
Thanks!

soth
New poster
Posts: 7
Joined: Tue Apr 17, 2007 1:22 am

Post by soth »

please, does somebody have some rare IO for this problem?
I still get WA...

Post Reply

Return to “Volume 102 (10200-10299)”