Page 2 of 3
Posted: Mon Mar 31, 2003 4:21 pm
by 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
Posted: Mon Mar 31, 2003 6:53 pm
by supermin
Thank you very much!!!!
I miss this mistack...........
Thanks again....
Posted: Sun Jun 22, 2003 1:44 am
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.
10126: Zipf's Law ---- WA
Posted: Tue Mar 16, 2004 10:13 pm
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]
Posted: Wed Mar 17, 2004 9:37 am
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 :
The output should be:
Posted: Sat Mar 20, 2004 11:25 am
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.
Posted: Sat Mar 20, 2004 11:44 am
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.
Posted: Sat Mar 20, 2004 3:34 pm
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)
10126 TLE
Posted: Sun Jun 05, 2005 8:27 pm
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?
10126 - Zipf's Law - one question
Posted: Sun Oct 02, 2005 10:57 am
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.
Posted: Sun Oct 02, 2005 11:47 am
by Larry
I assume anything not in [A-Za-z] is a delimiter.
Posted: Sat Nov 25, 2006 9:10 am
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;
}
Posted: Sat Nov 25, 2006 11:48 pm
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.
Posted: Sun Nov 26, 2006 5:37 pm
by sakhassan
Thanks for ur information .... my code is lack of something ...
compiler error....
Posted: Thu Sep 06, 2007 2:59 pm
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;
}