11584 - Partitioning by Palindromes

All about problems in Volume 115. 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
srinivas
New poster
Posts: 2
Joined: Sun Feb 22, 2009 8:20 am

11584 - Partitioning by Palindromes

Post by srinivas » Sun Feb 22, 2009 11:01 am

Hi,

Any Hints on this problem .
I was only able to think of a O ( n ^ 3 ) dp solution which timed out when i submitted it .
Please help me.

Thanks a billion for your reply in advance

SerailHydra
New poster
Posts: 20
Joined: Mon Oct 20, 2008 6:26 am

Re: 11584 - Partitioning by Palindromes

Post by SerailHydra » Sun Feb 22, 2009 11:42 am

It's O(N^2) DP

mice123456789
New poster
Posts: 12
Joined: Tue Aug 27, 2002 6:09 pm

Re: 11584 - Partitioning by Palindromes

Post by mice123456789 » Sun Feb 22, 2009 12:03 pm

Is it possible to solve this problem with no DP? Sample input/output please. Thanks in advance :-?

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 11584 - Partitioning by Palindromes

Post by Igor9669 » Sun Feb 22, 2009 1:33 pm

I solved this problem with the help of BFS!

srinivas
New poster
Posts: 2
Joined: Sun Feb 22, 2009 8:20 am

Re: 11584 - Partitioning by Palindromes

Post by srinivas » Sun Feb 22, 2009 7:08 pm

Thanks alot SerailHydra for that hint .
I got ACC in that problem .

Igor9669 , can you please give some details of your BFS approach .
I wasn't able to think anything related to BFS for that problem :cry:
Thanks alot for your reply in advance .

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 11584 - Partitioning by Palindromes

Post by Igor9669 » Sun Feb 22, 2009 9:15 pm

I construct a graph, where vertices were symbols of the string, and edges connected a pair of such symbols(X,Y),where in X the palindrom begined and before Y it ended. So, now the problem is to find the shortest path from the first symbol to the (last+1).
To find all palindroms in the string I use O(N^2) algo in worse case.

Sorry for my English :D !!!

sapnil
Experienced poster
Posts: 106
Joined: Thu Apr 26, 2007 2:40 pm
Location: CSE-SUST
Contact:

Re: 11584 - Partitioning by Palindromes

Post by sapnil » Tue Feb 24, 2009 5:49 am

I use Dijkstra & get lot of WR, please help me:

Code: Select all

Code remove.....
Last edited by sapnil on Wed Feb 25, 2009 4:06 am, edited 1 time in total.
"Dream Is The Key To Success"

@@@ Jony @@@

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 11584 - Partitioning by Palindromes

Post by Igor9669 » Tue Feb 24, 2009 7:19 pm

Try this tests:
2
asaaaa
azzaa

correct answer are:
2 (asa aaa)
2 (azza a)

Your programm output:
1
1

And you should modify your algo to find palindroms, because you will get TLE with it.Try to make O(n^2)algo

mice123456789
New poster
Posts: 12
Joined: Tue Aug 27, 2002 6:09 pm

Re: 11584 - Partitioning by Palindromes

Post by mice123456789 » Tue Feb 24, 2009 10:00 pm

Hi Igor,

I dont know complex algo for this problem, just used the simple one. But still get WA. Is there any special case that i do not handle? Thanks.

Code: Select all

#include <stdio.h>
#include <string.h>

int ispalindrom(char *s, int index, int size)
{
	int i;

	for (i = 0; i < (size / 2); i++)
	{
		if (s[index + i] != s[index + size - i - 1])
			return 0;
	}

	return 1;
}

int main()
{
	char s[10000];
	int i, j, len, size, group, N;

	scanf("%d\n", &N);

	for (j = 0; j < N; j++)
	{
		gets(s);
		len = strlen(s);

		i = 0;
		group = 0;
		size = len;

		while (i < len)
		{
			for (size = len - i; size >= 1; size--)
				if (ispalindrom(s, i, size))
				{
					i += size;
					group++;
					break;
				}
		}

		printf("%d\n", group);
	}

	return 0;
}

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 11584 - Partitioning by Palindromes

Post by Igor9669 » Thu Feb 26, 2009 12:42 pm

Try this:

Code: Select all

7
amadam
madama
zzxzcc
qwerty
zzxxxz
zxxxzz
zxzczxxzc
Answer:

Code: Select all

2
2
3
6
2
2
2

mice123456789
New poster
Posts: 12
Joined: Tue Aug 27, 2002 6:09 pm

Re: 11584 - Partitioning by Palindromes

Post by mice123456789 » Thu Feb 26, 2009 5:23 pm

Thanks, Igor. This problem is not easy as I thought. Can you clarify the group no below?

amadam = 2: {a}, {madam}
madama = 2: {madam}, {a}
zzxzcc = 3: {z}, {zxz}, {cc}
qwerty = 6: {q}, {w}, {e}, {r}, {t}, {y}
zzxxxz = 2: {z}, {zxxxz}
zxxxzz = 2: {zxxxz}, {z}
zxzczxxzc = 2: {zxz}, {czxxzc}

Seemed likely we have to find the largest palidrome first. Correct me...

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 11584 - Partitioning by Palindromes

Post by Igor9669 » Sat Feb 28, 2009 9:17 am

I had discripted my algo above!
I don't need to find the largest palindrom at first!!!

f74956227
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:

Re: 11584 - Partitioning by Palindromes

Post by f74956227 » Sun Mar 01, 2009 4:07 am

Could someone give me a hint how to use a O(N^2) DP to solve this problem? :D I use a N^3 with TLE.
electron

Igor9669
Learning poster
Posts: 85
Joined: Sun Jun 08, 2008 12:58 pm

Re: 11584 - Partitioning by Palindromes

Post by Igor9669 » Sun Mar 29, 2009 8:44 am

For example we have a string s;

O(n^2) how to find palindromes:

Code: Select all

int l,r;
s[0]='*';
s[s.length()]='*';
for(int i=1;i<s.length();++i)
{
   l=i-1;
   r=i+1;
   while(s[l]==s[r])
   {
        //some code
        .......
        l--;r++;
   }
   l=i;
   r=i+1;
   while(s[l]==s[r])
   {
        //some code
        .......
        l--;r++;
   }  
   //also the string form i to i is a palindrom!       
}

whateva
New poster
Posts: 3
Joined: Fri Jun 20, 2008 7:22 am

Re: 11584 - Partitioning by Palindromes

Post by whateva » Thu Jul 23, 2009 7:07 pm

the o(n^2) DP is like this :
let's say that v stores the minimum number of group up to the i-th character. Then for every position j ( 0 <= j < i ), we check which one is the minimum one. That is, we only take every j in which the substring from j+1 to i is a palindrome, and we check if current v < v[j]+1 (it's 1, since the substring from j+1 to i is already a palindrome). Of course, we'll need to precompute a boolean table which store each substring's status (palindrome or not), which is also can be done in o(n^2) (look for the previous post in this thread, for a hint). Therefore, the time complexity is o(n^2).

I hope this will help... ^^

Post Reply

Return to “Volume 115 (11500-11599)”