10126 - Zipf's Law

[saiqbal]

well, it seems quite wiered!! i've compiled the code you pasted above using two different compilers and tested them using the above input and got the same following output:

Code: Select all

abcd

There is no such word.
abcd


There is no such word.

and i was so confused that i carefully checked your code afterwards, and got a bug for which this happend. so, it seems you might have changed something in the code posted above otherwise it is impossible to get the output you posted.

about the bug, in your code there's a part as follows:
[c]if(nl) printf("\n");
else nl=1;
[/c]
i just cut this segment and pasted it just above the statement:
[c]inorder(root,num);
[/c]
and after this change your code gave correct output.

i'm quite sure that after making the same change in your code you'll get AC.

good luck
-sohel

[supermin]

Thank you very much!!!!

I miss this mistack...........

Thanks again....

[rjhadley]

As an aggregate, all the string concatentations are fairly expensive:
[cpp]text = text + " " + line;
...
word+=(tolower(ch));[/cpp]

I'm also not familiar with how the sort() function is implemented for a list, but since a list isn't random access, I suspect there are a some inefficiencies that, say, using a vector would eliminate.

[Jewel of DIU]

I got WA in this prob. But I couldnt find any prob in my code. Can anyone help me?
Here is my code
[c]
# include <stdio.h>
# include <stdlib.h>
# include <string.h>
# include <ctype.h>

char zipf[10001][100];

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

char * valid( char *a)
{
int i,l;
l=strlen(a);
for(i=0;i<l;i++)
{
if(!isalpha(a))
{
a=0;
break;
}
/* New addition*/
a=tolower(a);
}
return a;
}
int main()
{
int n,i,t,j,flg,fst=0;
char inp[100];
/*freopen("c:\\inp.txt","r",stdin);*/
while(scanf("%d",&n)==1)
{
i=0;
while(scanf("%s",&inp)==1)
{
if(strcmp(inp,"EndOfText")==0) break;
strcpy(inp,valid(inp));
if(strlen(inp)>1)
strcpy(zipf,inp);
i++;
}
qsort((void *)zipf, i-1, sizeof(zipf[0]), sort_function);
t=i;
flg=j=0;
if(fst!=0) printf("\n");
for(i=1;i<t;i++)
{
if(strcmp(zipf[i-1],zipf)==0) j++;
else
{
if(j==n-1)
{
printf("%s\n",zipf[i-1]);
flg=1;
}
j=0;
}
}
if(j==n-1)
{
printf("%s\n",zipf[i-1]);
flg=1;
}
if(!flg) printf("There is no such word.\n");
fst=1;
}
return 0;
}


[/c]

[shamim]

Here are two quotes from the problem statement.

Words are separated by non-letters. Capitalization should be ignored

For each test case, output the words which occur n times in the input text, one word per line, lower case, in alphabetical order.

Your code does not handle this, for the input :

• 2
  AA AA
  EndOftext

The output should be:

• aa

[Jewel of DIU]

My program is now ok for ur test case. But i got wa again.
If u have enough time then pls look through my code.
Or if u can't then give me more test case.

[shamim]

Here is few lines from your code
[cpp]char inp[100];
/*freopen("c:\\inp.txt","r",stdin);*/
while(scanf("%d",&n)==1)
{
i=0;
while(scanf("%s",&inp)==1)
[/cpp]

Don' you think you made a very basic mistake here.

[Jewel of DIU]

Shamim Bahi, I didn't find any mistake in there.
What can i do?
I change my that portion of code with that. but the result is same.
[c]
char inp[100];
while(scanf("%d",&n)==1)

[medv]

I have TLE in this problem because I use in a program
g += tolower(c);

in a part of code

string g;
char c;
vector<pair<string,int> > v;

while(scanf("%c",&c))
{
if (!isalpha(c))
{
if (g.size() > 0)
{
if (g == "endoftext") break;
i = Find(g);
if (i < 0) v.push_back(make_pair(g,1));
else v[i].second++;
g = "";
}
continue;
}
g += tolower(c);
}

How to increase spped?
If I use not string, but char*, then I have a question:

if I have char a[1000], where I put a word. How to convert
it into string?

[Ali Arman Tamal]

i got rte

i think i have a problem :

does the words consists of only a-z and A-Z ? do i have to consider @ & $ etc symbol as word element or a delimiter.

Can anyone tell me the word and nonword range in this prob.

[Larry]

I assume anything not in [A-Za-z] is a delimiter.

[sakhassan]

I am getting TLE ??? I dont know what's wrong !!!!!!!!!!!

Code: Select all

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

#define N 100
#define M 10001

struct d{

	char str[N];
	int count;

}dic[M];
int count;

void chk(char str[N])
{

	int i;
	int flag;

	flag = 0;

	for(i=0;i<count;i++)
	{

		if(strcmp(str,dic[i].str)==0)
		{
		       flag = 1;
		       dic[i].count++;
		       break;
		}
	}

	if(!flag)
	{
		strcpy(dic[count].str,str);
		dic[count].count++;
		count++;
	}

	return ;

}


int cmp( const d *a, const d *b)
{


	return strcmp(a->str,b->str);
}


int main()
{


   int n;
   int cases;
   char str[N];
   int i;
   int idx;
   int len;
   char temp[N];
   int flag;
   char ch;


   //freopen("10126.cpp","r",stdin);

   cases = 0;
   while(scanf("%d",&n)==1)
   {

	gets(str);
	//if(strlen(str)==0)
	// continue;

	if(cases)printf("\n");

	count = 0;
	for(i=0;i<M;i++)
	{
		dic[i].count=0;
		dic[i].str[0]='\0';
	}


	while(1)
	{

		gets(str);

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



		len = strlen(str);


		flag = 0;
		idx = 0;
		memset(temp,'\0',sizeof(temp));

		for(i=0;i<len;i++)
		{
			ch = str[i];
			if(!isalpha(ch))
			{
				if(flag)
				{

					temp[idx]='\0';
					chk(temp);
					idx=0;
					flag = 0;
					memset(temp,'\0',sizeof(temp));

				}
			}
			else if(isalpha(ch))
			{

			    temp[idx++]=tolower(ch);
			    if(!flag)flag=1;
			}
		}

		if(isalpha(ch) && flag)
		{
		     temp[idx]='\0';
		     chk(temp);
		}

	}

	if(count)
	 qsort(dic,count,sizeof(dic[0]),(int(*)(const void *, const void *))cmp);


	for(i=0;i<count;i++)
	{
		if(dic[i].count==n)
		printf("%s\n",dic[i].str);
	}


	cases++;
   }


   return 0;
}

[Jan]

Though you are using qsort(), your complexity is actually O(n^2). Because you are listing the words first. And while listing you are checking whether this current word exists or not by checking all the other listed words. Just change this idea. First, list all the words. So, there can be duplicate words in the list. Sort them. Then you can find all the non-duplicate words and their frequency in just O(n) time. So, the total complexity will be O(n*log(n)), and which is an acceptable complexity for this problem.

[sakhassan]

Thanks for ur information .... my code is lack of something ...

[lena]

hi,all.
my code run well on my machine. my C++ environment is Dev-C++.but I do konw where is my fault.


#include<cstdio>
#include<cstring>
#include<iostream>
#include<map>
using namespace std;
int n;
map<string ,int> dict;
int main(){
// freopen("10126.txt","r+",stdin);
string str;
map<string ,int>::iterator pos;
int i;
int c = 0;
while(cin>>n){
if(c>0)cout<<endl;
++c;
dict.clear();
while(cin>>str,strcmp(str.c_str(),"EndOfText")!=0){
//cout<<str<<" ";
for(i=0;i<str.size();i++)if(str>'z'||str<'a')break;
if(i<str.size())continue;
pos = dict.find(str);
if(pos!=dict.end()){
(*pos).second++;
}
else{
dict.insert(map<string ,int>::value_type(str,1));
}
}
// cout<<"done"<<endl;
i = 0;
for(pos=dict.begin();pos!=dict.end();pos++){
//cout<<(*pos).first<<" "<<(*pos).second<<endl;
if((*pos).second==n){
cout<<(*pos).first<<endl;
++i;
}
}
if(i==0)cout<<"There is no such word."<<endl;
}
// while(true){}
return 0;
}