11539 - Another Word Game

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
Samiul
New poster
Posts: 36
Joined: Thu Dec 13, 2007 3:01 pm

11539 - Another Word Game

Post by Samiul » Sun Oct 26, 2008 1:23 pm

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

Code: Select all

deleted
Last edited by Samiul on Sun Oct 26, 2008 7:31 pm, edited 1 time in total.

Leonid
Experienced poster
Posts: 146
Joined: Thu Dec 22, 2005 5:50 pm
Contact:

Re: 11539 - Another new game

Post by Leonid » Sun Oct 26, 2008 1:37 pm

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

sunny
Experienced poster
Posts: 124
Joined: Sun Sep 11, 2005 10:22 pm
Location: Civil-BUET

Re: 11539 - Another new game

Post by sunny » Sun Oct 26, 2008 3:18 pm

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
New poster
Posts: 36
Joined: Thu Dec 13, 2007 3:01 pm

Re: 11539 - Another new game

Post by Samiul » Sun Oct 26, 2008 7:30 pm

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
New poster
Posts: 37
Joined: Sun Jan 27, 2008 1:50 am
Location: Taiwan
Contact:

Re: 11539 - Another new game

Post by f74956227 » Thu Jan 22, 2009 4:48 pm

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

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

Re: 11539 - Another new game

Post by Chirag Chheda » Sat Apr 04, 2009 10:07 am

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

User avatar
plamplam
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

Re: 11539 - Another new game

Post by plamplam » Thu Nov 22, 2012 2:09 am

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
You tried your best and you failed miserably. The lesson is 'never try'. -Homer Simpson

Post Reply

Return to “Volume 115 (11500-11599)”