401 - Palindromes

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

Moderator: Board moderators

Algoritmo
New poster
Posts: 32
Joined: Wed Oct 15, 2003 12:10 pm
Contact:

Alun's code

Post by Algoritmo » Sat May 08, 2004 2:58 pm

Alun, you checked for mirroring and palindroming, both things at the same time. I think it's easier if you check independently:

[cpp]int Len = strlen(S);
bool IsPal = true, IsMir = true;
for (int i = 0; i < Len; i++) {
char C = S;
char Op = S[Len-1-i];
if (C != Op) IsPal = false;
if (C != Rev(Op)) IsMir = false;
}
[/cpp]
One thing that bored me about this problem is this sentence:
"A mirrored string is a string for which when each of the elements of the string is changed to its reverse (if it has a reverse) and the string is read backwards the result is the same as the original string."

This sentence is ambuguous. What if it does not have a reverse? Should I not replace that character, should I replace it with blank space or all characters must have an reverse for that input to be mirrored?
The sample input does not answer my question, but I discovered the answer by sending mutiple codes until I got Accepted.
I replaced characters that didn't have a reverse with blank space.
I solve 4 problems per day, then I expend 4 days stuck in a single problem. But I think I'm doing well... ID 37180

Jewel of DIU
New poster
Posts: 32
Joined: Thu Jul 31, 2003 6:21 am
Location: Daffodil Univ, Bangladesh
Contact:

401Why WA??

Post by Jewel of DIU » Sun Jun 06, 2004 4:41 am

Here is my code for prob 401, It causes WA.
[c]
#===========#
CUT AFTER AC
#===========#
[/c]
Last edited by Jewel of DIU on Wed Jun 09, 2004 3:55 pm, edited 1 time in total.
Hate WA
Visit phpBB!

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

silly mistake

Post by sohel » Sun Jun 06, 2004 7:59 am

Reversing V yields V and not U.

A part of your code
[c]
rev['T'] = 'T';
rev['U'] = 'U';
rev['V'] = 'U';
[/c]

Hope you can see the mistake... :wink:

Jewel of DIU
New poster
Posts: 32
Joined: Thu Jul 31, 2003 6:21 am
Location: Daffodil Univ, Bangladesh
Contact:

Post by Jewel of DIU » Wed Jun 09, 2004 3:57 pm

Now I have got AC :) .
Thank you Sohel Bhai.
Hate WA
Visit phpBB!

RustB
New poster
Posts: 16
Joined: Mon Jun 14, 2004 5:08 pm

401- Palindromes

Post by RustB » Sun Jun 20, 2004 11:57 am

This seems too simple to give this much trouble :(
Can anyone see what the problem is?

Code: Select all

#include <stdio.h>
char rev[40]="01SE0Z0080A000300HIL0JM0O0002TUVWXY5";
int ispalin(char *x, int n)
{
	int i;
	for(i=0;i<n;i++)
	     if(x[i] != x[n-i-1])
	     	return 0;
	return 1;
}
int ismirror(char *x, int n)
{
	int i,flag=0;
     for(i=n/2;i<n;i++)
    	     if(isalpha(x[i]))
    	     	if(rev[x[i]-'A'+10]!=0)
    	     	{
    	     	    	x[i]=rev[x[i]-'A'+10];
    	     	    	flag=1;
    	     	}
    	     else
    	     	if(rev[x[i]])
    	     	{
    	     	   	x[i]=rev[x[i]];
    	     	   	flag=1;
    	     	}

	if(!flag) return 0;

    	for(i=0;i<n;i++)
    	     if(x[i] != x[n-i-1])
    	     	return 0;
	return 1;
}
int main(void)
{
	char inp[25],xinp[25];
	while(!feof(stdin))
	{
	     int isp,ism,n;
	     scanf("%s",inp);
		n=strlen(inp);
		strcpy(xinp,inp);
	     isp=ispalin(xinp,n);
	     ism=ismirror(xinp,n);
	     if(!isp && !ism)
	     	printf("%s -- is not a palindrome.\n\n",inp);
	     else if(isp && !ism)
	     	printf("%s -- is a regular palindrome.\n\n",inp);
	     else if(!isp && ism)
	     	printf("%s -- is a mirrored string.\n\n",inp);
	     else
	     	printf("%s -- is a mirrored palindrome.\n\n",xinp);
	}
	return 0;
}

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Sun Jun 20, 2004 12:31 pm

Consider these inputs and outputs..

input
[c]
B
E
[/c]

your program outputs
[c]
0 -- is a mirrored palindrome.

3 -- is a mirrored palindrome.
[/c]

Hope you can find your mistake and rectify it. :)

RustB
New poster
Posts: 16
Joined: Mon Jun 14, 2004 5:08 pm

Post by RustB » Sun Jun 20, 2004 6:50 pm

Okay... Thanks for that. I made some stupid assumptions about ASCII conversions :/ But I have a different set of problems now. I suppose I have to sort this out the hard way :/

Thanks anyway

RustB
New poster
Posts: 16
Joined: Mon Jun 14, 2004 5:08 pm

Post by RustB » Mon Jun 21, 2004 2:19 pm

I still don't understand. This is my test data

Code: Select all

NOTAPALINDROME
ISAPALINILAPASI
2A3MEAS
ATOYOTA
MAIAM
123ESI
123ES1
DEO3D
9339
A
B
E
M
1
3
2
4
Output is:

Code: Select all

NOTAPALINDROME -- is not a palindrome.
ISAPALINILAPASI -- is a regular palindrome.
2A3MEAS -- is a mirrored string.
ATOYOTA -- is a mirrored palindrome.
MAIAM -- is a mirrored palindrome.
123ESI -- is not a palindrome.
123ES1 -- is a mirrored string.
DEO3D -- is a mirrored string.
9339 -- is a regular palindrome.
A -- is a mirrored palindrome.
B -- is a regular palindrome.
E -- is a mirrored palindrome.
M -- is a mirrored palindrome.
1 -- is a mirrored palindrome.
3 -- is a mirrored palindrome.
2 -- is a mirrored palindrome.
4 -- is a regular palindrome.
Is everything correct? Why do I still get a WA? Please help me
Edit: The formatting is correct in the actual output

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Mon Jun 21, 2004 2:27 pm

By giving a quick glance I see that the output for

E

is not correct. :o

E is a palindrome - right.... but its not a mirrored one.

So I think the output should be

E -- is a regular palindrome.
:wink:

RustB
New poster
Posts: 16
Joined: Mon Jun 14, 2004 5:08 pm

Post by RustB » Mon Jun 21, 2004 5:06 pm

I changed that, but it's still not accepted

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Post by jagadish » Tue Jun 22, 2004 8:17 pm

i lost my AC code for this one ..anyway consider these inputs
2S2
SS22
output:

222 -- is a mirror.... // original string is changed
SS22 -- is not a palindrome // must be mirrored string
if u can think of it .. u can do it in software.

RustB
New poster
Posts: 16
Joined: Mon Jun 14, 2004 5:08 pm

Post by RustB » Wed Jun 23, 2004 6:44 am

This is my modified code

Code: Select all

#include <stdio.h>
char rev[40]="01SE0Z0080A000300HIL0JM0O0002TUVWXY5";
int ispalin(char *x, int n)
{
	int i;
	for(i=0;i<n;i++)
	     if(x[i] != x[n-i-1])
	     	return 0;
	return 1;
}
int ismirror(char *x, int n)
{
	int i,flag=0;
	if(n<2) return 0;
     for(i=n/2;i<n;i++)
    	     if(isalpha(x[i]))
    	     {
    	     	if(rev[x[i]-'A'+10]!='0')
    	     	{
				x[i]=rev[x[i]-'A'+10];
    	     	    	flag=1;
    	     	}
    	     }
    	     else
    	     {
    	     	if(rev[x[i]-'0']!= '0')
    	     	{
				x[i]=rev[x[i]-'0'];
    	     	   	flag=1;
    	     	}
    	     }

	if(!flag) return 0;
    	for(i=0;i<n;i++)
    	     if(x[i] != x[n-i-1])
    	     	return 0;
	return 1;
}
int main(void)
{
	char inp[25],xinp[25];
	int i;
	while(1)
	{
	     int isp,ism,n;
	     fgets(inp,sizeof(inp),stdin);
		n=strlen(inp);
		inp[n-1]='\0';
		n--;
		if(strcmp(inp,"")==0) break;
		strcpy(xinp,inp);
	     isp=ispalin(xinp,n);
	     ism=ismirror(xinp,n);
	     if(!isp && !ism)
	     	printf("%s -- is not a palindrome.\n\n",inp);
	     else if(isp && !ism)
	     	printf("%s -- is a regular palindrome.\n\n",inp);
	     else if(!isp && ism)
	     	printf("%s -- is a mirrored string.\n\n",inp);
	     else
	     	printf("%s -- is a mirrored palindrome.\n\n",inp);
	}
	return 0;
}
The OJ says it gets a wrong answer.
It gives the correct answer for your inputs jagadish

jagadish
Learning poster
Posts: 90
Joined: Mon Feb 16, 2004 8:53 pm
Location: Bangalore INDIA

Post by jagadish » Wed Jun 23, 2004 7:54 pm

since sohel told pointed out that program is not working for B ,E you
probably added this line [c] if(n<2) return 0; [/c] to fix it ,now it doesnt work for 8 ! ..its an easy program you need to test properly

btw i re-wrote the solution if u still get WA i can send that ..
if u can think of it .. u can do it in software.

RustB
New poster
Posts: 16
Joined: Mon Jun 14, 2004 5:08 pm

Post by RustB » Thu Jun 24, 2004 5:02 am

For 8 I'm getting
8 -- is a regular palindrome

What's wrong with that?

User avatar
sohel
Guru
Posts: 856
Joined: Thu Jan 30, 2003 5:50 am
Location: New York

Post by sohel » Sun Jun 27, 2004 6:41 am

8 is a mirrored palindrome.. I think. :-?

Post Reply

Return to “Volume 4 (400-499)”