10226 - Hardwood Species

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

Moderator: Board moderators

Post Reply
minskcity
Experienced poster
Posts: 199
Joined: Tue May 14, 2002 10:23 am
Location: Vancouver

Post by minskcity » Fri Oct 22, 2004 5:16 am

First of all, if you are getting compile error it is a good idea to mention what kind of complile error you are getting...

I have used hash_map for some problems on Valladolid - it works. Judge is saying he does not know what 'collate' is... As far as I understand you are using collate for hashing. You have two choices:
1) Figure out how to make the judge understand collate.
2) Implement you own hashing. (shifting, bitwise ^&|, no -+*/%) :-?

In any case I recommend you to switch string to char[] - strings are twice as slow as char[]. :wink:

Ask you if have any specific questions.

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

10226 Hardwood Species Compile Error!!!

Post by neno_uci » Sat Mar 19, 2005 7:10 am

Why do I always get CE???
This is my code:

Code: Select all

#include <iostream>
#include <stdio.h>
#include <map>

using namespace std;

int main()
{
	map<string, int> mapa;
	char lines[101];
	int test, n;
	
	scanf("%d", &test);
	gets(lines);
	
	for (int t = 1; t <= test; t++)
	{
		if (t > 1)
			putchar('\n');
		
		mapa.clear();
		gets(lines);
		n = 0;
		
		while (strlen(gets(lines)))
		{
			mapa[string(lines)]++;
			n++;
		}
		
		map<string, int>::iterator ptr = mapa.begin();
		map<string, int>::iterator end = mapa.end();
		
		do
		{
			cout << ptr->first << " ";
			printf("%0.4lf\n", (100.0 * ptr->second) / (1.0 * n));
		}
		while (++ptr != end);
	}
	
	return 0;
}
Thanx in advance,
Yandry.

neno_uci
Experienced poster
Posts: 104
Joined: Sat Jan 17, 2004 12:26 pm
Location: Cuba

Post by neno_uci » Sat Mar 19, 2005 9:05 am

I got AC using BST :D

Ankur Handa
New poster
Posts: 6
Joined: Mon May 15, 2006 11:34 am

10226 TLE ???

Post by Ankur Handa » Tue May 23, 2006 10:44 pm

i am still getting TLE in this question . Can somebody help me sort out
this problem ..
here is the code

Code: Select all

#include<iostream>
#include<stdio.h>
#include<map>
#include<string>
using namespace std;
int main(void)
{
        map<string,int>Plant;
        int Tcases=0,Cnt=0;
        double num;
        char str[40];
        scanf(" %d",&Tcases);
        getchar();
        getchar();
        for(int i=0;i<Tcases;i++)
        {
                Cnt=0;
                while(1)
                {
                        scanf("%[^\n]",str);
                        getchar();
                        if(strcmp(str,"")==0)
                                break;
                        if(Plant.find(str)!=Plant.end())
                        Plant[string(str)]++;
                        else Plant[string(str)]=1;
                        Cnt++;
                        str[0]='\0';
                }
                for(map<string,int>::iterator iter=Plant.begin();iter!=Plant.end();iter++)
                {
                        printf("%s",((*iter).first).c_str());
                        num = (double)((*iter).second)*100/(double)Cnt;
                        printf(" %.4lf\n",num);
                }
                Plant.clear();
                printf("\n");
                getchar();

        }
}
Thanks in advance

Psyco
New poster
Posts: 14
Joined: Sat Jan 21, 2006 12:39 pm
Contact:

10226... Runtime Error

Post by Psyco » Sun May 28, 2006 7:48 am

I got RTE, But Why?

Code: Select all

#include <stdio.h>
#include <string.h>
char str[1000001][31], t[31]; int i, j, n, cnt;
double x;
int main()
{
	while(gets(str[n])!=NULL)
		n++;
	for(i=0;i<n;i++){
		for(j=i+1;j<n;j++){
			if(strcmp(str[i],str[j])>0){
				strcpy(t,str[i]);
				strcpy(str[i],str[j]);
				strcpy(str[j],t);
			}
		}
	}
	for(i=0;i<n;i++){
		cnt=1;
		for(j=i+1;j<n;j++){
			if(strcmp(str[i],str[j])!=0)
				break;
			cnt++;
		}
		x=double(cnt)/double(n)*100;
		printf("%s %.4f\n",str[i],x);
		i=j-1;
	}
}

Antonio Ocampo
Experienced poster
Posts: 131
Joined: Sat Jul 17, 2004 4:09 am
Location: Lima, Per

Post by Antonio Ocampo » Mon Jan 08, 2007 7:52 pm

I've got WA too :( Please help me!!

Code: Select all

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <map>

#define Fe(it,v) for(__typeof__ ((v).begin()) it=v.begin();it!=(v).end();++it )

using namespace std;

int main()
{
   int casos;

   scanf("%d",&casos);

   while(casos--)
   {
     map <string,int> m;
     string s;
     int ct=0;

     getline(cin,s); /* white line */
     while(getline(cin,s)&&s!="")
     {
        ++m[s];
        ++ct;
     }

     Fe(it,m) printf("%s %.4lf\n",((*it).first).c_str(),(*it).second*100.0/ct);
     if(casos) putchar('\n');
   }
}

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

Post by Jan » Tue Jan 09, 2007 12:00 am

Antonio Ocampo wrote:I've got WA too
Are you sure? :D
I solved it with manual hashing. May be stl would be too slow for this problem.
Ami ekhono shopno dekhi...
HomePage

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

Post by cytmike » Wed Jan 10, 2007 5:35 am

How do you do manual hashing?
I also get WA by using STL. Seems like STL hash table is not working too well, not as good as Java's hash table.
Impossible is Nothing.

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

Post by Jan » Wed Jan 10, 2007 10:31 pm

Suppose you have total 'N' linked lists numbered from 0 to N-1. Each element has two values, name and occurrance. Now you have generated a Hash function for the names. Remember that it would be better if the Hash function returns different values for different names.

Now suppose you have got one name. Find its hash value. Let R = Hash Value % N (Or you can design the hash function such that it returns a value less than N).

Go to the Rth linked list. Start checking all the elements in that list. If you find a name which is similar to your name then just increase the occurrance of that element. Otherwise make occurrance = 1 and add the name and occurrance in that (Rth) list.

Finally traverse all the lists to gather needed informations.

Hope you understand.
Ami ekhono shopno dekhi...
HomePage

Mushfiqur Rahman
Learning poster
Posts: 56
Joined: Tue Jun 13, 2006 5:18 pm
Location: (CSE, SUST) Sylhet, Bangladesh
Contact:

Post by Mushfiqur Rahman » Mon May 14, 2007 8:46 pm

I saw heres a lot of discussion about solving the problem by stl ( hash maping ). But it can be easily solved by BST within 5 sec.
:lol: :lol: :lol:

User avatar
cytmike
Learning poster
Posts: 95
Joined: Mon Apr 26, 2004 1:23 pm
Location: Hong Kong and United States
Contact:

Post by cytmike » Tue Dec 25, 2007 8:14 pm

With the new judge server, I tried my old code (<30 lines) and it gets accepted in 2.2s.

So it is possible to use STL map to get AC now, using the way described by Larry (3 years ago).

Remember to use gets to read input, using cin will cause TLE.

It feels so good to solve a problem after 3.5 years! :D My programming experience is so different now.
Impossible is Nothing.

kangroo
New poster
Posts: 13
Joined: Fri Sep 12, 2008 9:12 am

Re: 10226 - Hardwood Species --- getting TLE

Post by kangroo » Sat Oct 25, 2008 1:30 pm

hi everyone,

I tried to solve this problem using tries (implementing a structure)...but keep getting TLE...
I think the problem is when getting inputs...
Below is my code ...anyone pls help me !!!
thanks in advance..!!

Code: Select all

#include <iostream>
using namespace std;

struct node
{
 string word;
 int cnt;
 struct node *left;
 struct node *right;
}; 

int n;

struct node *addtree ( struct node *p , string s )
{
 int c;
 if ( p == NULL ) 
 {
  p = new node();
  p -> word = s;
  p -> cnt = 1;
  p -> left = p -> right = NULL;
 }

 else if ( s == p -> word ) p -> cnt ++;
 else if ( s < p -> word ) p -> left = addtree ( p -> left , s );
 else p -> right = addtree ( p -> right , s );
 
 return p;
}



void printtree ( struct node *p )
{
 if ( p != NULL )
 {
  printtree ( p -> left );
  double per = ( ( ( p -> cnt ) * 1. ) / ( n * 1. ) ) * 100.;
  printf ( "%s %.4lf\n" , (p -> word).c_str() , per );
  printtree ( p -> right );
 }
}





int main ()
{
 int t; scanf ( "%d" , &t );
 getchar(); 
 bool fg = 0;
 while ( t -- )
 {
  getchar(); 
  struct node *root;
  root = NULL;
  n = 0;
  while ( true ) 
  {
   string s;
   getline ( cin , s );
   if ( s == "" ) break;
   n ++;
   root = addtree ( root , s );
  }
  if ( !fg ) fg = 1;
  else printf ( "\n" );
  printtree (root);
 }
 return 0;
}

thanks in advance !!

sazzadcsedu
Experienced poster
Posts: 136
Joined: Sat Nov 29, 2008 8:01 am
Location: narayangong,bangladesh.
Contact:

10226 - Hardwood Species

Post by sazzadcsedu » Mon May 24, 2010 4:40 pm

This problem can be solved by stl map && priority queue.And its running time is good.my Acc program run in 2.428s(current ranking 280).
Life is more complicated than algorithm.
http://felix-halim.net/uva/hunting.php?id=32359
For Hints: http://salimsazzad.wordpress.com

Shafaet_du
Experienced poster
Posts: 147
Joined: Mon Jun 07, 2010 11:43 am
Location: University Of Dhaka,Bangladesh
Contact:

Re: 10226 - Hardwood Species

Post by Shafaet_du » Sat Sep 11, 2010 10:13 pm

Code: Select all

1

orange
orange
mango
biriyani
icecream
orange
orange
biriyani
pine apple
what the hell is this tree 
what the hell is this tree
oak tree
longest tree ever
a tiny tree
pine apple
longest tree ever
this problem is not tough
you should know stl
this problem is not tough
a tiny tree
a tiny tree
you should know stl
try to pass this sample
mango
mango
accepted
accepted
wrong answer
runtime error
dont make precision error
try to pass this sample
dont make precision error
dont make precision error
don 4get to typecast if you divide int by an int n store result in double
don 4get to typecast if you divide int by an int n store result in double
try to pass this sample
hope this helps
dont see the board before trying the problem
it will spoil you
hope this helps
output from my ac code:

Code: Select all

a tiny tree 7.5000
accepted 5.0000
biriyani 5.0000
don 4get to typecast if you divide int by an int n store result in double 5.0000
dont make precision error 7.5000
dont see the board before trying the problem 2.5000
hope this helps 5.0000
icecream 2.5000
it will spoil you 2.5000
longest tree ever 5.0000
mango 7.5000
oak tree 2.5000
orange 10.0000
pine apple 5.0000
runtime error 2.5000
this problem is not tough 5.0000
try to pass this sample 7.5000
what the hell is this tree 2.5000
what the hell is this tree  2.5000
wrong answer 2.5000
you should know stl 5.0000

nhrahi
New poster
Posts: 6
Joined: Tue Aug 25, 2009 7:38 pm

Re: 10226 - Hardwood Species

Post by nhrahi » Fri Jan 07, 2011 8:36 pm

can anyone please help me with what's wrong with my code????? i just cant get it working,it is always missing the first item.i think i am having troubles with the input,please help me with a hint on what's wrong.

Code: Select all

#include<iostream>
#include<map>
#include<string>
#include<cstring>
#include<cstdio>
#include<cstdlib>

#define MAX 10000
using namespace std;

char seq[MAX];

int main(){
  //  freopen("10226.txt","r",stdin);
    map<string,int>t;
    string str,str1;
    int test;
        cin.getline(seq,MAX);
        test=atoi(seq);
        getline(cin,str);
        for(int i=1;i<=test;i++){

            int total=0;
            t.clear();
            while(getline(cin,str1) && (str1.size()>=1)){
                t[string(str1)]++;
                total++;
   //            cout<<total<<endl;
            }
           // cout<<total<<endl;
            map<string,int>::iterator iter;
            for(iter=t.begin();iter!=t.end();iter++){

              cout<<iter->first<<" ";
              printf("%0.4lf\n",(100.0*iter->second)/(1.0*total));
            }
            if(i>1);
             cout<<endl;
        }

    return 0;
}

Post Reply

Return to “Volume 102 (10200-10299)”