895 - Word Problem

All about problems in Volume 8. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

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

895 - Word Problem

Post by sohel » Sat Jul 17, 2004 7:33 am

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

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.. 8)

.. 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. :o


Is there anything special that I have to consider?

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Re: 895 Word Problem__ Simple isn't it.

Post by .. » Sat Jul 17, 2004 7:34 pm

sohel wrote:but I saw people getting AC in less then 0.1 seconds.. so I think I am missing something very obvious. :o
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.....
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

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

Post by sohel » Sun Jul 18, 2004 6:50 am

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? :)

..
A great helper
Posts: 454
Joined: Thu Oct 18, 2001 2:00 am
Location: Hong Kong

Post by .. » Sun Jul 18, 2004 7:02 am

Sounds right,
but complicate implementation needs more code => more chance of bug...
My signature:
  • Please make discussion about the algorithm BRFORE posting source code.
    We can learn much more in discussion than reading source code.
  • I HATE testing account.
  • Don't send me source code for debug.

L I M O N
Learning poster
Posts: 58
Joined: Wed Dec 31, 2003 8:43 am
Location: Dhaka, Bangladesh
Contact:

Post by L I M O N » Mon Jul 19, 2004 7:31 am

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

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

Post by sohel » Mon Jul 19, 2004 8:32 am

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
New poster
Posts: 3
Joined: Mon Nov 22, 2004 5:26 pm
Location: Tehran

Post by Arktus » Mon Nov 22, 2004 5:37 pm

Hi Sohel

What was your algorithm for finding the permutations?
Arktus

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

Post by sohel » Tue Nov 23, 2004 7:35 am

Arktus wrote: 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
New poster
Posts: 6
Joined: Mon Oct 10, 2005 5:13 am
Location: Taiwan

Post by erictwpt » Sun Oct 30, 2005 4:35 am

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
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

why WA 895???

Post by sakhassan » Tue Sep 26, 2006 7:11 am

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
New poster
Posts: 30
Joined: Tue Oct 17, 2006 5:59 pm

about problem 895 , "WORD PROBLEM"

Post by coolguy » Mon Oct 30, 2006 12:24 pm

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
In good company

coolguy
New poster
Posts: 30
Joined: Tue Oct 17, 2006 5:59 pm

Post by coolguy » Mon Oct 30, 2006 12:32 pm

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

Code: Select all

               cut after AC
Last edited by coolguy on Mon Oct 30, 2006 7:03 pm, edited 1 time in total.
In good company

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Mon Oct 30, 2006 6:49 pm

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.
Ami ekhono shopno dekhi...
HomePage

sakhassan
Experienced poster
Posts: 105
Joined: Sat Mar 11, 2006 9:42 am
Location: cse,DU

Post by sakhassan » Tue Oct 31, 2006 7:36 pm

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

Jan
Guru
Posts: 1334
Joined: Wed Jun 22, 2005 10:58 pm
Location: Dhaka, Bangladesh
Contact:

Post by Jan » Tue Oct 31, 2006 8:09 pm

Remove your code.
Ami ekhono shopno dekhi...
HomePage

Post Reply

Return to “Volume 8 (800-899)”