11584  Partitioning by Palindromes
Moderator: Board moderators
11584  Partitioning by Palindromes
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
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

 New poster
 Posts: 20
 Joined: Mon Oct 20, 2008 6:26 am
Re: 11584  Partitioning by Palindromes
It's O(N^2) DP

 New poster
 Posts: 12
 Joined: Tue Aug 27, 2002 6:09 pm
Re: 11584  Partitioning by Palindromes
Is it possible to solve this problem with no DP? Sample input/output please. Thanks in advance
Re: 11584  Partitioning by Palindromes
I solved this problem with the help of BFS!
Re: 11584  Partitioning by Palindromes
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
Thanks alot for your reply in advance .
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
Thanks alot for your reply in advance .
Re: 11584  Partitioning by Palindromes
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 !!!
To find all palindroms in the string I use O(N^2) algo in worse case.
Sorry for my English !!!
Re: 11584  Partitioning by Palindromes
Last edited by sapnil on Wed Feb 25, 2009 4:06 am, edited 1 time in total.
"Dream Is The Key To Success"
@@@ Jony @@@
@@@ Jony @@@
Re: 11584  Partitioning by Palindromes
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
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

 New poster
 Posts: 12
 Joined: Tue Aug 27, 2002 6:09 pm
Re: 11584  Partitioning by Palindromes
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.
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;
}
Re: 11584  Partitioning by Palindromes
Try this:
Answer:
Code: Select all
7
amadam
madama
zzxzcc
qwerty
zzxxxz
zxxxzz
zxzczxxzc
Code: Select all
2
2
3
6
2
2
2

 New poster
 Posts: 12
 Joined: Tue Aug 27, 2002 6:09 pm
Re: 11584  Partitioning by Palindromes
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...
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...
Re: 11584  Partitioning by Palindromes
I had discripted my algo above!
I don't need to find the largest palindrom at first!!!
I don't need to find the largest palindrom at first!!!
Re: 11584  Partitioning by Palindromes
Could someone give me a hint how to use a O(N^2) DP to solve this problem? I use a N^3 with TLE.
electron
Re: 11584  Partitioning by Palindromes
For example we have a string s;
O(n^2) how to find palindromes:
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=i1;
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!
}
Re: 11584  Partitioning by Palindromes
the o(n^2) DP is like this :
let's say that v stores the minimum number of group up to the ith 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... ^^
let's say that v stores the minimum number of group up to the ith 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... ^^