10126 - Zipf's Law

[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 ...

[mirage]

hi friends,
i m gettin wrong answer on the OJ for this easy prob........the program is passing the test that i gave it n the one ones i found in the forums.....
still unable to find the bug....plz help......
is thr any special way to print the output for this prob...
here's the code:

Code: Select all

//Zipf's law
#include<iostream>
#include<map>
#include<string>
using namespace std;
int main(){
   int n;
   int count=0;
   while(cin>>n){
      if(count++!=0) cout<<"\n";
      string s;
      int loop=1;
      map<string,int> maps;
      while(loop==1){   
         getline(cin,s,'\n');
         s=s+" ";   
         int i=0;
         while(i<s.length()){
            string h="";
            int val=s[i];
            string alias="";
            while((val>=65 && val<=90)|| (val>=97 && val<=122)){
               if(val>=90) h=h+s[i];
               else h=h+char(s[i]+32);
               alias=alias+s[i++];
               val=s[i];
            }
            i++;
            if(alias=="EndOfText"){
               loop=0;
               break;
            }
            maps[h]=maps[h]+1;
         }
      }
      map<string,int>::iterator iter;
      iter=maps.begin();
      int l=0;
      while(iter!=maps.end()){
         if(iter->second==n) {
            cout<<iter->first<<"\n";
            l=1;
         }
         iter++;
      }
      if(l==0) cout<<"There is no such word."<<"\n";
      maps.clear();
   }
   return(0);
}


[Jehad Uddin]

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

[sd12582000]

try
input

2
a-a
EndOfText

output
a