## 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

Samiul
New poster
Posts: 36
Joined: Thu Dec 13, 2007 3:01 pm

### 11539 - Another Word Game

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

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

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

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

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

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
Experienced poster
Posts: 150
Joined: Fri May 06, 2011 11:37 am

### Re: 11539 - Another new game

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