895 - Word Problem

[sohel]

This problem looks straight forward.. but I keep getting wrong answer.

I store all the words in the dictionary in an array and ignore words of more than 7 letters.
.. And then for every puzzle I generate all the permutation of different lengths and see if it exists in the dictionary. I also ensure that a word is not repeated..

.. is there anything wrong with this approach.

One more thing : I got WA in around 2.3 seconds , but I saw people getting AC in less then 0.1 seconds.. so I think I am missing something very obvious.


Is there anything special that I have to consider?

[..]

but I saw people getting AC in less then 0.1 seconds.. so I think I am missing something very obvious.

Yes, you really miss something. You have no need to permutate the characters. For each word in the dictionary if count['a'-'z'] <= the character count ['a'-'z'] of the query, then it is alerady possible to get the dictionary word by permutation.....

[sohel]

Thanks for your reply...

But shouldn't permutating the characters and seeing whether it exists work.
It might take longer time but the idea is not wrong, right?

[..]

Sounds right,
but complicate implementation needs more code => more chance of bug...

[L I M O N]

Hellow shohel,

I almost used your algorithm as you descsribed and got accepted.
Do you consider the case that same word may appear more than once
in the dictionary ?

L I M O N

[sohel]

Do you consider the case that same word may appear more than once
in the dictionary ?

You mean the dictionary can contain the same word twice.

For example :

cat
cat
dog
lion
#
c a t
#

will output 2.

I applied the method that .. mentioned and got AC.. but still can't figure out why the original was rejected.

[Arktus]

Hi Sohel

What was your algorithm for finding the permutations?

[sohel]

What was your algorithm for finding the permutations?

Initially applied backtracking..
.. and then I also tried next_permutation().

The trick to this problem is that the dictionary can contain a word twice which seems to be a little unrealistic.

[erictwpt]

sorry for posting my code here, but i cannot get AC after many WA..

i use the algoritms sohel said at first, and it is ok for

cat
cat
dog
lion
#
c a t
#

can anyone help me? Thanks a lot..!!

Code: Select all

#include <stdio.h>
#include <string.h>
int ndic=0,n,u[7],ans;
char s[10000],dic[1000][11],d[8][2],word[8],c,*p;
void subset(int,int);
int BSearch();
main(){
    int i;
    for(i=0;i<7;i++) u[i]=0;
    while(scanf("%s%c",s,&c) && s[0]!='#')
        strcpy(dic[ndic++],s);
    while(gets(s) && s[0]!='#'){
        n=ans=0;
        p=strtok(s," ");
        strcpy(d[n++],p);
        while((p=strtok(NULL," "))!=NULL)
            strcpy(d[n++],p);
        for(i=1;i<=n;i++)       //generate all the permutations
            subset(0,i);
        printf("%d\n",ans);
    }
}
void subset(int level,int len){
    if(level==len){
        word[len]='\0';
        ans+=BSearch();
        return;
    }
    int i;
    char pre='-';
    for(i=0;i<n;i++)
        if(!u[i] && d[i][0]!=pre){
            u[i]=1;
            pre=d[i][0];
            word[level]=d[i][0];
            subset(level+1,len);
            u[i]=0;
        }
}
int BSearch(){          //search for word[] in dic[]
    int left=0,right=ndic-1,mid,r,flag,i;
    while(left<=right){
        mid=(left+right)/2;
        flag=strcmp(word,dic[mid]);
        if(flag==0){
            r=1;
            //the same words in the dictionary?
            for(i=mid-1;i>=0   && strcmp(word,dic[i])==0;i--,r++);
            for(i=mid+1;i<ndic && strcmp(word,dic[i])==0;i++,r++);
            return r;
        }
        if(flag<0) right=mid-1;
        else       left=mid+1;
    }
    return 0;   //not found
}


[sakhassan]

I can't find whats wrong... It seems to be an easy problem

Code: Select all

#include<stdio.h>
#include<string.h>
#include<ctype.h>

#define N 1001

struct d{

   char str[40];
   int len;
   int flag;
}dic[N];

int main()
{

   //freopen("895.txt","r",stdin);

   int indx;
   int i,j;
   int count;
   int len;
   char ch;
   char str[40];

   indx = 0;
   while(1)
   {
      gets(str);
      if(strcmp(str,"#")==0)
         break;

      strcpy(dic[indx].str,str);
      dic[indx].len= strlen(str);
      indx++;
   }

   while(1)
   {
      gets(str);

      if(strcmp(str,"#")==0)
         break;

      for(i=0;i<N;i++)
         dic[i].flag=0;

      len = strlen(str);
      
      for(i=0;i<len;i++)
      {
         ch = str[i];
         if(isalpha(ch))
         {
            for(j=0;j<indx;j++)
            {
               if(strchr(dic[j].str,ch))
               {
                  dic[j].flag++;
               }
            }
         }
      }


      count = 0;
      for(i=0;i<indx;i++)
      {
         if(dic[i].flag>=dic[i].len)
            count++;
      }

      printf("%d\n",count);

      
   }
   return 0;
}




[coolguy]

i cant just get it accepted . there may be something wrong with my approach . can any one provide me some i/o or critical cases . if anyone wants i can give me my source code . please reply .... waiting to be helped
bye bye

[coolguy]

here goes my code for the problem ............please some one help . have i over looked sumthing ???

Code: Select all

               cut after AC


[Jan]

To coolguy, I have sent you a PM.
To sakhassan, try the following I/O set.

Input:

Code: Select all

abc
bcd
cde
def
eee
eff
eggg
ffff
#
e e e
#

Output:

Code: Select all

1

Hope you both get accepted.

[sakhassan]

Thanks J@N .. I changed ma code and got AC

[Jan]

Remove your code.