11539 - Another Word Game

[Samiul]

Can anybody give a look to my code, it is giving me TLE. Is it my algorithm or using STL?

Code: Select all

deleted

[Leonid]

Your algo seems to be O(n^2). I don't think O(n^2) is enough, you need faster approach.

[sunny]

STL map is too slow for this problem. I used trie to determine the matches at every position.

The maximum word length can be 100. So while doing the DP you only need to check the next 100 positions.

Also avoid using cin too.

[Samiul]

Thanks for your reply. First I am going to try qsort and bsearch, if that doesn't work then I will go for trie.(I like using built-in functions )

[f74956227]

I always get TLE... I first use the STL with TLE and now i use binary search and get TLE again...
Could someone help we or if the code is wrong?

Code: Select all

#include <iostream>
#define MAX 10001
#define MAX_ASCII 26
#define MAX_LEN 110
using namespace std;

typedef struct coding_info
{
	char code_name[MAX_LEN];
	int code_weight;	
}CODING;
CODING coding[MAX], *KEY;

int CMP(const void *a, const void *b)
{
	return strcmp((char*)a, (char*)b);	
}

int main()
{
	//freopen("11539.in","r",stdin);
	int datacase, i, j, l, N, P, worth, dp[MAX], t=0, len, weight, max_l;
	char in[MAX], tmp[MAX];
	
	scanf("%d",&datacase);
	while(datacase--)
	{
		//initialization
		max_l = -1;
		
		scanf("%d %d",&N,&P);

		//read the coding
		for(i=0;i<N;i++)
		{
			scanf("%s %d",coding[i].code_name, &coding[i].code_weight);
			l = (int)strlen(coding[i].code_name);
			max_l >?= l;
		}
		
		//sort the code
		qsort(coding, N, sizeof(CODING), CMP);
		
		//read the original string
		scanf("%s",in);
		l = (int)strlen(in);

		//DP
		for(i=1, dp[0]=0;i<=l;i++)
		{
			//set the initialization value
			dp[i] = dp[i-1] - P;	//not take this element
			for(j=1;j<=i && j<=max_l;j++)
			{
				//set the tmp to be j-i
				strncpy(tmp, in+i-j, j);
				tmp[j] = 0;
				
				//search the key
				KEY = (CODING*)bsearch(tmp, coding, N, sizeof(CODING), CMP);
				
				//dp stratagy
				if(KEY!=NULL)
					dp[i] >?= dp[i-j] + KEY -> code_weight;
				else
					dp[i] >?= dp[i-j] - P*j;
			}	
		}
		printf("Case %d: %d\n",++t,dp[l]);
	}	
	return 0;	
}

[Chirag Chheda]

Can someone please help me on how to reduce the time on this question. I am getting TLE. I used tries for looking up the dictionary and also use memorization for storing the maximum value between any 2 indices once its computed. Any help is appreciated. Thanx in advance.

Code: Select all

#include <iostream>
#define N INT_MIN

using namespace std;

char str[110],s1[10010],s[10010];
int in,len,p,wt,len1;

struct trie
{
       int word;
       int wt;
       struct trie *arr[26];
       
       trie()
       {
             for(int i=0;i<26;i++)
             arr[i]=NULL;
             
             word=0;
             wt=-1;
       }
};

void trie_add(struct trie *p)
{
     if(in==len)
     {
         p->word++;
         p->wt=wt;
         return;
     }
     
     int k = str[in]-'a';
     
     if(p->arr[k]==NULL)
     {
          p->arr[k]=new trie();
     }
     
     in++;
     
     trie_add(p->arr[k]);
}

int check(struct trie *p)
{
     if(p==NULL)
     return 0;
     
     if(in == len1)
     {
           if(p->word)
           return p->wt;
           
           else return 0;
     }
     
     int k = s1[in]-'a';
      in++;
      
      return check(p->arr[k]);
}

int main()
{
    int t,n,i,j,cnt=1,dp[10010],k;
    scanf("%d",&t);
    char ss[120];
    struct trie *root;
    
    while(t--)
    {
         scanf("%d %d\n",&n,&p);
         root = new trie();
         
         while(n--)
         {
             gets(ss);
             sscanf(ss,"%s %d",str,&wt);
             len = strlen(str);
             in = 0;
             wt++;
             
             trie_add(root);
         }
         
         gets(s);
         len = strlen(s);
         
         dp[0]=0;
         for(i=1;i<=len;i++)
         {
             dp[i]=dp[i-1]-p;
             
             for(j=1;j<=i;j++)
             {
                    in=0;
                    for(len1=j-1;len1<i;len1++)
                    s1[in++]=s[len1];
                    s1[in]='\0';
                    
                    len1=in;
                    in=0;
                    
                    k = check(root);
                    
                    if(k>0)
                    dp[i] = max(dp[i],dp[j-1]+k-1);
             }
         }
         
         printf("Case %d: %d\n",cnt++,dp[len]);
    }
    
    return 0;
}

[plamplam]

I didn't use trie, but used hashing instead. Got Accepted in 1.4 seconds. However, there is something wrong with the judging of this problem. I coded in C and I tried several times but whenever I submitted in ANSI C I got TLE. But the same code gets AC in C++ in less than 2 seconds. I tested this several times, and also note that there is no PE for this problem. A PE code gets Wrong Answer.

Some i/o:

Code: Select all

3
15 5
abdbc 20
aaab 15
abb 0
cbcb 14
bcdbcd 17
aaaba 50
bbcbc 5
dcdc 7
dabc 10
dbaba 12
caaaca 14
cbadc 15
baba 10
ababa 12
ccadbb 7
acbdbcbabcbdbcbabcabdddababababcddcbbabcbbba
9 5
a 1
b 0
aaabaa 180
abb 100
bbaba 50
baba 200
aaa 100
aaba 500
babaa 1000
abaabaababababbaabbaaabaaaabababaababaaabaa
7 5
aaabaa 180
abb 100
bbaba 50
baba 200
aaa 100
aaba 500
babaa 1000
abaabaababababbaabbaaabaaaabababaababaaabaa

Code: Select all

Case 1: -183
Case 2: 3908
Case 3: 3845