10126 - Zipf's Law

All about problems in Volume 101. 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
saiqbal
New poster
Posts: 36
Joined: Wed Aug 07, 2002 4:52 pm
Location: Dhaka, Bangladesh
Contact:

Post by saiqbal »

well, it seems quite wiered!! :o 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
New poster
Posts: 37
Joined: Sat Oct 12, 2002 9:54 am
Location: (Taiwan)
Contact:

Post by supermin »

Thank you very much!!!! :P

I miss this mistack........... :cry:

Thanks again.... :D

rjhadley
Learning poster
Posts: 73
Joined: Mon Oct 14, 2002 7:15 am
Location: United States

Post by 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
New poster
Posts: 32
Joined: Thu Jul 31, 2003 6:21 am
Location: Daffodil Univ, Bangladesh
Contact:

10126: Zipf's Law ---- WA

Post by 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]
Last edited by Jewel of DIU on Sat Mar 20, 2004 11:29 am, edited 1 time in total.
Hate WA
Visit phpBB!

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by 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
:wink:

Jewel of DIU
New poster
Posts: 32
Joined: Thu Jul 31, 2003 6:21 am
Location: Daffodil Univ, Bangladesh
Contact:

Post by 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.
Hate WA
Visit phpBB!

shamim
A great helper
Posts: 498
Joined: Mon Dec 30, 2002 10:10 am
Location: Bozeman, Montana, USA

Post by 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. :wink:

Jewel of DIU
New poster
Posts: 32
Joined: Thu Jul 31, 2003 6:21 am
Location: Daffodil Univ, Bangladesh
Contact:

Post by 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)
Hate WA
Visit phpBB!

medv
Learning poster
Posts: 85
Joined: Sun Jul 14, 2002 1:17 pm

10126 TLE

Post by 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?

User avatar
Ali Arman Tamal
Learning poster
Posts: 76
Joined: Sat Jan 15, 2005 5:04 pm
Location: Dhaka
Contact:

10126 - Zipf's Law - one question

Post by 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
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

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

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

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



Time that gone is gone forever ...

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

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

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

Post by sakhassan »

Thanks for ur information .... my code is lack of something ... :oops: :-?
Time that gone is gone forever ...

lena
New poster
Posts: 28
Joined: Mon Mar 05, 2007 5:44 pm

compiler error....

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

Post Reply

Return to “Volume 101 (10100-10199)”