11569 - Lovely Hint

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
User avatar
tryit1
Experienced poster
Posts: 119
Joined: Sun Aug 24, 2008 9:09 pm

11569 - Lovely Hint

Post by tryit1 » Sat Dec 27, 2008 6:05 pm

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;
}


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

Re: 11569 Lovely Hint

Post by sohel » Sat Dec 27, 2008 7:55 pm

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

Post by Chirag Chheda » Fri Jan 09, 2009 6:58 am

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

Post by Chirag Chheda » Sun Jan 11, 2009 9:28 am

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

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

Re: 11569 - Lovely Hint

Post by yjwoo14 » Mon Jan 12, 2009 6:36 am

You can solve this problem by using DP. :D

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

Post by Chirag Chheda » Wed Jan 14, 2009 10:50 am

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

Post by JohnTortugo » Wed Jan 14, 2009 8:50 pm

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

Post by Andre Brito » Fri Feb 27, 2009 3:28 pm

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
Location: Dhaka, Bangladesh
Contact:

Re: 11569 - Lovely Hint

Post by Jan » Sat Feb 28, 2009 4:35 pm

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

Post Reply

Return to “Volume 115 (11500-11599)”