## 11569 - Lovely Hint

Moderator: Board moderators

tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

### 11569 - Lovely Hint

for the lovely string problem

i store the SORTED UNIQUE chars in vector.

Then do

Code: Select all

``````count[0]=1
for(i=0;i<v.size();i++)
{
for(j=0;j<i;j++)
if(v[j]*5 <= v[i]*4)
best[i]=max(best[i],best[j]+1);

if(best[i]>1)
for(j=0;j<i;j++)
if(best[i]==best[j]+1)
count[i]+=count[j];
else
count[i]=1;

In the end sum of all the count[x] where best[x] is the maximum

}

``````
why is this wrong ?

Code: Select all

``````#include<cstdio>
#include<vector>
#include<iostream>
#include<algorithm>
#include<string>
#include<cctype>
#include<cstring>
#include<cstdlib>
using namespace std;

int
main ()
{
int no;
string s;
getline (cin, s);
sscanf (s.c_str (), " %d", &no);

while (no--)
{
int i;
getline (cin, s);
vector < int >v;
int arr[30];
memset (arr, 0, sizeof (arr));

for (i = 0; i < s.size (); i++)
if (isupper (s[i]))
{
if (!arr[s[i] - 'A' + 1])
{
arr[s[i] - 'A' + 1] = 1;
v.push_back (s[i] - 'A' + 1);
}
}

sort (v.begin (), v.end ());
if(v.size()==1){ printf("1 1\n"); continue; }
if(v.size()==0){ printf("0 0\n"); continue; }
/*		for(i=0;i<v.size();i++)
printf("%c,",v[i]+'A'-1);
printf("\n");
*/

int best[v.size () + 1], j;
unsigned long long cnta[v.size () + 1];
memset (best, 0, sizeof (best));
memset (cnta, 0, sizeof (cnta));

cnta[0] = 1;
for (i = 0; i < v.size (); i++)
{
if (best[i] == 0)
{
best[i] = 1;
}
for (j = 0; j < i; j++)
{
if (v[j] * 5 <= 4 * v[i])
{
if ((best[j] + 1) >= best[i])
{
best[i] = best[j] + 1;
}
}
}
if (best[i] > 1)
{
for (j = 0; j < i; j++)
{
if (best[i] == (best[j] + 1))
cnta[i] += cnta[j];
}
}
else
cnta[i] = 1;
}
/*
for(i=0;i<v.size();i++)
printf("%d,",best[i]);
printf("\n");
*/
int mmax = 1;
for (i = 0; i < v.size (); i++)
mmax = max (mmax, best[i]);
unsigned long long cnt = 0;
for (i = 0; i < v.size (); i++)
if (best[i] == mmax)
cnt += cnta[i];
printf ("%d %llu\n", mmax, cnt);

}
return 0;
}

``````

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

### Re: 11569 Lovely Hint

Try this input:
1
ABCDEFGHIJKLMNOPQRSTUVWXYZ

Output should be:
11 7

Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

### Test Cases Needed

Can someone please post some more test cases for this problem. I used a simple DFS in it. i am getting a WA for it and i am unable to find it out. Thanking you in advance.

Here's my code.

Code: Select all

``````Removed
``````
Last edited by Chirag Chheda on Wed Apr 08, 2009 7:31 am, edited 1 time in total.

Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

### Re: 11569 - Lovely Hint

Can someone please reply. I have got lots of WA on this prob

yjwoo14
New poster
Posts: 7
Joined: Wed Jan 09, 2008 5:58 am

### Re: 11569 - Lovely Hint

You can solve this problem by using DP.

1) Keep Length and The number of ways.

2) Are these different? (AABC, CBA ..... )

Chirag Chheda
Learning poster
Posts: 74
Joined: Sat Jun 21, 2008 12:24 pm
Location: India

### Re: 11569 - Lovely Hint

Can u please tell if there is some logical mistake in using DFS ?

JohnTortugo
New poster
Posts: 18
Joined: Sun Jul 20, 2008 7:05 pm

### Re: 11569 - Lovely Hint

Hi.

Chirag, how are you doing that?

Andre Brito
New poster
Posts: 1
Joined: Fri Feb 27, 2009 3:13 pm

### Re: 11569 - Lovely Hint

Can someone help me in this problem?
Can I use a tree or a graph to solve the problem? And is that the easier and fastest way?

Bye.

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Contact:

### Re: 11569 - Lovely Hint

First, take all the uppercase letters and sort them. Suppose a[] is the string now.

1. the length of the longest string can be found using greedy. Try to pick the smaller letter that can be placed. So, you will find the length of the longest lovely string.
2. This part can be found using dp.

Code: Select all

``````rec( i, len ) // This will find the number strings that have length 'len' and the first character assigned in the string is at least the ith character from string a[].
{
res = rec( i + 1, len ); // Find the result from the next character
find j from i + 1 to end, where a[j] can be placed after a[i]
res += rec( j, len - 1 ); // Since we have placed i and a[j] can be placed after a[i], so, a[j+1], a[j+2], ... can also be placed after a[i]
return res;
}``````
Hope these help.
Ami ekhono shopno dekhi...
HomePage