11569 - Lovely Hint

[tryit1]

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]

Try this input:
1
ABCDEFGHIJKLMNOPQRSTUVWXYZ

Output should be:
11 7

[Chirag Chheda]

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

[Chirag Chheda]

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

[yjwoo14]

You can solve this problem by using DP.

1) Keep Length and The number of ways.

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

[Chirag Chheda]

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

[JohnTortugo]

Hi.

Chirag, how are you doing that?

[Andre Brito]

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]

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.